| Binary Decision Diagram |
Article Index for Binary |
Shopping Diagram |
Website Links For Binary |
Information AboutBinary Decision Diagram |
| CATEGORIES ABOUT BINARY DECISION DIAGRAM | |
| data structures | |
| trees structure | |
| diagrams | |
|
which consists of decision nodes and two terminal nodes called 0-terminal and 1-terminal. Each decision node is labeled by a Boolean variable and has two Child Node s called low child and high child. The edge from a node to a low (high) child represents an assignment of the variable to 0 (1). Such graph is called BDD if the variables occur in the same ordering on all paths and it is reduced according to two rules:
A path from the root node to the 1-terminal represents a variable assignment for which the represented Boolean function is true. If the path descends to a low child (high child) from a node, then the node's variable is assigned to 0 (1). Strictly spoken, the notion BDD stands for ''Shared Reduced Ordered Binary Decision Diagram'' (also ROBDD in the literature). EXAMPLE The left figure below 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, a dotted (solid) line represents an edge to a low (high) child. 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 left figure can be transformed into a binary decision ''diagram'', if it is maximally reduced according to the two reduction rules. The resulting BDD is shown in the right figure. HISTORY The basic idea from which the data structure was created is the Shannon extension. A switching function is split into two sub-functions (cofactors) by assigning one variable (cf. ''if-then-else normal form''). If such a sub-function is considered as sub-tree, it can be represented by a ''binary decision tree''. Binary decision diagrams (BDD) were introduced by Lee (Lee 1959), and further studied and made known by Akers (Akers 1978). The full potential for efficient algorithms based on the data structure was investigated by 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 (Bryant 1986, Bryant 1992). By extending the sharing to several BDDs, i.e. one sub-graph is used by several BDDs, the data structure ''Shared Reduced Ordered Binary Decision Diagram'' is defined (Brace, Rudell, Bryant 1990). The notion of a BDD is now generally used to refer to that particular data structure. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. In difference to other compressions, the actual operations are performed on that compressed representation, without decompression. VARIABLE ORDERING The size of a BDD may vary between a linear to an exponential range depending upon the ordering of the variables. Simply put, if we have a boolean function then depending upon the ordering of the variables we would end up getting a graph whose number of nodes would be linear at the best and exponential at the worst case. Let us consider the Boolean function . Using the variable ordering , the BDD needs nodes to represent the function. Using the ordering , the BDD consists of nodes. 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 and Wegener 1996 . For any constant c>1 it is even NP-hard to compute a variable ordering resulting in an OBDD with a size that is at most c times larger than an optimal one 2002 . However there exist efficient heuristics to tackle the problem. There are functions for which the graph size is always exponential — independent of variable ordering. This holds e. g. for the multiplication function (an indication as to the apparent complexity of Factoring ). Researchers have of late suggested refinements on the BDD data structure giving way to a number of related graphs - BMD ( Binary Moment Diagrams ), ZDD ( Zero Suppressed Decision Diagram ) etc. SEE ALSO IMPLEMENTATIONS
REFERENCES
EXTERNAL LINKS
|
|
|