NIST defines Binary Decision Diagram (BDD) as “A binary lattice data structure that succinctly represents a truth table by collapsing redundant nodes and eliminating unnecessary nodes.”
A BDD (Bryant 1986) 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. A BDD represents a Boolean function as a rooted directed acyclic graph (DAG), which consists of several decision nodes and terminal nodes. Many logical operations on BDDs can be performed such as conjunction (Logical AND operation), disjunction (OR Operation) and negation (NOT Operation).
The term BDD mostly 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) for a particular function and variable order. This property makes it useful in functional equivalence checking and other operations like functional technology mapping.
Applications of BDDs
BDDs are mainly used in Computer-aided design software for logic synthesis. BDDs are also sued in model checking, web applications and product configuration software such as Auto Configuration and computer/laptop configuration. These data structures are also used in private information retrieval.
Building binary trees (decision diagrams) increases the possibility of smaller and thus more optimal decision trees:
Binary Decision Diagram Example
The figure above shows a binary decision tree (the reduction rules are not applied), and a truth table, each representing the function f (x1, x2, x3). In the tree on the left, the value of the function can be determined for a given variable assignment by following a path down the graph to a terminal. In the figures below, dotted lines represent edges to a low child (0), while solid lines represent edges to a high child (1). Therefore, to find (x1=0, x2=1, x3=1), begin at x1, traverse down the dotted line to x2 (since x1 has an assignment to 0), then down two solid lines (since x2 and x3 each have an assignment to one). This leads to the terminal 1, which is the value of f (x1=0, x2=1, x3=1).
The binary decision tree of the figure above can be transformed into a binary decision diagram by maximally reducing it according to the two reduction rules. The resulting BDD is shown in the figure as below.
There are many other advance data structures you can use in solving your complex problems. For example, Trie data structure is mainly used for sorting. Binary Trees are mainly used for searching and sorting as they provide a means to store data hierarchically.
