Definition: A binary lattice data structure that succinctly represents a truth table by collapsing redundant nodes and eliminating unnecessary nodes.
See also OBDD, reduced ordered binary decision diagram.
Note: Randy Bryant's homepage
A BDD is a full binary tree.
Starting with slide 39, Monica Lam shows how a BDD relates to a truth table in Software Design Rules.
Randy E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35(8):677-691, August, 1986.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 17 December 2012.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "BDD", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2012. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bdd.html