Binary Decision Diagram
Binary Decision Diagram (BDD) · Also known as: BDD, reduced BDD, ordered BDD
Binary Decision Diagrams (BDDs) are a canonical, memory-efficient representation of Boolean functions developed by Randal Bryant in 1986. A BDD is a directed acyclic graph encoding all variable assignments and results; reduced BDDs are unique for each function and enable efficient manipulation of combinatorial logic in model checking, circuit design, and symbolic computation.
Read the full method
Sign in with a free account to read this section.
When to use it
Use BDDs for Boolean satisfiability (SAT), model checking finite-state systems, combinatorial circuit verification, and symbolic state-space exploration. Effective when function has locality or structure; avoid for highly irregular functions (worst-case exponential size). Modern SAT solvers often use BDDs internally for specific subproblems.
Strengths & limitations
- Canonical representation: each Boolean function has unique reduced BDD (given variable ordering), enabling efficient equality checking
- Compact storage: many practical functions have polynomial BDD size despite exponential variables
- Efficient operations: Boolean operations (AND, OR, NOT, quantification) execute in O(|BDD₁| × |BDD₂|) time
- Complete algorithm: systematically explores state space; can prove unreachability and deadlock freedom
- Variable ordering is critical: poor ordering can cause exponential size blow-up; finding optimal order is NP-hard
- Memory explosion: adversarially chosen functions (e.g., middle-bit function) have inherently exponential BDD size
- Not suitable for arithmetic: integer arithmetic requires Boolean representation of operations, leading to huge BDDs
- Debugging difficulty: BDD size changes are unpredictable; reordering heuristics are problem-specific
Frequently asked
What is variable ordering and why does it matter so much?
Variable ordering is the sequence in which variables are tested from root to terminal (e.g., x₁, x₂, x₃, …). The same function can have BDD size 10 for order A but size 10^6 for order B. Dynamic reordering (Sift) greedily swaps adjacent variables to minimize size; heuristics like grouping related variables help.
What is the reduction step in BDD construction?
After expanding f = (¬x ∧ f₀) ∨ (x ∧ f₁), merge redundant nodes: if two nodes have identical children, combine them. Also remove duplicate nodes (same variable, same children). Merging aggressively shrinks the graph while preserving function semantics.
How do I perform Boolean operations (AND, OR) on two BDDs?
Recursive algorithm: AND(BDD₁, BDD₂) traverses both graphs simultaneously, returning terminal 1 only if both paths reach 1, else 0. Memoize subproblems to avoid redundant recursion. Time is O(|BDD₁| × |BDD₂|); result size varies with input structure.
When is BDD size intractable and what are alternatives?
Functions like 'middle bit' (parity-like) have exponential BDD size. Alternatives: ZDDs (zero-suppressed), SAT solvers (avoid explicit structure), SMT solvers with bit-vector theory, or domain-specific tools. Hybrid approaches (BDD for structure, SAT for arithmetic) often succeed where pure BDD fails.
Sources
- Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35(8), 677–691. DOI: 10.1109/TC.1986.1676819 ↗
- Andersen, H. R. (1997). An introduction to binary decision diagrams. Technical Report, IT University of Copenhagen. link ↗
- Becker, B., & Drechsler, R. (1998). Binary Decision Diagrams: Theory and Implementation. Kluwer. ISBN: 0792380185
How to cite this page
ScholarGate. (2026, June 3). Binary Decision Diagram (BDD). ScholarGate. https://scholargate.app/en/numerical-methods/binary-decision-diagram