Predicting the functional complexity of combinational circuits by symbolic spectral analysis of Boolean functions

Spectral analysis of Boolean functions represents an elegant approach to the problem of estimating the complexity of digital designs. In general, however, the use of spectral techniques in logic synthesis has been very limited in the past because Boolean functions associated with circuits of interest are usually too large and complex to allow the computation of their corresponding spectral representations using traditional techniques. In this paper we present a symbolic formulation of the logic complexity prediction problem, and we propose an ADD-based algorithm that performs well, in terms of both execution time and accuracy in the estimation, on circuits that are sensibly larger than the ones usually handled by the tools currently available. Experimental results on discussed in detail to support this claim