Algorithms and Data Structures in VLSI Design: OBDD — Foundations and Applications

✍ Scribed by Prof. Dr. Christoph Meinel, Dr. Thorsten Theobald (auth.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1998
• Tongue: English
• Leaves: 270
• Edition: 1
• Category: Library

✦ Synopsis

One of the main problems in chip design is the huge number of possible combinations of individual chip elements, leading to a combinatorial explosion as chips become more complex. New key results in theoretical computer science and in the design of data structures and efficient algorithms can be applied fruitfully here. The application of ordered binary decision diagrams (OBDDs) has led to dramatic performance improvements in many computer-aided design projects. This textbook provides an introduction to the foundations of this interdisciplinary research area with an emphasis on applications in computer-aided circuit design and formal verification.

✦ Table of Contents

Front Matter....Pages I-XI
Introduction....Pages 1-6
Basics....Pages 7-22
Front Matter....Pages 23-23
Boolean Functions....Pages 25-49
Classical Representations....Pages 51-76
Requirements on Data Structures in Formal Circuit Verification....Pages 77-86
Front Matter....Pages 87-87
OBDDs — Ordered Binary Decision Diagrams....Pages 89-103
Efficient Implementation of OBDDs....Pages 105-122
Influence of the Variable Order on the Complexity of OBDDs....Pages 123-144
Optimizing the Variable Order....Pages 145-170
Front Matter....Pages 171-171
Analysis of Sequential Systems....Pages 173-197
Symbolic Model Checking....Pages 199-209
Variants and Extensions of OBDDs....Pages 211-234
Transformation Techniques for Optimization....Pages 235-255
Back Matter....Pages 257-267

✦ Subjects

Processor Architectures; Algorithm Analysis and Problem Complexity; Computer Hardware