BDD

(data structure)

Definition: A binary lattice data structure that succinctly represents a truth table by collapsing redundant nodes and eliminating unnecessary nodes.

Note: A short bibliography of Binary Decision Diagrams. Randy Bryant's homepage

A BDD is a full binary tree.

More information

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.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Fri Oct 28 09:42:30 2005.
HTML page formatted Fri Oct 28 09:46:03 2005.

Cite this as:
"BDD", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/bdd.html