IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2003 · 29 citations · 14 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureFormal MethodsTheory Of ComputationEquivalence CheckingFinite State Machine ModelingFinite-state MachinesModel CheckingSequential Logic DescriptionVerificationBinary Decision DiagramsCircuit State VariablesFinite State Machine VerificationFormal VerificationRegistersSequential Equivalence CheckingState VariablesState-space Structure
The state-explosion problem limits formal verification on large sequential circuits partly because the sizes of binary decision diagrams (BDDs) sizes heavily depend on the number of variables dealt with. In the worst case, a BDD size grows exponentially with the number of variables. Thus, reducing this number can possibly increase the verification capacity. In particular, this paper shows how sequential equivalence checking can be done in the sum state space. Given two finite state machines M/sub 1/ and M/sub 2/ with numbers of state variables m/sub 1/ and m/sub 2/, respectively, conventional formal methods verify equivalence by traversing the state space of the product machine with m/sub 1/+m/sub 2/ registers. In contrast, this paper introduces a different possibility, based on partitioning the state space defined by a multiplexed machine, which can have merely max{m/sub 1/,m/sub 2/}+1 registers. This substantial reduction in state variables potentially enables the verification of larger instances. Experimental results show the approach can verify benchmarks with up to 312 registers, including all of the control outputs of microprocessor 8085.
14
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
SIS : A System for Sequential Circuit Synthesis
Ellen Sentovich · 1992 · 1.9K citations
Optimizing synchronous systems
Charles E. Leiserson, James B. Saxe · 1981 · 428 citations