Boolean function representation and spectral characterization using AND/ORgraphs

Methods based on AND/OR graph representations of Boolean relations provide a promising new way of approaching VLSI CAD design automation problems. AND /OR graphs can represent any Boolean network and they allow for systematic reasoning through the application of the technique of recursive learning. A n approach to build and analyze AND/OR graphs that makes use of hashing tec hniques in a way similar to that for modern Decision Diagram (DD) packages is described. Additionally, the problem of extracting spectral information from AND/OR graphs is also examined. Spectral information can be used for m any CAD system tasks including synthesis, verification and test vector gene ration. It is shown that spectral information may be calculated directly fr om output probabilities and a method for estimating output probabilities fr om AND/OR graphs is presented. Experimental results regarding the AND/OR gr aph package efficiency and the extraction of spectral information are provi ded. (C) 2000 Elsevier Science B,V. All rights reserved.