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 E. Black.
Entry modified 17 December 2012.
HTML page formatted Mon Dec 17 09:52:36 2012.
Cite this as:
Paul E. Black, "BDD", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2012. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bdd.html