Binary Decision Diagram
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.
Key highlights
- 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
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
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
- 1.Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35(8), 677–691.
- 2.Andersen, H. R. (1997). An introduction to binary decision diagrams. Technical Report, IT University of Copenhagen.
- 3.Becker, B., & Drechsler, R. (1998). Binary Decision Diagrams: Theory and Implementation. Kluwer.ISBN 0792380185
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Binary Decision Diagram. ScholarGate. https://scholargate.app/numerical-methods/binary-decision-diagram