Binary Decision Diagrams

Binary Decision Diagrams (BDDs) are one of the biggest breakthroughs in CAD in the last decade. BDDs are a canonical and efficient way to represent and manipulate Boolean functions and have been successfully used in numerous CAD applications. Although the basic idea has been around for more than 30 years (see, for example, [Aker78]), it was Bryant who described a canonical BDD representation [Brya86] and efficient implementation algorithms [BrRB90]. Ref. [Brya92] is a very readable introduction to BDD representations and applications.

BDDs are a very active research area. Some interesting, recent developments include:

BDD variable ordering problem has been discussed in: [Malik et al., ICCAD88], [Friedman et al., IEEE Trans. Comp., May 1990], [Liaw et al., IEEE Trans. Comp., June 1992], [Fujita et al., IEEE Trans. CAD/ICAS, Jan. 1993]...

The above lists are by no means complete!


S. B. Akers, "Binary Decision Diagrams", IEEE Transactions on Computers, vol. c-27, no. 6, June 1978.
R.E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, vol. c-35, no.8, Aug. 1986.
K.S. Brace, R.L. Rudell, and R.E. Bryant, "Efficient Implementation of a BDD package", Proc. 27th Design Automation Conference, 1990.
R. E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys, vol.24, no.3, Sep. 1992.