An impulse-response based linear time-complexity algorithm for lossy interconnect simulation

Abstract

A linear time-complexity algorithm for lossy transmission line simulation within arbitrary nonlinear circuits is presented. The method operates by storing information about the state of the line at dynamically selected internal points and using an analytical formulation based on impulse responses to predict the line's future behavior accurately. Previous approaches using impulse responses possess quadratic-time complexity. The proposed method does not require rational or other approximations of transfer functions to achieve linear time-complexity, nor does it increase the size of the simulator's matrix by more than 2 for each transmission line. Experimental results on industrial circuits indicate that, for equivalent or superior accuracy, the state-based method can be faster for simulations of one or more block or data pulses, with speedups of more than 10 and 50 over the convolution and lumped-RLC methods for the longer simulations.