Equivalence Checking of Digital Circuits: Fundamentals, Principles, Methods

ISBN-13: 9781402077258 / Angielski / Twarda / 2004 / 263 str.

Paul Molitor; Janett Mohnke

Opis

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 118] 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. 113]). 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."

Spis treści

Acknowledgements. 1: Introduction. 1. Tasks in verification processes. 2. Equivalence checking. 3. Structure of the book. 4. The audience. Part I: Fundamentals. 2: Preliminaries. 1. Basic notations. 2. Boolean algebra. 3. Boolean functions. 4. Pseudo-Boolean functions. 3: Representation of Functions. 1. Desirable properties of representations. 2. Traditional representations of Boolean functions. 3. Binary decision diagrams. 4. Representations of pseudo-Boolean functions. Part II: Equivalency Checking of Combinational Circuits. 4: Use of Canonical Representations. 1. Synthesizing ROBDDs and *BMDs. 2. Problems arising when using one of these methodologies. 5: SAT and ATPG Based Equivalence Checking. 1. SAT based equivalence checking. 2. ATPG based equivalence checking. 6: Exploiting Similarities. 1. The basic idea. 2. Partitioning the problem into a set of smaller and simpler equivalence checking problems. 3. Using internal equivalences to simplify large miters. 4. Finding internal equivalences. 7: Partial Implementations; Chr. Scholl, B. Becker. 1. Symbolic Z-simulation. 2. Symbolic Zi-simulation. 8: Permutation Independent Boolean Comparison. 1. The problem. 2. Signatures. 3. Examples of signatures. 4. Limits of signatures. 5. Special kinds of G-Symmetries. Part III: Equivalence Checking of Sequential Circuits. 9: Basic Definitions and Algorithms. 1. Finite State Machines and their representations. 2. Equivalence of Finite State Machines. 3. State space traversal. 10: Latch Correspondence Problem. 1. Problem description. 2. Signatures. Index.

O autorze

Paul Molitor ist Professor für Technische Informatik an der Martin-Luther-Universität Halle-Wittenberg. Vor seiner Tätigkeit an der Universität Halle war er Professor für Schaltungstechnik an der Humboldt-Universität zu Berlin (1993/94) bzw. Projektleiter in dem an der Universität des Saarlandes und der Universität Kaiserslautern angegliederten Sonderforschungsbereich 'VLSI Entwurfsmethoden und Parallelität' (1983-92). Er studierte Informatik und Mathematik an der Universität des Saarlandes (Diplom 1982, Promotion 1986, Habilitation 1992).