Error bounds for capacitance extraction via window techniques

The overwhelming size of the capacitance extraction problem forces designer s to localize the capacitive coupling and determine a distance (a "window") outside of which the mutual capacitance between two wires is "small enough " to ignore. The primary difficulties with such approaches are determining how large the extraction windows have to be to capture all of the relevant mutual capacitances, and estimating the error incurred due to "windowing." This paper proposes solutions for both problems. We first show that the shi ft-truncate method [1] and the windowing method yield opposite bounds for t he exact values of the mutual and self capacitances. It is also shown that the capacitance matrices resulting from the application of these two locali zation methods are positive definite and, therefore, lead to stable approxi mations of the exact parasitics system, For the windowing method, we show t hat the original asymmetric capacitance matrix can be made symmetric while guaranteeing the positive definiteness and making the error bounds even tig hter. In summary, we describe an adaptive, window sizing methodology based on error values from the windowing and shift-truncate bounds. The proposed methodology is also potentially useful in identifying crosstalk problem zon es for interconnect optimization and noise reduction, and for the generatio n of noise-reducing design rules.