Algorithms and data structure in VLSI design. DBDD - foundations and applications

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

Review text

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.

Recommendations

Cited in

(41)

This page was built for publication: Algorithms and data structure in VLSI design. DBDD - foundations and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388806)