Efficient Spectral Coefficient Calculation Using Circuit Output Probabilities

✍ Scribed by M.A. Thornton; V.S.S. Nair

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 765 KB
• Volume: 4
• Category: Article
• ISSN: 1051-2004
• DOI: 10.1006/dspr.1994.1024

✦ Synopsis

Thornton, M. A., and Nair, V. S. S., Efficient Spectral Coefficient Calculation Using Circuit Output Probabilities, Digital Signal Processing 4 (1994), 245-254.

Many problems in the field of digital logic may be solved more efficiently in the spectral domain than in the Boolean domain. However, the primary drawback of spectral techniques is the large complexity associated with the calculation of the spectrum of a Boolean function. We present a new method for the computation of a spectral coefficient that has a complexity equal to (O(|E|)) where (|E|) is the number of edges in a binary decision diagram characterizing the circuit. This result is especially significant for techniques that require the calculation of only a few spectral coefficients since it allows the computations to be accomplished very efficiently and does not require storage resources for a large number of values. Furthermore, this method holds for any general spectral transform and does not require the transformation matrix to be recursively defined or sparse. c 1.194 A Arademir Press. Inc