Formal verification has become one of the most important steps in circuit design. Since circuits can contain several million transistors, verification of such large designs becomes more and more difficult. Pure simulation cannot guarantee the correct behavior and exhaustive simulation is often impossible. However, many designs, like ALUs, have very regular structures that can be easily described at a higher level of abstraction. For example, describing (and verifying) an integer multiplier at the bit-level is very difficult, while the verification becomes easy when the outputs are grouped to build a bit-string. Recently, several approaches for formal circuit verification have been proposed that make use of these regularities. These approaches are based on Word-Level Decision Diagrams (WLDDs) which are graph-based representations of functions (similar to BDDs) that allow for the representation of functions with a Boolean range and an integer domain. Formal Verification of Circuits is devoted to the discussion of recent developments in the field of decision diagram-based formal verification. Firstly, different types of decision diagrams (including WLDDs) are introduced and theoretical properties are discussed that give further insight into the data structure. Secondly, implementation and minimization concepts are presented. Applications to arithmetic circuit verification and verification of designs specified by hardware description languages are described to show how WLDDs work in practice. Formal Verification of Circuits is intended for CAD developers and researchers as well as designers using modern verification tools. It will help people working with formal verification (in industry or academia) to keep informed about recent developments in this area.
Symbolic Simulation Methods for Industrial Formal Verification contains two distinct, but related, approaches to the verification problem. Both are based on symbolic simulation. The first approach is applied at the gate level and has been successful in verifying sub-circuits of industrial microprocessors with tens and even hundreds of thousands of gates. The second approach is applied at a high-level of abstraction and is used for high-level descriptions of designs. Historically, it has been difficult to apply formal verification methods developed in academia to the verification problems encountered in commercial design projects. This book describes new ideas that enable the use of formal methods, specifically symbolic simulation, in validating commercial hardware designs of remarkable complexity. These ideas are demonstrated on circuits with many thousands of latches-much larger circuits than those previously formally verified. The book contains three main topics: Self consistency, a technique for deriving a formal specification of design behavior from the design itself; The use of the parametric representation to encode predicates as functional vectors for symbolic simulation, an important step in addressing the state-explosion problem; Incremental flushing, a method used to verify high-level descriptions of out-of-order execution. Symbolic Simulation Methods for Industrial Formal Verification concludes with work on verification of simplified models of out-of-order processors.
A Step-by-Step Guide to Verification of Digital Systems This practical book provides a step-by-step, interactive introduction to formal verification of systems and circuits. The book offers theoretical background and introduces the application of three powerful verification toolsets: LOTOS-based CADP, Petri nets–based PETRIFY, and CCS-based CWB. The book covers verification of modular asynchronous circuits, alternating-bit protocols, arbiters, pipeline controllers, up-down counters, and phase converters, as well as many other verification examples. Using the given detailed examples, exercises, and easy-to-follow tutorials, complete with the downloadable toolsets available via referenced Web sites, this book serves as an ideal text in advanced undergraduate and graduate courses in computer science and electrical engineering. It is also valuable as a desktop reference for practicing verification engineers who are interested in verifying that designed digital systems meet specifications and requirements.
These lecture notes contain an overview of an exciting new field of research, formal methods which give the VLSI designer a firm foundation and useful tools for developing integrated circuits. Such methods allow the possibility of systematic verification in the early phases of the design process. By verifying high level descriptions of the design before concerning themselves with low level details, designers can avoid wasting time implementing circuits that would later be discarded. Obviously it can be very expensive to locate and correct errors found in the later stages of a project, especially if correcting these errors requires extensive, global changes to the design. Furthermore, the long turn-around time for circuit fabrication makes it attractive to use techniques which uncover errors at an early phase of the design. The summer school where these lectures were given was held in Denmark in June 1990, and consisted of six series of lectures, each presenting a distinct formal method.
We develop an algorithm for verifying multiplier circuits using this structure. Finally, we present a form of deterministic finite automaton, the n-DFA, whose transitions are labeled with boolean functions. Using this structure, we develop an algorithm for the problem of sequential logic verification. For each of these algorithms -- to do BDD minimization, multiplier verification, and verification of sequential circuits --we report the running times of actual implementations and compare them to benchmarks in order to demonstrate the practicality of our methods."
This book is a solid foundation of the most important formalisms used for specification and verification of reactive systems. In particular, the text presents all important results on m-calculus, w-automata, and temporal logics, shows the relationships between these formalisms and describes state-of-the-art verification procedures for them. It also discusses advantages and disadvantages of these formalisms, and shows up their strengths and weaknesses. Most results are given with detailed proofs, so that the presentation is almost self-contained. Includes all definitions without relying on other material Proves all theorems in detail Presents detailed algorithms in pseudo-code for verification as well as translations to other formalisms
This book focuses on an Integrated Design Validation (IDV) system that provides a framework for design validation and takes advantage of current technology in the areas of simulation and formal verification resulting in a practical validation engine with reasonable runtime. After surveying the basic principles of formal verification and simulation, this book describes the IDV approach to integrated circuit functional validation. Table of Contents: Introduction / Formal Methods Background / Simulation Approaches / Integrated Design Validation System / Conclusion and Summary
As the number of transistors per unit chip area increases, the power dissipation of the chip becomes a bottleneck. New nano-technology materials have been proposed as viable alternatives to CMOS to tackle area and power issues. The power consumption can be minimized by the use of reversible logic instead of conventional combinational circuits. Theoretically, reversible circuits do not consume any power (or consume minimal power) when performing computations. This is achieved by avoiding information loss across the circuit. However, use of reversible circuits to implement digital logic requires development of new Electronic Design Automation techniques. Several approaches have been proposed and each method has its own pros and cons. This often results in multiple designs for the same function. Consequently, this demands research in efficient equivalence checking techniques for reversible circuits. This thesis explores the optimization and equivalence checking of reversible circuits. Most of the existing synthesis techniques work in two steps -- generate an original, often sub-optimal, implementation for the circuit followed optimization of this design. This work proposes the use of Binary Decision Diagrams for optimization of reversible circuits. The proposed technique identifies repeated gate (trivial) as well as non-contiguous redundancies in a reversible circuit. Construction of a BDD for a sub-circuit (obtained by sliding a window of fixed size over the circuit) identifies redundant gates based upon the redundant variables in the BDD. This method was unsuccessful in identifying any additional redundancies in benchmark circuits; however, hidden non-contiguous redundancies were consistently identified for a family of randomly generated reversible circuits. As of now, several research groups focus upon efficient synthesis of reversible circuits. However, little work has been done in identification of redundant gates in existing designs and the proposed peephole optimization method stands among the few known techniques. This method fails to identify redundancies in a few cases indicating the complexity of the problem and the need for further research in this area. Even for simple logical functions, multiple circuit representations exist which exhibit a large variation in the total number of gates and circuit structure. It may be advantageous to have multiple implementations to provide flexibility in choice of implementation process but it is necessary to validate the functional equivalence of each such design. Equivalence checking for reversible circuits has been researched to some extent and a few pre-processing techniques have been proposed prior to this work. One such technique involves the use of Reversible Miter circuits followed by SAT-solvers to ascertain equivalence. The second half of this work focuses upon the application of the proposed reduction technique to Reversible Miter circuits as a pre-processing step to improve the efficiency of the subsequent SAT-based equivalence checking.
Hardware veri?cation is the process of checking whether a design conforms to its speci?cations of functionality and timing. In today’s design processes it becomes more and more important. Very large scale integrated (VLSI) circuits and the resulting digital systems have conquered a place in almost all areas of our life, even in security sensitive applications. Complex digital systems control airplanes, have been used in banks and on intensive-care units. Hence, the demand for error-free designs is more important than ever. In addition, economic reasons underline this demand as well. The design and production process of present day VLSI-circuits is highly time- and cost-intensive. Mo- over, it is nearly impossible to repair integrated circuits. Thus, it is desirable to detect design errors early in the design process and not just after producing the prototype chip. All these facts are re?ected by developing and prod- tion statistics of present day companies. For example, In?neon Technologies  assumed that about 60% to 80% of the overall design time was spent for veri?cation in 2000. Other sources cite the 3-to-1 head count ratio between veri?cation engineers and logic designers. This shows that verifying logical correctness of the design of hardware systems is a major gate to the problem of time-to-market (cf. ). With the chip complexity constantly increasing, the dif?culty as well as the - portance of functional veri?cation of new product designs has been increased. It is not only more important to get error-free designs.
The most widely used technique for checking the correctness of digital circuits designs is simulation. As the complexity of digital circuits has continued to grow, however, circuit designers have become unable to perform complete simulations of their integrated circuits. Formal hardware verification provides an alternative approach, performing a series of mathematical proofs in order to show that the construction of the circuit from its submodules will result in the intended overall circuit behavior. Papers by Barrow in 1983 and 1984 discuss a PROLOG-based hierarchical formal circuit verification system named VERIFY. AFIT VERIFY, a simple, experimental reverse-engineered version of Barrow's VERIFY system, was produced by Captain Kevin Sparks in 1991. Since that time, a new user interface has been added to the AFIT VERIFY system, as well as the capability to maintain a central repository of standard, previously verified parts. This thesis provides a detailed description of these and other improvements that have been made to Sparks's AFIT VERIFY system.
This book provides readers with a comprehensive introduction to the formal verification of hardware and software. World-leading experts from the domain of formal proof techniques show the latest developments starting from electronic system level (ESL) descriptions down to the register transfer level (RTL). The authors demonstrate at different abstraction layers how formal methods can help to ensure functional correctness. Coverage includes the latest academic research results, as well as descriptions of industrial tools and case studies.