Delay Analysis of Digital Circuits Using Prony's Method

Abstract

This thesis describes possible applications of Prony's method in timing analysis of digital circuits. Such applications include predicting the future shape of the waveform in DTA(Dynamic Timing Analysis) and delay look-up table in STA(Static Timing Analysis).

Given some equally spaced output values, the traditional Prony's method can be used to extract poles and residues of a linear system, i.e. to characterize a waveform using an exponential function. In this thesis, not only values but also equally spaced derivatives are tested. Still using same idea of the traditional Prony's method, poles and residues can also be extracted with those values and derivatives. The resultant poles and residues will be used to predict the output waveform in DTA analysis. The benefits brought by the using of derivatives include less simulation steps and less CPU time consuming than the regular constant step simulation.

As a matter of fact, the Prony's method can precisely approximate a complicated waveform. Such property can be applied for STA analysis. The Prony's approximation can be used to precisely record an output waveform, which is used as an entry of the look-up table of STA. Since the accuracy of STA analysis relies on the accuracy of the input and output waveform in the look-up table, the accuracy of the Prony's approach is promising.