Gary D. Hachtel - Böcker

Abstraction Refinement for Large Scale Model Checking summarizes recent research on abstraction techniques for model checking large digital system. Considering both the size of today's digital systems and the capacity of state-of-the-art verification algorithms, abstraction is the only viable solution for the successful application of model checking techniques to industrial-scale designs. This book describes recent research developments in automatic abstraction refinement techniques. The suite of algorithms presented in this book has demonstrated significant improvement over prior art; some of them have already been adopted by the EDA companies in their commercial/in-house verification tools.

This textbook is designed for courses on VLSI Logic Synthesis and Verification, Design Automation, CAD and advanced level discrete mathematics. It also serves as a basic reference work in design automation for both professionals and students. This book is about the theoretical underpinnings of VLSI (Very Large Scale Integrated Circuits). It combines and integrates modern developments in logic synthesis and formal verification with the more traditional matter of Switching and Finite Automata Theory. The book also provides background material on Boolean algebra and discrete mathematics. A unique feature of this text is the large collection of solved problems. Throughout the text the algorithms covered are the subject of one or more problems based on the use of available synthesis programs.

The roots of the project which culminates with the writing of this book can be traced to the work on logic synthesis started in 1979 at the IBM Watson Research Center and at University of California, Berkeley. During the preliminary phases of these projects, the impor­ tance of logic minimization for the synthesis of area and performance effective circuits clearly emerged. In 1980, Richard Newton stirred our interest by pointing out new heuristic algorithms for two-level logic minimization and the potential for improving upon existing approaches. In the summer of 1981, the authors organized and participated in a seminar on logic manipulation at IBM Research. One of the goals of the seminar was to study the literature on logic minimization and to look at heuristic algorithms from a fundamental and comparative point of view. The fruits of this investigation were surprisingly abundant: it was apparent from an initial implementation of recursive logic minimiza­ tion (ESPRESSO-I) that, if we merged our new results into a two-level minimization program, an important step forward in automatic logic synthesis could result. ESPRESSO-II was born and an APL implemen­ tation was created in the summer of 1982. The results of preliminary tests on a fairly large set of industrial examples were good enough to justify the publication of our algorithms. It is hoped that the strength and speed of our minimizer warrant its Italian name, which denotes both express delivery and a specially-brewed black coffee.

The roots of the project which culminates with the writing of this book can be traced to the work on logic synthesis started in 1979 at the IBM Watson Research Center and at University of California, Berkeley. During the preliminary phases of these projects, the impor­ tance of logic minimization for the synthesis of area and performance effective circuits clearly emerged. In 1980, Richard Newton stirred our interest by pointing out new heuristic algorithms for two-level logic minimization and the potential for improving upon existing approaches. In the summer of 1981, the authors organized and participated in a seminar on logic manipulation at IBM Research. One of the goals of the seminar was to study the literature on logic minimization and to look at heuristic algorithms from a fundamental and comparative point of view. The fruits of this investigation were surprisingly abundant: it was apparent from an initial implementation of recursive logic minimiza­ tion (ESPRESSO-I) that, if we merged our new results into a two-level minimization program, an important step forward in automatic logic synthesis could result. ESPRESSO-II was born and an APL implemen­ tation was created in the summer of 1982. The results of preliminary tests on a fairly large set of industrial examples were good enough to justify the publication of our algorithms. It is hoped that the strength and speed of our minimizer warrant its Italian name, which denotes both express delivery and a specially-brewed black coffee.

Logic Synthesis and Verification Algorithms is a textbook designed for courses on VLSI Logic Synthesis and Verification, Design Automation, CAD and advanced level discrete mathematics. Logic Synthesis and Verification Algorithms is about the theoretical underpinnings of VLSI (Very Large Scale Integrated Circuits).