Binary Decision Diagrams:Construction of BDD Based on a Logic Expression

Construction of BDD Based on a Logic Expression

Procedure 29.1 shows a way of constructing compact BDDs from the truth table for a function f of n variables. This procedure, however, is not efficient because the size of its initial BDD is always of the order of 2n, even for a very simple function. To avoid this problem, Bryant [6] presented a method to construct BDDs by applying a sequence of logic operations in a logic expression. Figure 29.7 shows a simple example of constructing a BDD for f = (x2 · x3) ∨ x1. First, trivial BDDs for x2 · x3, and x3 are created in Figure 29.7(a). Next, applying the AND operation between x2 and x3, the BDD for x2 · x3 is then generated. Then, the BDD for the entire expression is obtained as the result of the OR operation between (x2 · x3) and x1. After deleting the nodes that are not on the paths from the root node for f toward the 0- or 1-terminal, the final BDD is shown in Figure 29.7(b).

In the following, we show a formal algorithm for constructing BDDs for an arbitrary logic expression. This algorithm is generally far more efficient than that based on a truth table.

Binary Logic Operation

Suppose we perform a binary operation between two functions, g and h, and this operation is denoted by g ○ h, where “○” is one of OR, AND, Exclusive-OR, and others. Then by the Shannon expansion of a function explained previously, g ○ h can be expanded as follows:

