A Stochastic Algorithm for Solving Linear RC Networks: Pruning the Transition-Diagram Tree

RC circuit evaluation is important for many applications in electrical design; particularly for high-end, digital IC-interconnect CAD. Such circuits are often too large to solve efficiently with traditional methods. Le Coz et al. have developed a method for solving these kinds of circuits at low frequencies. They used stochastic random walks based on a Taylor Series state-diagram approximation. Their method neglected high-order impulse-response moments. Thus, it is unsuitable at elevated frequencies comparable to inverse RC-circuit time constants. We have developed a state-diagram "pruning algorithm" for higher-frequency application, eliminating any need for a Taylor Series approximation. This is accomplished by altering the circuit's transition diagram to limit the number of weight factors that can cause non-convergent growth in stochastic evaluation. Preliminary trials of our new algorithm were performed. The trials achieved less than 4% error at a normalized characteristic frequency ω = 0.2. A third order Taylor Series approximation, on the other hand, yielded close to 150% error. Opportunities for future research include self- and mutual- inductance effects, and parallel software and hardware acceleration.