What Is a Binary Decision Diagram (BDD)?

A Binary Decision Diagram (BDD) is a specialized data structure used in computer science and digital circuit design to efficiently represent, manipulate, and evaluate Boolean functions. By translating truth tables and algebraic expressions into a directed acyclic graph, a BDD maps binary inputs directly to binary outputs through conditional decision paths. When structured under strict variable ordering and reduction rules—known as a Reduced Ordered Binary Decision Diagram (ROBDD)—it achieves a strictly canonical form, meaning any given Boolean function corresponds to one unique diagram. This article explains the fundamental structure of BDDs, how they utilize binary logic paths based on Shannon’s expansion theorem, and how canonical representations are formed and applied.

The Structure of a Binary Decision Diagram

A standard BDD is a directed acyclic graph (DAG) made up of two types of nodes:

  1. Decision Nodes (Internal Nodes): Each node represents an input variable of the Boolean function. From every internal node, exactly two directed edges emerge:
    • The Low Edge (or 0-branch): Followed when the variable evaluates to 0 (False). This is typically rendered as a dashed line.
    • The High Edge (or 1-branch): Followed when the variable evaluates to 1 (True). This is typically rendered as a solid line.
  2. Terminal Nodes (Leaf Nodes): These are sink nodes representing the final evaluation of the function, labeled either 0 or 1.

Evaluating a Boolean expression using a BDD involves traversing the graph from the single root node down to a terminal node based on the binary assignment of each input variable.

Binary Representation and Shannon’s Expansion

BDDs fundamentally operate on Shannon’s Expansion Theorem, which decomposes any Boolean function \(f(x_1, x_2, \dots, x_n)\) around a single variable \(x_i\):

\[f = (\neg x_i \land f_{x_i=0}) \lor (x_i \land f_{x_i=1})\]

In this formulation: * \(f_{x_i=0}\) (the cofactor) is the simplified function when \(x_i\) is 0. * \(f_{x_i=1}\) is the cofactor when \(x_i\) is 1.

Every internal node in a BDD represents this exact choice. The binary number system directly dictates the evaluation path: a binary vector input (such as \((x_1, x_2, x_3) = (1, 0, 1)\)) defines a deterministic step-by-step route from the root to the resulting binary output (0 or 1).

Canonical Representation via ROBDDs

Standard BDDs can vary widely in shape and size for the same Boolean function. To make the representation canonical—meaning that identical Boolean functions are guaranteed to have identical graph structures—two critical constraints are applied to create a Reduced Ordered Binary Decision Diagram (ROBDD).

1. Fixed Variable Ordering (Ordered BDD)

Variables must appear in the exact same sequence along every path from the root to the terminal nodes. For example, if the defined order is \(x_1 < x_2 < x_3\), a path cannot evaluate \(x_2\) before \(x_1\).

2. Reduction Rules (Reduced BDD)

The graph is systematically simplified using two reduction rules: * Node Sharing (Elimination of Isomorphic Subgraphs): If two distinct nodes have the same variable label and their corresponding 0-branches and 1-branches point to the same respective child nodes, one node is eliminated, and all incoming edges are redirected to the remaining node. * Redundant Node Elimination: If both the 0-branch and the 1-branch of a node point to the exact same child node, the decision at that variable does not affect the output. The node is removed, and incoming edges bypass it directly to the child.

Once a variable order is fixed and the graph is fully reduced, Bryant’s theorem guarantees that the ROBDD is canonical.

Key Advantages of Canonical BDDs