Theory of a Stochastic Algorithm for Capacitance Extraction in Integrated Circuits

We present the theory of a novel stochastic algorithm for high-speed capacitance extraction in complex integrated circuits. The algorithm is most closely related to a statistical procedure for solving Laplace’s equation known as the floating random-walk method. Our analysis begins with surface Green’s functions for Laplace’s equation on a scalable square domain. From them, we obtain integrals for electric potential and electric field at the domain center. An electrodecapacitance integral is next derived. This integral is expanded as an infinite sum, and probability rules that statistically evaluate the sum are deduced. These rules define the algorithm.