Binary Decision Diagrams and Applications for VLSI CAD

This text discusses Symbolic Boolean manipulation, which, using binary decision diagrams (BDDs), has been successfully applied 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 the early work by Lee and Akers. Since the mid-1980s, 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.