Algorithms and Data Structures in VLSI Design
OBDD - Foundations and Applications
Published on 19. August 1998
Book
Paperback/Softback
XII, 268 pages
978-3-540-64486-6 (ISBN)
Description
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.
More details
Edition
1998 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Primary & secondary/elementary & high school
Graduate
Illustrations
7 s/w Abbildungen
XII, 268 p. 7 illus.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 16 mm
Weight
429 gr
ISBN-13
978-3-540-64486-6 (9783540644866)
DOI
10.1007/978-3-642-58940-9
Schweitzer Classification
Persons
Prof. Dr. Christoph Meinel war 2004-2023 Direktor des Hasso-Plattner-Instituts und Professor für Internet-Technologien und Systeme an der Universität Potsdam. Er ist Autor, Koautor und Herausgeber von zahlreichen Büchern, Tagungsbänden und Artikeln.Prof. Dr. Martin Mundhenk ist seit 2001 Professor für Informatik an der Friedrich-Schiller-Universität Jena. Er ist dort in Forschung und Lehre für Haupt- und Nebenfach Informatik tätig.
Content
1. Introduction.- 2. Basics.- 2.1 Propositions and Predicates.- 2.2 Sets, Relations, and Functions.- 2.3 Graphs.- 2.4 Algorithms and Data Structures.- 2.5 Complexity of Algorithms.- 2.6 Hashing.- 2.7 Finite Automata and Finite State Machines.- 2.8 References.- I. Data Structures for Switching Functions.- 3. Boolean Functions.- 4. Classical Representations.- 5. Requirements on Data Structures in Formal Circuit Verification.- II. OBDDs: An Efficient Data Structure.- 6. OBDDs - Ordered Binary Decision Diagrams.- 7. Efficient Implementation of OBDDs.- 8. Influence of the Variable Order on the Complexity of OBDDs.- 9. Optimizing the Variable Order.- III. Applications and Extensions.- 10. Analysis of Sequential Systems.- 11. Symbolic Model Checking.- 12. Variants and Extensions of OBDDs.- 13. Transformation Techniques for Optimization.