Efficient time-domain simulation of frequency-dependent elements

ABSTRACT

We describe an efficient algorithm for the time-domain simulation of elements described by causal impulse responses. The computational bottleneck in the simulation of such elements is the need to compute convolutions at each time point. Hence, direct approaches for the simulation of such elements require time O(N^2), where N is the length of the simulation. We apply ideas from approximation theory to reduce this complexity to O(N \log N) while maintaining double-precision accuracy. The only restriction imposed by our method is that the impulse response h(t) gets ``smoother'' as t goes to infinity. Essentially all physically reasonable impulse responses have this characteristic. The ideas presented can also be applied to time-domain simulation of elements described in the frequency domain, including those characterized by measured data. In this paper, we demonstrate the efficiency of the algorithm by applying it to the simulation of lossy transmission lines.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: Bradley K. Alpert , Vladimir Rokhlin, A fast algorithm for the evaluation of Legendre expansions, SIAM Journal on Scientific and Statistical Computing, v.12 n.1, p.158-179, Jan. 1991 [doi>10.1137/0912009]
• 3: J.E. Bracken, V. Raghavan, and R. A. Rohrer. Interconnect simulation with Asymptotic Waveform Evaluation. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 39(11):869-878, November 1992.
• 4: Germund Dahlquist , Ake Bjorck, Numerical Methods, Dover Publications, Incorporated, 2003
• 5: H.W. Dommel. Digital computer solution of electromagnetic transients in single and multiphase networks. IEEE Transactions on Power Apparatus and Systems, PAS- 88(4):388, April 1969.
• 6: A. Dutt and V. Rokhlin. Fast Fourier transforms for nonequispaced data, II. Applied and Computational Harmonic Analysis, 2(1):85-100, January 1995.
• 7: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 8: R. Griffith, E. Chiprout, Q. Zhang, and M. Nakhla. A CAD framework for simulation and optimization of highspeed VLSI interconnections. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 39(11):893-906, November 1992.
• 9: S. Lin and E. S. Kuh. Transient simulation of lossy interconnects based on the recursive convolution formula. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 39(11):879-892, November 1992.
• 10: J. S. Roychowdhury, A. R. Newton, and D. O. Pederson. Algorithms for the transient simulation oflossy interconnect. IEEE Transactions on Computer-Aided Design of lntegrated Circuits, 13(1):96-104, January 1994.
• 11: A. Semlyen and A. Dabuleanu. Fast and accurate switching transient calculations on transmission lines with ground return using recursive convolution. IEEE Transactions on Power Apparatus and Systems, PAS-94:561-571, 1975.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.4 Performance Analysis and Design Aids**
          Subjects: Simulation**

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Theory

Keywords:
time-domain simulation, transient simulation, transmission lines, convolution