Many tasks in computer-aided design (CAD), such as equivalence checking, property checking, logic synthesis, and false paths analysis, require efficient Boolean reasoning for problems derived from circuits. Traditionally, canonical representations, e.g., binary decision diagrams (BDDs), or structural satisfiability (SAT) methods, are used to solve different problem instances. Each of these techniques offer specific strengths that make them efficient for particular problem structures. However, neither structural techniques based on SAT, nor functional methods using BDDs offer an overall robust reasoning mechanism that works reliably for a broad set of applications. The authors present a combination of techniques for Boolean reasoning based on BDDs, structural transformations, an SAT procedure, and random simulation natively working on a shared graph representation of the problem. The described intertwined integration of the four techniques results in a powerful summation of their orthogonal strengths. The presented reasoning technique was mainly developed for formal equivalence checking and property verification but can equally be used in other CAD applications. The authors' experiments demonstrate the effectiveness of the approach for a broad set of applications.

This paper presents a verification technique which isspecifically targeted to formally comparing large combinational circuits with some structural similarities. The approach combines the application of BDDs withcircuit graph hashing, automatic insertion of multiple cut frontiers, and a controlled elimination of false negative verification results caused by the cuts. Twoideas fundamentally distinguish the presented technique from previous approaches. First, originating from the cut frontiers, multiple BDDs are computedfor the internal nets of the circuit, and second, theBDD propagation is prioritized by size and discontinued once a given limit is exceeded.

In this paper we present the application of random simulation in formal verification of functional equivalence of hardware designs. We demonstrate that random simulation can effectively complement BDD-based verification approaches in three areas: (1) quick generation of counter example pattern for miscomparing designs, (2) exhaustive comparison of small functions, and (3) providing meaningful signatures for design partitioning based on functionally equivalent cut-points. The presentation describes a smooth and efficient integration of a simulation algorithm into a general verification framework. In this framework the simulator can be applied as one of various engines for Boolean reasoning the outcome of which might be undecided.