Decision Diagram Variants





Decision Diagram Variants

In this section we will study several variants of decision diagrams, all of which are canonical and have efficient manipulation algorithms, such as construction and Boolean operations. Each variant is targeted toward a specific application domain. Therefore, as the application of decision diagrams become more widespread, more variants are sure to come.

Shared BDDs (SBDDs)

Strictly speaking, SBDDs are not a variant of BDDs; rather, they are an application of a BDD to vector Boolean functions. A vector Boolean function has multiple outputs. An example is the next-state function of a finite-state machine having more than one FF. When constructing BDDs for a number of Boolean functions, instead of having a number of isolated BDDs, one for each function, the BDD nodes representing the same functionality are shared. This overall BDD having multiple roots each representing a function is called a shared BDD (or SBDD). The main advantage of an SBDD is compactness through node sharing. An SBDD preserves all the properties of a BDD.

9.

Construct an SBDD for the following functions:


For illustration purposes let's first construct a BDD for each function and then merge their nodes. In practice, BDDs for f and g are constructed simultaneously, and node sharing is a part of the construction process. Choose variable ordering a < b < c. To merge nodes of the same functionality, we start from the leaf nodes and move toward the root. The BDDs for f and g and the SBDD are shown in Figure. The ratio of BDD sizes before and after sharing is 13:9.

Figure. (A) BDD for f. (B) BDD for g (C) SBDD for f and g


Edge-Attributed BDDs

It is simple operation to complement a function: by exchanging the constant nodes in the function's BDD. That is, except for the two constant nodes, the BDD of the function and that of its complement are identical. Being able to share the common structures between the function and its complement can have a drastic effect on overall size, especially for a function with many subfunctions that are complements of each other. One solution to this problem allows BDD edges to carry an attribute that can be an inversion or no inversion. When an edge's attribute is inversion, the function seen at the tail of the edge is the complement of the function at the head of the edge. To denote an inversion attribute, we place a small dot on the edge.

Allowing unconditional placement of inversion attributes on an edge violates canonicity. For instance, the pairs of BDDs in Figure have equivalent functionality, even though they are structurally different. Therefore, we must restrict which edges are allowed to be complemented. For the two equivalent configurations in each pair, we only allow the one with no dot on the 1-edge (in other words, the first configuration). With this restriction, we restore canonicity.

19. (AD) Equivalent-edge attributes


10.

As an example, let's apply edge attributes to the SBDD in FigureC. Recognizing that the two c nodes are complements of each other, we choose to eliminate the c node on the right and redirect its incoming edges to the other c node. Add the inversion attribute to each of the redirected edges (see FigureB). Redistribute the dots to avoid complementation on the 1-edge to preserve canonicity. The resulting BDD is shown in FigureC.

20. SBDD with edge attributes. (A) SBDD without edge attributes (B) Add edge attributes (C) Canonical form with edge attributes


Zero-Suppressed BDDs (ZBDDs)

The two reduction rules for BDD are removing nodes with two edges that point to the same node and merging nodes that represent the same functionality. In ZBDDs, the first reduction rule is replaced by removing nodes with a 1-node that is the constant node 0. As illustrated in Figure, the two transformations for the ZBDD are the following:

  1. Remove the node with a 1-edge that points to constant node 0 and redirect all incoming edges to its 0-node.

  2. Merge nodes that represent the same functionality.

21. ZBDD reduction rules


It can be shown that ZBDDs are canonical. However, ZBDD nodes may exist with both edges that point to the same node. Consequently, a ZBDD has the following interpretation. A path from the root to the constant node 1 represents a cube. If a variable is missing in the path, the variable node's 1-node is constant 0 and therefore the variable is a negative literal in the cube.

