Civil Engineering Reference
In-Depth Information
variables‚ if a Gaussian; if a
Guassian‚ it may be reasonable to approximate this maximum using a Gaus-
sian. This method was applied and found to be highly effective in [Ber97].
It was suggested there that a statistical sampling approach could be used to
approximate the mean and variance of the distribution; alternatively‚ this infor-
mation could be embedded in look-up tables. In later work in [JB00]‚ a precise
closed-form approximation for the mean and variance‚ based on [Pap91]‚ was
utilized.
6.4.2
Discrete PDFs
Statistical timing analysis has also been pursued in the test community. The
approach in [CW00] takes into account capacitive coupling and intra-die pro-
cess variation to estimate the worst case delay of critical path. The technique
in [LCKK01] uses a discrete PDF based method to propagate discrete PDFs
through the circuit‚ developing effective heuristics to overcome inaccuracies in
event propagation due to reconvergences. The work in [LKWC02] uses a Monte
Carlo sampling-based framework to analyze circuit timing on a set of selected
sensitizable true paths. Similar lines of investigation as [LCKK01‚ LKWC02]
have also been independently pursued in [Nai02].
The work in [DK03] develops an efficient algebra for the computation of
discrete probabilities in a block-based approach. For a single input gate‚ the
convolution described in Equation (6.12) may be used to propagate a discrete
PDF forward‚ except that instead of propagating the PDF of the signal prob-
ability forward‚ we now propagate the PDF of the arrival time instead. For
multiinput gates‚ a “max” operation must be carried out: for a
gate
with arrival times and input-to-output delays
the arrival time at the output is found as the PDF of
Instead of a discrete PDF‚ this method uses a piece-wise constant PDF‚ which
translates to a piecewise-linear cumulative density function (CDF); recall that
the CDF is simply the integral of the PDF.
The CDF of
is easily computed given the PDFs of the
and
The PDF of
can be obtained by convolving their respective PDFs‚ i.e.‚
where represents the convolution operator. It can be shown that the CDF
of this sum is given by
The CDF of the maximum of a set of
independent
random variables is easily
verified to simply be the product of the CDFs‚ so that we obtain
