PREDICTING THE COMPLEXITY OF LARGE COMBINATIONAL-CIRCUITS THROUGH SYMBOLIC SPECTRAL-ANALYSIS OF THEIR FUNCTIONAL SPECIFICATIONS

The use of symbolic data structures to store pseudo-Boolean (i.e. inte ger-valued) functions has proved to be extremely effective in handling both transform matrices and spectral representations of large Boolean functions. The authors propose a novel application of symbolic spectr al analysis techniques to the prediction of the complexity of a combin ational circuit. They present a symbolic formulation of the problem, a nd propose an implicit algorithm for its solution that performs well, in terms of both execution time and accuracy in the computation, on ci rcuits that are sensibly larger than the ones usually handled by the t ools currently available. Experimental results, collected on standard examples, are discussed to support this claim.