2003 · 64 citations · 6 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsCircuit TheoryVlsi DesignCombinational Logic DescriptionDeductive VerificationDigital Logic DesignEquivalence CheckingLogic SynthesisVery-large-scale Integration LayoutCircuit Equivalence CheckingCombinational Equivalence CheckingCut-based SynthesisEquivalent CircuitsHardware Equivalence CheckingSignals
A method is described for circuit equivalence which proceeds by reducing the question of whether two circuits are equivalent to a number of a more easily answered questions concerning the equivalence of smaller, related circuits. The primary technical contribution is a technique for discovering internal equivalences and using them to show the equivalence of the outputs. The method involves the use of signatures to reduce the number of potentially equivalent signals, and the use of the min-cut algorithm to reduce the original problem to related problems with fewer independent inputs. The method can be used to extend the power of any given equivalence checking algorithm. The authors report the result of experiments evaluating their technique.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
6
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
Logic verification using binary decision diagrams in a logic synthesis environment
Sharad Malik, A.R. Wang, Robert K. Brayton et al. · 2003 · 509 citations
LSS: A system for production logic synthesis
John A. Darringer, Daniël Brand, John V. Gerbi et al. · IBM Journal of Research and Development · 1984 · 136 citations