Automatic Verification of Sequential Circuits Using Temporal Logic (Q3743249)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3976934
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Automatic Verification of Sequential Circuits Using Temporal Logic |
scientific article; zbMATH DE number 3976934 |
Statements
Automatic Verification of Sequential Circuits Using Temporal Logic (English)
0 references
1986
0 references
asynchronous circuits
0 references
hardware verification
0 references
correctness of sequential circuits
0 references
propositional temporal logic
0 references
state-transition graph
0 references
truth of a temporal formula
0 references
0.8624700307846069
0 references
0.846006453037262
0 references
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 modelchecker. 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 exhaustive simulation. The second obtains the state graph by compilation from an HDL specification of the original circuit.
0 references