with respect to variable xi, which is the variable of the node that is in the highest level among all the nodes in g and h. This expansion creates the 0- and 1-edges which go to the next two nodes from the node for the variable xi, by operations (g(x =0) ○ h(x =0) ) and (g(x =1) ○ h(x =1) ). The two subgraphs whose roots are these two nodes represent the cofactors derived by the Shannon expansion, (g(x =0)

When BDDs for functions g and h are given, we can derive a new BDD for function f = g ○ h by the following procedure.

Procedure 29.2: Construction of a BDD for Function f ○ h, Given BDDs for g and h.

Given BDDs for functions g and h (e.g., Figure 29.8(a)), let us construct a new BDD (e.g., Figure 29.8(b)) with respect to the specified logic operation g ○ h and then reduce it by the previous Procedure 29.1 (e.g., Figure 29.8(d)).

1. Starting with the root nodes for g and h and going down toward to the 0- or 1-terminal, apply repeatedly steps a and b in the following, considering steps c and d.

a. When the node under consideration, say Na, in one of the two BDDs for g and h is in a higher level than the other node, Nb:

If Na and Nb are for variables xa and xb, respectively, and if the 0-edge from Na for xa = 0 goes to node Na0 and the 1-edge from Na for xa = 1 goes to node Na1, then we create the following two new nodes, to which the 0- and 1-edges go down from the corresponding node N ′a for the variable xa in the new BDD (i.e., N ′a corresponds to this combination of Na and Nb), as a part of the new BDD:

One new node for the operation ○ between Na0 and Nb for xa = 0, and the other new node for the operation ○ between Na1 and Nb for xa = 1.

The variable for the first node, i.e., the node for Na0 ○ Nb will be the one in the higher level of the two nodes, Na0 and Nb, in the BDDs for g and h; and the variable for the second node (i.e., the node for Na1 ○ Nb) will be the one in the higher level of the two nodes, Na1 and Nb, in the BDDs for g and h.

In this case, creation of edges is not considered with respect to Nb in the original BDDs.

For example, suppose binary operation g ○ h is to be performed on the functions g and h in the BDD shown in Figure 29.8(a) and furthermore, “○” is OR in this case. We need to start the OR operation with the root nodes for g and h (i.e., N8 and N7 respectively). N8 is in a higher level than N7. So, in Figure 29.8(b) which explains how to construct the new BDD according to this procedure, we create two new nodes; one for OR(N4, N7) for the 0-edge for x1 = 0 from the node for OR(N8, N7) and the other for OR(N6, N7) for the 1-edge for x1 = 1 from the node for OR(N8, N7), corresponding to this step (a). Thus, we need next to form the OR between N4 and N7 and also the OR between N6 and N7 at these nodes in the second level in Figure 29.8(b). These two nodes are both for variable x2.

For OR(N4, N7), N7 is now in a higher level than N4. So, corresponding to this step (a), we create the new nodes for OR(N4, N2) and also for OR(N4, N5) for 0- and 1-edge, respectively, in the third level in Figure 29.8(b).

b. When the node under consideration, say Na, in one of the BDDs for g and h is in the same level as the other node, Nb. (If Na is for a variables xa, these two nodes are for the same variable xa because both g and h have this variable.):

If the 0-edge from Na for xa = 0 goes to node Na0 and the 1-edge from Na for xa = 1 goes to node Na1, and if the 0-edge from Nb for xb = 0 goes to node Nb0 and the 1-edge from Nb for xb = 1 goes to node Nb1, then we create the following two new nodes, to which the 0- and 1-edges come down from the corresponding node N ′a for the variable xa in the new BDD (i.e., N ′a corresponds to this combination of Na and Nb), as a part of the new BDD:

one new node for the operation ○ between Na0 and Nb0 for xa = 0, and the other new node for the operation ○ between Na1 and Nb1 for xa = 1.

The variable for the first node, i.e., the node for Na0 ○ Nb0 will be the one in the higher level of the two nodes, Na0 and Nb0, in the BDDs for g and h; and the variable for the second node, i.e., the node for Na1 ○ Nb1 will be the one in the higher level of the two nodes, Na1 and Nb1, in the BDDs for g and h.

For the example in Figure 29.8(b), we need to create two new nodes for the operations, OR(N4, N2) and OR(N2, N5) to which the 0- and 1-edges go for x2 = 0 and x2 = 1, respectively, from the node OR(N6, N7) because N6 and N7 are in the same level for variable x2 in Figure 29.8(a). These two nodes are both for variable x3.

c. In the new BDD for the operation g ○ h, we need not have more than one subgraph that represent the same logic function. So, during the construction of the new BDD, whenever a new node (i.e., a root node of a subgraph) is for the same operation as an existing node, we need not continue creation of succeeding nodes from that new node.

For the example, in Figure 29.8(b), the node for operation OR(N4, N2) appears twice, as shown with a dotted arc, and we do not need to continue the creation of new nodes from the second and succeeding nodes for OR(N4, N2). OR(N2, N3) also appears twice, as shown with a dotted arc.

d. In the new BDD for the operation g ○ h, if one of Na and Nb is the 0- or 1-terminal, or Na and Nb are the same, i.e., Na = Nb, then we can apply the logic operation that g ○ h defines. If g ○ h is for AND operation, for example, the node for AND(N1, Na) represents Na because N1 is the 1-terminal in Figure 29.8(a), and furthermore, if Na represents function g, this node represents g.

Also, it is important to notice that only this step (d) is relevant to the logic operation defined by g ○ h, whereas all other steps from (a) through (c) are irrelevant of the logic operation g ○ h.

For the example in Figure 29.8(b), the node for operation OR(N0, N2) represents N2, which is for variable x4. Also, the node for operation OR(N0, N1) represents constant value 1 because N0 and N1 are the 0- and 1-terminals, respectively, and consequently, 0 ∨ 1.

By using binary operation f ⊕ 1, f can be performed and its processing time is linearly proportional to the size of a BDD. However, it is improved to a constant time by using the complement edge, which is discussed in the following. This technique is now commonly used.

2. Convert each node in the new BDD that is constructed in Step 1 to a node with the corresponding variable inside. Then derive the reduced BDD by Procedure 29.1.

For the example, each node for operation OR(Na, Nb) in Figure 29.8(b) is converted to a node with the corresponding variable inside in Figure 29.8(c), which is reduced to the BDD in Figure 29.8(d).

Complement Edges

Complement edge is a technique to reduce computation time and memory requirement of BDDs by using edges that indicates to complement the function of the subgraph pointed to by the edge, as shown in Figure 29.9(a). This idea was first shown by Akers [3] and later discussed by Madre and Billon [18]. The use of complement edges brings the following outstanding merits.

• The BDD size is reduced by up to a half

• Negation can be performed in constant time

• Logic operations are sped by applying the rules, such as Use of complement edges may break the uniqueness of BDDs. Therefore, we have to adopt the two rules, as illustrated in Figure 29.9(b):

1. Using the 0-terminal only.

2. Not using a complement edge as the 0-edge of any node (i.e., use it on 1-edge only). If necessary, the complement edges can be carried over to higher nodes.

Derivation of a Logic Expression from a BDD

A logic expression for f can be easily derived from a BDD for f. A path from the root node for f to the 1-terminal in a BDD is called 1-path, where the values of the variables on the edges on this path make f equal 1. For each 1-path, a product of literals is formed by choosing xi for xi = 1 or its complement, xi for xi = 0. The disjunction of such products for all 1-paths yields a logic expression for f. For example, in Figure 29.8(a), the sequence of nodes, N8-N6-N4-N2-N1, is a 1-path and the values of variables on this path, x1 = 1, x2 = 0, x3 = 1, and x4 = 1, make the value of f (g for this example) equal 1. Finding all 1-paths, a logic expression for f is derived as It is important to notice that logic expressions that are derived from all 1-paths are usually not minimum sums for the given functions.