IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2002 · 331 citations · 23 references
ComputingComputer EngineeringComputer ScienceComputer-aided DesignDesign AutomationFormal MethodsBoolean AlgebraDesign RepresentationDigital Logic DesignEquivalence CheckingLogic SynthesisVerificationBinary Decision DiagramsBoolean ExpressionsBoolean SatisfiabilityCircuit Equivalence CheckingFalse Path AnalysisProperty VerificationSatisfiability
Computer‑aided design tasks such as equivalence checking, property checking, logic synthesis, and false‑path analysis rely on efficient Boolean reasoning, yet existing canonical methods like BDDs and SAT each excel only on specific problem structures and lack a universally robust solution. The authors aim to create a unified Boolean reasoning framework that combines BDDs, structural transformations, SAT, and random simulation on a shared graph representation. Their approach integrates these techniques by operating natively on a common graph, leveraging BDDs for functional analysis, structural transformations for simplification, SAT for constraint solving, and random simulation for probabilistic verification. Experiments show that this intertwined integration harnesses the orthogonal strengths of each method, proving effective for formal equivalence checking, property verification, and other CAD applications across a broad set of problems.
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.
23
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
A machine program for theorem-proving
Martin Davis, George Logemann, Donald Loveland · Communications of the ACM · 1962 · 3.2K citations · Full text
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
A Computing Procedure for Quantification Theory
Martin Davis, Hilary Putnam · Journal of the ACM · 1960 · 2.6K citations · Full text
Akers · IEEE Transactions on Computers · 1978 · 1.8K citations