Symbolic Model Checking for Sequential Circuit Verification
Abstract
The temporal logic model checking algorithm of Clarke, Emerson, and Sistla 17 is modified to represent state graphs using binary decision diagrams (BDDs) 7 and partitioned transition relations (10, 11). Because this representation captures some of the regularity in the state space of circuits with data path logic, we are able to verify circuits with an extremely large number of states. We demonstrate this new technique on a synchronous pipelined design with approximately 5 x 10(120) states. Our model checking algorithm handles full CTL with fairness constraints. Consequently, we are able to express a number of important liveliness and fairness properties, which would otherwise not be expressible in CTL. We give empirical results on the performance of the algorithm applied to both synchronous and asynchronous circuits with data path logic.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 15, 1993
- Accession Number
- ADA274375
Entities
People
- D. E. Long
- D. L. Dill
- E. M. Clarke
- J. R. Burch
- K. L. Mcmillan
Organizations
- Carnegie Mellon University