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:
- ADDs (algebraic decision diagrams) [Bahar et al., ICCAD93]
- asynchronous circuit synthesis [Lin et al., ICCAD94]
- BCP (binate covering problem) solver [Jeong et al., ICCAD92]
- BDDs for implicit set representation in combinatorial problems [Minato, DAC93] and applications to polynomial algebra [Minato, IWLS95]
- efficiency improvements through dynamic variable reordering ([Rudell, ICCAD93], [Panda et al., ICCAD94]) and breadth-first manipulations [Ashar et al., ICCAD94]
- exact and approximate FSM traversal techniques ([Coudert et al., IFIP Workshop on Applied Formal Methods, 1989, and ICCD90], [Touati et al., ICCAD90], [Cho et al., DAC93])
- formal verification of arithmetic circuits ([Bryant et al., DAC95][Kimura, DAC95])
- ILP solver based on edge-valued BDDs [Pedram et al., ICCAD93]
- implicit prime generation and two-level minimization ([Coudert et al., DAC92], [Coudert et al., DAC93], [Coudert, Integration, Oct. 1994]),
- matrix representation using MTBDDs [Clarke et al., IWLS93]
- MDDs (multi-valued decision diagrams) [T. Kam's M.S. Thesis, UC Berkeley, 1990]
- OKFDDs (ordered Kronecker functional decision diagrams) [Drechsler et al., DAC94]
- parallel algorithm for BDD construction [Kimura et al., ICCD90]
- symbolic synthesis techniques [B. Lin's Ph.D. Thesis, UC Berkeley, 1991]
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!
- [Aker78]
- S. B. Akers, "Binary Decision Diagrams", IEEE Transactions on Computers, vol. c-27, no. 6, June 1978.
- [Brya86]
- R.E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, vol. c-35, no.8, Aug. 1986.
- [BrRB90]
- K.S. Brace, R.L. Rudell, and R.E. Bryant, "Efficient Implementation of a BDD package", Proc. 27th Design Automation Conference, 1990.
- [Brya92]
- R. E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys, vol.24, no.3, Sep. 1992.