(data structure)
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: A short bibliography of Binary Decision Diagrams. Randy Bryant's homepage
A BDD is a full binary tree.
Author: PEB
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 22 January 2007.
HTML page formatted Mon Dec 3 13:57:37 2007.
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. 22 January 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bdd.html
