In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression.

Similar data structures include negation normal form (NNF), Zhegalkin polynomials, and propositional directed acyclic graphs (PDAG).

Definition

A Boolean function can be represented as a rooted, directed, acyclic graph, which consists of several (decision) nodes and two terminal nodes. The two terminal nodes are labeled 0 (FALSE) and 1 (TRUE). Each (decision) node <math>u</math> is labeled by a Boolean variable <math>x_i</math> and has two child nodes called low child and high child. The edge from node <math>u</math> to a low (or high) child represents an assignment of the value FALSE (or TRUE, respectively) to variable <math>x_i</math>. Such a BDD is called 'ordered' if different variables appear in the same order on all paths from the root. A BDD is said to be 'reduced' if the following two rules have been applied to its graph:

  • Merge any isomorphic subgraphs.
  • Eliminate any node whose two children are isomorphic.

In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD in the literature, used when the ordering and reduction aspects need to be emphasized). The advantage of an ROBDD is that it is canonical (unique up to isomorphism) for a particular function and variable order. The full potential for efficient algorithms based on the data structure was investigated by Randal Bryant at Carnegie Mellon University: his key extensions were to use a fixed variable ordering (for canonical representation) and shared sub-graphs (for compression). Applying these two concepts results in an efficient data structure and algorithms for the representation of sets and relations.

Variable ordering

The size of the BDD is determined both by the function being represented and by the chosen ordering of the variables. There exist Boolean functions <math>f(x_1,\ldots, x_{n})</math> for which depending upon the ordering of the variables we would end up getting a graph whose number of nodes would be linear (in&nbsp;n) at best and exponential at worst (e.g., a ripple carry adder). Consider the Boolean function <math>f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \cdots + x_{2n-1}x_{2n}.</math> Using the variable ordering <math>x_1 < x_3 < \cdots < x_{2n-1} < x_2 < x_4 < \cdots < x_{2n}</math>, the BDD needs <math>2^{n+1}</math> nodes to represent the function. Using the ordering <math>x_1 < x_2 < x_3 < x_4 < \cdots < x_{2n-1} < x_{2n}</math>, the BDD consists of <math>2n+2</math> nodes.

{| align="center"

|-

| thumb|638px|BDD for the function ƒ(x<sub>1</sub>, ..., x<sub>8</sub>) = x<sub>1</sub>x<sub>2</sub> + x<sub>3</sub>x<sub>4</sub> + x<sub>5</sub>x<sub>6</sub> + x<sub>7</sub>x<sub>8</sub> using bad variable ordering

| thumb|156px|Good variable ordering

|}

It is of crucial importance to care about variable ordering when applying this data structure in practice. The problem of finding the best variable ordering is NP-hard.

Researchers have suggested refinements on the BDD data structure giving way to a number of related graphs, such as:

  • BMD (binary moment diagrams),
  • ZDD (zero-suppressed decision diagrams),
  • FBDD (free binary decision diagrams), where any path from the root to a leaf node reads every variable at most once. Any OBDD is a FBDD.
  • FDD (functional decision diagrams),
  • MDD (multiple-valued decision diagrams), which generalize BDDs by allowing decision variables to take more than two values,
  • PDD (parity decision diagrams),
  • MTBDD (multiple-terminal BDDs),
  • TDD (ternary decision diagrams), where an "unknown" branch is added to make consecutive union/disjunction operations lazy, avoiding exponential size growth.
  • NDD (network decision diagrams),

Logical operations on BDDs

Many logical operations on BDDs can be implemented by polynomial-time graph manipulation algorithms:

Further reading

  • Complete textbook available for download.
  • Fun With Binary Decision Diagrams (BDDs), lecture by Donald Knuth
  • List of BDD software libraries for several programming languages.