Logic verification using binary decision diagrams in a logic synthesis environment

The results of a formal logic verification system implemented as part of the multilevel logic synthesis system MIS are discussed. Combinational logic verification involves checking two networks for functional equivalence. Techniques that flatten networks or use cube enumeration and simulation cannot be used with functions that have very large cube covers. Binary decision diagrams (BDDs) are canonical representations for Boolean functions and offer a technique for formal logic verification. However, the size of BDDs is sensitive to the variable ordering. Ordering strategies based on the network topology are considered. Using these strategies with BDDs, it has been possible to carry out formal verification for a larger set of networks than with existing verification systems. The present method proved significantly faster on the benchmark set of examples tested.