Error bounds for capacitance extraction via window techniques

The overwhelming size of the capacitance extraction problem forces designers 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 shift-truncate method and the windowing method yield opposite bounds for the exact values of the mutual and self capacitances. It is also shown that the capacitance matrices resulting from the application of these two localization methods are positive definite and, therefore, lead to stable approximations of the exact parasitics system. For the windowing method, we show that the original asymmetric capacitance matrix can be made symmetric while guaranteeing the positive definiteness and making the error bounds even tighter. 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 zones for interconnect optimization and noise reduction, and for the generation of noise-reducing design rules