CMU-CS-85-100
Computer Science Department
School of Computer Science, Carnegie Mellon University

CMU-CS-85-100

Automatic Verification of Sequential Circuits Using Temporal Logic

Michael Browne, Edmund Clarke, David Dill, Bhubaneswar Mishra

December 1984

Unavailable Electronically

Verifying the correctness of sequential circuits has been an important problem for a long time. But lack of any formal and efficient method of verification has prevented the creation of practical design aids for this purpose. Since all the known techniques of simulation and prototype testing are time-consuming and not very reliable, there is an acute need for such tools, In this paper we describe an automatic verification system for sequential circuits in which specifications are expressed in a propositional temporal logic. In contrast to most other mechanical verification systems, our system does not require any user assistance and is quite fast--experimental results show that state machines with several hundred states can be checked for correctness in a matter of seconds!

The verification system uses a simple and efficient algorithm, called a Model Checker . The algorithm works in two steps: in the first step, it builds a labeled state-transition graph; and in the second step, it determines the truth of a temporal formula with respect to the state-transition graph. We discuss two different techniques that we have implemented for automatically generating the state-transition graphs: The first involves extracting the state graph directly from the circuit by simulation. The second obtains the state graph by compilation from an HDL specification of the original circuit. Although these approaches are quite different, we believe that there are situations in which each is useful.

18 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]