Conceptually, a ZBDD can be obtained from a completely unreduced decision diagram by applying the two previous reduction rules. A completely unreduced decision diagram is a graphical representation of the truth table of a function, and hence has exactly 2n paths and 2n leaf nodes, where n is the number of variables, and it can be constructed by applying successive cofactor operations for all variables in the function. Each path represents a minterm, and the value of the leaf node is the value of the function at the minterm. In practice, ZBDDs are not constructed directly from unreduced decision diagrams, but from a procedure that applies the two reduction rules throughout the whole construction process. For more details, please refer to the bibliography.

11.

FigureA shows a completely unreduced decision diagram. From this decision diagram, we can apply the ZBDD reduction rules. First, remove all the c nodes with a 1-edge that points to constant node 0, and redirect their incoming edges to their respective 0-nodes, as in FigureB. Now the left b node has its 1-node as constant 0 and is thus removed, as shown in FigureC. At this point, node a becomes eligible for removal. Getting rid of node a and sharing the constant node 1, we have a reduced ZBDD in FigureC. An ROBDD for the same function is shown in FigureA. Note that the reduced BDD has more nodes and edges. Also note that variable a does not even appear in the ZBDD. Let us try to read the function off the ZBDD. There are two paths to constant node 1. The first path consists of b and c. Because variable a is missing in the path, it is a negative literal in the cube. The cube indicated by the first path is bc. The second path has only variable b; therefore, the two missing variables show up in the cube as negative literals. This cube is . The function is the sum of the two cubes: . The same function can be derived from the BDD.

22. (A) Unreduced decision diagram (B, C) Nodes eliminated via reduction (D) Reduced ZBDD


23. (A, B) Compare ROBDD (A) with ZBDD (B)


Not all functions have ZBDDs smaller than BDDs. Apart from sharing nodes, a ZBDD gets reduced in size by removing nodes with 1-edges that point to 0, whereas BDD reduces from removing nodes with both edges that point to the same node. Therefore, a ZBDD has a smaller size than the BDD of the function if there are more such 1-edge-to-0 nodes than the nodes with both edges that point to the same node, and vice versa. A path in a decision diagram represents a cube. Thus, a path having a 1-edge-to-0 node means the cube has a negative phase of the variable. Therefore, intuitively, a ZBDD is more compact if the function to be represented has a lot more negative literals than positive literals in the minterms of its on set. A minterm of n literals can be interpreted as a selection among the n objects: A positive literal at position i means the ith object is selected; a negative literal, the ith object is not selected. Therefore, a function of n variables, expressed as a disjunction of minterms, represents all acceptable selections. A more compact ZBDD results if there are more negative literals, implying that few objects are selected. With this interpretation, sometimes ZBDDs are said to be compact for sparse representation (in other words, the objects selected are sparse).

Ordered Functional Decision Diagrams (OFDDs)

A BDD is based on the first form of the Shannon cofactoring expansion. It is possible to derive decision diagrams based other expansions. OFDDs are based on positive Davio expansion. Positive and negative Davio expansions are


We will focus our discussion on positive expansion. A function, when expanded with respect to variable x, generates two subfunctions: and , each of which is independent of x. Expansion continues on the subfunctions until all variables are exhausted. The resulting expansion is called the Reed Muller form, which is an XOR sum-of-products term. This expansion of a function can be represented graphically, and the resulting graph is called an OFDD. When expanding about variable x, a node labeled x is created and the 1-edge is pointed to the node of the Boolean difference whereas the 0-edge is pointed to the node of the cofactor, as shown in FigureA. If the cofactor or the Boolean difference is not a constant, the expansion continues.

Figure. OFDD from Davio expansion. (A) Edge semantics of an OFDD node (B) An OFDD for f = z xy


Conversely, given an OFDD, the represented function is derived by ANDing the node variable with its 1-node and XORing with its 0-node, as in FigureB, starting from the leaf nodes and ending at the root. Each path from the root to a leaf node represents a cube. Based on the semantics of an OFDD node, if a path takes the 1-edge of a node, the node variable is included in the cube. If the 0-edge is taken, the variable is not included. Therefore, to obtain a function from an OFDD, enumerate all paths from the root to the constant 1-node. Then generate the cubes for the paths. Finally, XOR all the cubes.

