Equivalence Checking of Digital Circuits

1. Front Matter

   Pages i-xiii

   PDF

2. Introduction

   Pages 1-6

3. Fundamentals

   1. Preliminaries

      Pages 9-22

   2. Representation of Boolean and Pseudo Boolean Functions

      Pages 23-65

4. Equivalence Checking of Combinational Circuits

   1. Use of Canonical Data Structures

      Pages 71-97

   2. SAT and ATPG Based Equivalence Checking

      Pages 99-130

   3. Exploiting Similarities

      Pages 131-143

   4. Checking Equivalence for Partial Implementations

      • Bernd Becker, Christoph Scholl

      Pages 145-167

   5. Permutation Independent Boolean Comparison

      Pages 169-204

5. Equivalence Checking of Sequential Circuits

   1. Formal Basics

      Pages 209-226

   2. The Latch Correspondence Problem

      Pages 227-239

6. Back Matter

   Pages 243-263

   PDF

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.

• Hardware
• Simulation
• VLSI
• algorithms
• complexity
• integrated circuit
• logic
• model
• production
• security
• statistics

• Martin-luther-University Halle-Wittenberg, Germany

  Paul Molitor

• DResearch Digital Media Systems GmbH, Germany

  Janett Mohnke

• University Freiburg, Germany

  Bernd Becker

• University Heidelberg, Germany

  Christoph Scholl

Policies and ethics