Minato S.-I. Binary Decision Diagrams and Applications for VLSI CAD

Kluwer, 1996. — 151 p.Symbolic Boolean manipulation using Binary Decision Diagrams (BDDs) has been applied successfully to a wide variety of tasks, particularly in very large scale integration (VLSI) computer-aided design (CAD). The concept of decision graphs as an abstract representation of Boolean functions dates back to early work by Lee and Akers. In the last ten years, BDDs have found widespread use as a concrete data structure for symbolic Boolean manipulation. With BDDs, functions can be constructed, manipulated, and compared by simple and efficient graph algorithms. Since Boolean functions can represent not just digital circuit functions, but also such mathematical domains as sets and relations, a wide variety of CAD problems can be solved using BDDs.
The state of the art in the use of BDDs for symbolic Boolean manipulation has been advanced by researchers around the world. In particular, the group headed by Prof. Shuzo Yajima at Kyoto University has been the source of many important research results as well. as the spawning ground for some of the most productive researchers. Shin-Ichi Minato is a prime example of this successful research environment. While a Master's student at Kyoto University, he and his colleagues developed important refinements to the BDD data structure, including a shared representation, attributed edges, and improved variable ordering techniques. Since joining the NIT LSI Laboratories, Minato has continued to make important research contributions. Perhaps most significant among these is the use of a zero-suppressed reduction rule when using BDDs to represent sparse sets. These "ZBDDs" have proved effective for such tasks as the cube-set manipulations in two-level logic optimization, as well as for representing polynomial expressions.Techniques of BDD Manipulation
Variable Ordering for BDDs
Representation of Multi-Valued Functions
Generation of Cube Sets from BDDs
Zero-Suppressed BDDs
Multi-Level Logic Synthesis Using ZBDDs
Implicit Manipulation of Polynomials Based on ZBDDs
Arithmetic Boolean Expressions