Two reduction rules for OFDDs are the same as those for ZBDDs:

  1. If a node's 1-edge points to constant 0, remove the node and redirect its incoming edges to its 0-node.

  2. Merge nodes that have the same child nodes.

Rule 1 follows directly the expansion f = g xh; if the 1-node is constant 0 (in other words, h = 0, then f = g), meaning that the incoming edges directly point to the 0-node. Rule 2 combines isomorphic nodes.

12.

Expand the following function using positive Davio expansion and create an OFDD:


Choose variable ordering a < b < c < d.


Now the remaining subfunctions are constants, so we stop. The resulting expansion is as follows and the OFDD is shown in FigureA:


Now apply the reduction rules to simplify the OFDD. The reduced OFDD is shown in FigureB. Note that the d node has both edges pointing to the same node, yet the node remains in the OFDD.

As a check, let us derive the Reed Muller form from the OFDD. There are six paths from the root to constant node 1. For each path, the node variable is included in the cube if the path takes the 1-edge of the node. For the path shown FigureB, because only the 1-edge of node c is taken, the path gives cube c. The other five paths give cubes abc, acd, ac, bc, and bcd. The function is the XORing of the cubes


which is equal to the original function, as expected.

Figure. OFDD of (A) An OFDD (B) The reduced OFDD


Pseudo Boolean Functions and Decision Diagrams

Thus far, the Boolean domain is implied in our study. It is interesting to explore decision diagrams in other domains to see whether advantages such as representation size can be achieved. In this section we will briefly study several decision diagrams for functions that have either or both non-Boolean domain or range. These decision diagrams are extensions from the binary domain to the integer/real domain, and they have found application in specific design and analysis areas.

A generalization of a BDD is to relax the values a variable can take from binary to any set of numbers. Thus, a node can have more than two outgoing edges and each edge is labeled with the value the variable assumes. This decision diagram is called a multivalue decision diagram (MDD). An application of MDDs is to represent a design at an early stage when signals are in symbolic form as opposed to encoded binary form. For instance, the input variables to the function can be control signals with permissible values WAIT, SYNC, ACK, ABORT, ERR, and REQ.

For a multivalue function f: Mk -> M, where M = {1, ..., n} (in other words, f has k variables each of which can have a value between 1 and n), an MDD for f is a DAG with n leaf nodes. The leaf nodes are labeled as 1, ..., n. Each internal node is labeled with a variable and has n outgoing edges. Each edge is labeled with a value between 1 and n. Along any path from the root to a leaf node, a variable is traversed (at most) once. The semantics of an MDD is that a path from the root to a leaf node represents an evaluation of the function. Along the path, if a node takes on value v, the edge labeled v is followed to the next node. When a leaf node labeled i is reached, the function evaluates to i.

An ordered MDD conforms to a variable ordering such that variables along any path are consistent with the ordering. A reduced MDD satisfies the following two conditions: (1) no node exists with all of its outgoing edges pointing to the same node, and (2) no isomorphic subgraphs exist. Like a BDD, a reduced ordered MDD is canonical and has a suite of manipulation operations associated with it. Furthermore, several multivalue functions can be merged and represented as a shared MDD.

13.

Consider a robot controller equipped with three one-dimensional coordinate sensors. Each sensor has three possible outputs: 1, 2, and 3. The output of the controller is 1, 2, and 3, denoting stop, continue, and turn respectively. Let x, y, and z denote the output of the three sensors respectively. The controller's behavior is described in Figure. A reduced ordered MDD for the controller is shown in Figure.

Figure A Multivalue Function f: M3->M

(x,y,z)

f(x,y,z)

(1, 1, -)

1

(1, 2, z)

z

(1, 3, -)

2

(2, 1, -)

1

(2, 2, -)

2

(2, 3, z)

z

(3, -, z)

z


