Algorithms and Data Structures in VLSI Design

This textbook provides an introduction to ordered binary decision diagrams (OBDDs), with an emphasis on applications in computer-aided circuit design and formal verification.

**Publication date**: 01 Aug 1998

**ISBN-10**:
3540644865

**ISBN-13**:
9783540644866

**Paperback**:
267 pages

**Views**: 27,051

Algorithms and Data Structures in VLSI Design

This textbook provides an introduction to ordered binary decision diagrams (OBDDs), with an emphasis on applications in computer-aided circuit design and formal verification.

Book Summary:

An interaction has taken place between current research in theoretical computer science and practical applications in the area of VLSI design. This has mainly been initiated by the following two facts. Firstly, chip design without the assistance of computers is no longer conceivable. And secondly, the construction of permanently more powerful chips is reaching the absolute frontiers of current possibilities and capabilities. In 1994, the design error in the Intel Pentium chip with its economical consequences has made particularly aware of these difficulties.

One of the main problems is the huge number of possible combinations of individual chip elements (giving a combinatorial explosion). For such chips, the problem of representing and manipulating the functional behavior of the chip within a computer has already become almost impossible. Here, a fruitful connection with a core topic of theoretical computer science, the design of data structures and efficient algorithms, has been achieved. This connection is established by means of ordered binary decision diagrams (OBDDs), which have led to performance improvements and breakthroughs in many CAD projects all over the world.

This book provides a comprehensive introduction to the foundations of this interdisciplinary research topic and discusses important applications in computer-aided circuit design. It originated from undergraduate and graduate courses at the University of Trier as well as from relevant research projects.

Intended Audience:

On the one hand, the book is directed to students, researchers and lecturers who work or teach in the areas of algorithms, data structures, or VLSI design and are looking for access to the active research field of OBDDs, or are interested in paradigmatic connections between theory and practice. On the other hand, the book is intended to provide a source for all interested CAD engineers, VLSI designers, and users of CAD tools who are looking for a self-contained presentation of OBDD technology, or are interested in questions of modeling and methodology in CAD projects. The general prerequisites for reading the book are only some basic knowledge in computer science and a motivation in studying ideas that make CAD tools work efficiently.

An interaction has taken place between current research in theoretical computer science and practical applications in the area of VLSI design. This has mainly been initiated by the following two facts. Firstly, chip design without the assistance of computers is no longer conceivable. And secondly, the construction of permanently more powerful chips is reaching the absolute frontiers of current possibilities and capabilities. In 1994, the design error in the Intel Pentium chip with its economical consequences has made particularly aware of these difficulties.

One of the main problems is the huge number of possible combinations of individual chip elements (giving a combinatorial explosion). For such chips, the problem of representing and manipulating the functional behavior of the chip within a computer has already become almost impossible. Here, a fruitful connection with a core topic of theoretical computer science, the design of data structures and efficient algorithms, has been achieved. This connection is established by means of ordered binary decision diagrams (OBDDs), which have led to performance improvements and breakthroughs in many CAD projects all over the world.

This book provides a comprehensive introduction to the foundations of this interdisciplinary research topic and discusses important applications in computer-aided circuit design. It originated from undergraduate and graduate courses at the University of Trier as well as from relevant research projects.

Intended Audience:

On the one hand, the book is directed to students, researchers and lecturers who work or teach in the areas of algorithms, data structures, or VLSI design and are looking for access to the active research field of OBDDs, or are interested in paradigmatic connections between theory and practice. On the other hand, the book is intended to provide a source for all interested CAD engineers, VLSI designers, and users of CAD tools who are looking for a self-contained presentation of OBDD technology, or are interested in questions of modeling and methodology in CAD projects. The general prerequisites for reading the book are only some basic knowledge in computer science and a motivation in studying ideas that make CAD tools work efficiently.

Tweet

About The Author(s)

No information is available for this author.

No information is available for this author.

Book Categories

Computer Science
15
Introduction to Computer Science
32
Introduction to Computer Programming
52
Algorithms and Data Structures
25
Artificial Intelligence
24
Computer Vision
30
Machine Learning
6
Neural Networks
22
Game Development and Multimedia
25
Data Communication and Networks
5
Coding Theory
16
Computer Security
9
Information Security
35
Cryptography
3
Information Theory
17
Computer Organization and Architecture
22
Operating Systems
2
Image Processing
11
Parallel Computing
4
Concurrent Programming
24
Relational Database
3
Document-oriented Database
14
Data Mining
16
Big Data
17
Data Science
23
Digital Libraries
22
Compiler Design and Construction
26
Functional Programming
11
Logic Programming
26
Object Oriented Programming
21
Formal Methods
70
Software Engineering
3
Agile Software Development
7
Information Systems
5
Geographic Information System (GIS)

Mathematics
67
Mathematics
14
Algebra
1
Abstract Algebra
27
Linear Algebra
3
Number Theory
8
Numerical Methods
2
Precalculus
10
Calculus
3
Differential Equations
5
Category Theory
11
Proofs
19
Discrete Mathematics
24
Theory of Computation
14
Graph Theory
2
Real Analysis
1
Complex Analysis
15
Probability
47
Statistics
7
Game Theory
5
Queueing Theory
13
Operations Research
16
Computer Aided Mathematics

Supporting Fields
21
Web Design and Development
1
Mobile App Design and Development
28
System Administration
2
Cloud Computing
10
Electric Circuits
6
Embedded System
28
Signal Processing
4
Network Science
3
Project Management

Operating System
Programming/Scripting
6
Ada
13
Assembly
34
C / C++
8
Common Lisp
2
Forth
35
Java
13
JavaScript
1
Lua
15
Microsoft .NET
1
Rexx
12
Perl
6
PHP
68
Python
12
R
1
Rebol
13
Ruby
2
Scheme
3
Tcl/Tk

Miscellaneous