×

Algorithms and data structure in VLSI design. DBDD - foundations and applications. (Algorithmen und Datenstrukturen im VLSI-Design. DBDD - Grundlagen und Anwendungen.) (German) Zbl 0899.68040

Berlin: Springer. xiii, 283 p. (1998).
Assume the Boolean variables \(a,b,c, \dots\) are combined to form a Boolean expression. Arbitrarily designate \(a\) as variable 1, \(b\) as variable 2, \(c\) as variable \(3, \dots\) Place \(a\) at the root of a binary tree; place \(b\) at the two successor nodes of node \(a\), place \(c\) at the successor nodes of nodes \(b, \dots\) For a Boolean expression with \(n\) variables, this representation gives rise to a complete binary tree with \(2^n-1\) internal nodes. Successor nodes at level \(n+1\) are leaf nodes of the complete binary tree and have the value 1 to represent “True”, 0 to represent “False”.
To construct a binary decision diagram (BDD), arbitrarily designate the left branch from an internal node as the “True” branch, the right branch as the “False” branch. A Boolean expression involving the variables \(a,b,c, \dots\) is represented by assigning a leaf node with value 0 or 1 based on the value obtained by traversing the path from the root node to the leaf. For example, all leaf nodes of the Boolean expression \(a+b +c\) except the right most leaf node are assigned the value 1; the right most node of the tree is assigned the value 0. Placing an order on the variables as they are assigned to the levels of the three gives rise to an ordered binary decision diagram (OBDD).
This representation is exponential in the number of variables in the expression (if each bit of a 32 bit or 64 bit operand is a Boolean variable, the representation becomes unmanageable.) For OBDDs to be useful in practical applications, it is necessary to reduce the complete binary trees to “tall, skinny” trees. In general, multiple OBDDs exist for a Boolean expression. The ordering of nodes, i.e. the selection of the variable associated with the root node, its successor variable, etc., generally has considerable affect on the form of the resulting OBDD. From the \(n!\) different variable orderings, the problem is to select an ordering that gives rise to an OBDD representation that is “reasonable” in some sense.
The book consists of an extensive introduction, detailed sections on OBDDs, sections on applications and literature references. Time and space complexities are presented as are reduction algorithms and heuristics for optimizing variable order. Algorithms exist to reduce complete OBDDs both in height and breadth. Heuristics exist to help select a node ordering. Canonical forms exist for basic Boolean expressions. Circuits consisting of many Boolean expressions may be reduced and/or verified by OBDD algorithms.

MSC:

68W35 Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68P15 Database theory
68P05 Data structures
68W10 Parallel algorithms in computer science
68M99 Computer system organization
PDFBibTeX XMLCite