26. An example MDD


An algebraic decision diagram (ADD) represents a function with a domain that is Boolean but with a range that is real: f: Bn -> R. An ADD differs from a BDD only in the number of leaf nodes. An ADD has a number of leaf nodes equal to the number of possible output values of the function it represents. A reduced ordered ADD has the same variable ordering and reduction rules as in a BDD. The semantics of ADD nodes are the same as those of BDD nodes. One application of an ADD is in the area of timing analysis. For instance, the function gives the power consumption or delay of a circuit based the circuit input values. Figure illustrates such an application.

14.

In this example we will look at an application of an ADD in representing static leakage power of circuit. Assume that the leakage power of a gate is one unit if the gate's output is 0, and is 2 otherwise. We can use an ADD to represent all leakage power behavior of the circuit in Figure. Let's choose variable ordering a < b < c. First we calculate the power for all inputs. The results are tabulated in Figure. The result is translated into an ADD (FigureB), and a reduced ADD is shown in FigureC. Maximum power occurs when the input vectors are 101 or 001. Minimum power is consumed when the input is 01-.

27. (A) A circuit for leakage power representation (B) ADD of leakage power (C) Reduced ADD


Power Leakage Results

Input (abc)

Power

Input (abc)

Power

000

5

001

7

010

4

011

4

100

5

101

7

110

5

111

6


Binary Moment Diagram (BMD)

An interesting way to look at Boolean variables is to treat them as integer variables restricted to 0 and 1. TRUTH value is denoted by x and FALSE is denoted by 1 - x. When applying BMD to a function mapping from Bn to R, the inputs to the function can be conveniently expressed as "cubes." For instance, referring to Figure, the first entry, 000 giving 5, can be expressed as 5(1 - a)(1 -b)(1 - c), which is 5 only if a = b = c = 0 as required. Using this technique and by adding up the "cubes," a function from Bn to R can be expressed as a polynomial. The function in Figure has polynomial


A BMD represents the coefficients of the polynomial in leaf nodes. Nonterminal nodes have the interpretation that if the 1-edge (left) is taken, the variable of the node is included; otherwise, the variable is excluded. The path from the root to a leaf node represents a term in the polynomial by multiplying the value of the leaf node and all included variables along the path. Then the function is the sum of the terms represented by all paths. This interpretation is similar to that of OFDDs, which, instead of summation, XORs all cubes. A BMD for the leakage power function is in Figure. The two paths shown produce the terms ab and -b. The left path takes 1-edge of node a and node b, and 0-edge of node c; thus, variables a and b are included. Furthermore, the leaf node value is 1. Multiplying the variables with the leaf node value gives the term ab. Similarly, the right path takes the 0-edge of node a and node c, and the 1-edge of node b. The leaf node value is -1. Therefore, the term is -b.

28. (A) A BMD for leakage power function (B) A reduced BMD


The two reduction rules for BMDs are the same as those for OFDDs. That is, first, if the 1-edge of a node points to 0, the node is removed and its incoming edges are redirected to its 0-node. And second, all isomorphic subgraphs are shared. The first rule follows from the multiplicative action of the node variable on the 1-edge. If the 1-edge points to 0, the node variable is zeroed and only the 0-node is left. Therefore, all incoming edges can be redirected to the 0-node. Applying these reduction rules to FigureA, we obtain the reduced BMD in FigureB.

A further generalization of BMDs allows edges to carry weight. As a path is traversed, the included variables, the weights on the traversed edges, and the leaf node value are multiplied to produce a term. This generalization gives more freedom to distribute the coefficients, and results in more isomorphic subgraphs for sharing, producing more compact representations. With proper restrictions on subgraph transformations, these generalized BMDs can be reduced to be canonical. For more information, consult the citations in the bibliography.


     Python   SQL   Java   php   Perl 
     game development   web development   internet   *nix   graphics   hardware 
     telecommunications   C++ 
     Flash   Active Directory   Windows