Once Boolean functions are represented using BDDs, Boolean operations are translated into BDD manipulations. In this section we will study algorithms for constructing BDDs from a Boolean function and a circuit, and for computing various Boolean operations using BDDs.

Construction

Construction algorithms build a BDD for a function or circuit. The first question is whether any Boolean function has a BDD representation. The answer is affirmative because a BDD can be constructed for any function based on the Shannon cofactor theorem. According to the cofactor theorem, any function can be expressed as . Therefore, we can create a BDD with node x with a 1-edge that points to f_x and a 0-edge that points to , and then recur the procedure on f_x and until the function is a constant, as demonstrated in Example 8.3.

Example 8.3

Construct a BDD for . Let’s choose variable ordering a < b < c. First we compute cofactors of f with respect to variable a. f_a and f_ā are equal to and (bc) respectively. Thus, . Create node a and point its edges to f_a and f_ā. Repeat the same procedure for the two cofactors: is cofactored as ; thus, f_ab = 1 and . Create node b and point its two edges to and f_ab. The other cofactor, bc, is cofactored as b(c); thus, and . Create another node b and point its edges to and f_āb. Function c is . Create another node b and point its edges to 0 and 1. The BDDs for these cofactors are shown in Figure 8.7A. Connecting all these BDDs together, we have a BDD in Figure 8.7B. The cofactors are labeled in the BDD to illustrate the relationship between cofactor functions and BDD nodes. Then we apply the merge and eliminate transformations on the BDD to derive an ROBDD, as shown in Figure 8.7C.

Figure 8.7. Constructing BDDs using Shannon cofactoring. (A) BDD nodes and Shannon cofactors. (B) Connect BDD nodes. (C) Reduce BDD.

The major drawback of this method is the exponential number of operations. For the first variable, two cofactor functions are created. For the next variable, four cofactor functions are created, and so on. In general, 2ⁿ cofactor functions are created for n variables. In practice, BDDs are built from the bottom up, starting from variables or primary inputs of a circuit. As the building process progresses, a dynamic programming technique keeps track of the intermediate functions being built and returns the result if an intermediate function has already been built. This reuse strategy cuts down runtime substantially.

Let’s look at the bottom-up construction process. Then we will see how dynamic programming helps to reduce runtime. From the start, BDDs are built for the variables, then for simple expressions made of the variables, followed by more complex expressions made of the simple expressions, until the function is completed.

Example 8.4

To build a BDD for f = ((ab + c)(ad + ef) + bdf) + bce, BDDs are built for a, b, c, d, e, and f. There are six operations in this step. Then, based on the BDDs for the variables, BDDs are constructed for these simple functions: ab, ad, ef, bdf, and bce. To construct these BDDs, the BDDs for the variables are ANDed together. For now, let’s defer the study of ANDing and other Boolean operations of BDDs to a later section. There are seven ANDing operations in this step. Next, BDDs are created for (ab + c) and (ad + ef), which comprise two ORing operations of BDDs—namely, ORing of BDD of ab with BDD of c, and ORing of BDD of ab with BDD of ef. Finally, combining the clauses, BDDs are constructed for ((ab + c)(ad + ef) + bdf) and ((ab + c)(ad + ef) + bdf) + bce. Three operations are in this final step. There are a total of 18 operations, and each operation is of polynomial complexity in the number of BDD nodes. Compare this number of operations with 2⁶ = 64 operations using the cofactoring method. In the section on Boolean operations, we will get into the details of using dynamic programming in computing Boolean operations of BDDs.

If BDDs are built from a circuit, BDDs for the primary inputs are constructed first, followed by the BDDs for the intermediate nodes, and finishing with BDDs for the primary outputs. The progression resembles the previous bottom-up method for Boolean functions. Consider the circuit in Figure 8.8. The sequence of BDD construction follows alphabetical order. The rule is that a circuit node is ready for BDD construction if the BDDs of all its fanins have already been constructed.

Figure 8.8. A circuit for illustrating the BDD building sequence

The complexity of BDD construction in general depends on variable ordering. However, there are functions with BDD sizes that are exponential for any variable ordering. In practice, however, many functions have polynomial sizes for some variable orderings. We will revisit the issue of variable ordering in a later section.

Restriction

Restriction operation on a function sets certain variables to specific values. For example, restricting x to 0 and y to 1 in produces . This operation can be easily done on BDDs. To restrict variable v to 1, simply redirect all incoming edges to BDD nodes labeled v to their 1-nodes. Similarly, restricting v to 0 redirects all incoming edges to the 0-nodes. After the edges are redirected, it is possible that redundant nodes and equivalent nodes may appear. Thus, the reduction operation is called to reduce the BDD. The BDD nodes labeled v still exist in the BDD, but they have no incoming edges. To clean up, successively remove all nodes, except the root, that have no incoming edges.

Example 8.5

Restrict the BDD in Figure 8.9A to c = 0, d = 1, and reduce it. Redirect all incoming edges to nodes labeled c to their 0-nodes (see Figure 8.9B). The redirected edges are darker than the other edges. Now redirect all incoming edges to the d node to its 1-node (see Figure 8.9C). Now, the right b node and a node are redundant, because both their edges point to the same node. Apply the reduction operation to remove them. Finally, all nodes but the root are removed that do not have any incoming edges; nodes c and d are removed. The resulting reduced BDD is shown in Figure 8.9D.

Figure 8.9. Restriction operation on a BDD. (A) Original BDD (B) Restriction to c = 0 (C) Restriction to d = 1 (D) Reduced BDD

Boolean operations

When functions are represented by BDDs, operations on the functions translate into operations on BDDs. For example, f AND g becomes BDD(f) AND BDD(g). Here we examine various operations on BDDs. First we encounter the ITE (if–then–else) operator on Boolean functions A, B, and C: ITE(A, B, C) = AB + ĀC. Note that the function represented by a BDD node, say x, is a special case of an ITE operation; the function of the node can be written as ITE(x, function at 1-node, function at 0-node). The ITE operator notation also has the added convenience of relating to BDD nodes. For example, ITE(x, y, z), where x, y, and z are BDD nodes, simply represents BDD node x with its 1-edge pointing to node y and its 0-edge pointing to node z. The ITE operator encompasses all unary and binary operators. Table 8.1 lists some common Boolean operators and their corresponding ITE representations.

Table 8.1. ITE Operator Representation of Boolean Operators

Operator	ITE form
	ITE(X,0,1)
XY	ITE(X,Y,0)
X+Y	ITE(X,1,Y)
X ⊕ Y
MUX(X,Y,Z)	ITE(X,Y,Z)
composition, f(x,g(x))	ITE(g(x),f(x,1),f(x,0))
∃xf(x)	ITE(f(1),1,f(0))
∀xf(x)	ITE(f(1),f(0),0)

The complementation operation, , simply switches the 0 and 1 constant nodes. Composition of Boolean functions substitutes a variable in a function with another function and can be computed as follows. Composing f(x,y) with y = g(x), giving f(x, g(x)), is equivalent to f(x,1) when g(x) = 1 and f(x,0) when g(x) = 0. Symbolically,

which is ITE(g(x),f(x,1),f(x,0)). The existential and universal quantification operators are

which consist of restriction, and OR and AND operations. The existential quantification ∃xf(x) = f(1) + f(0) has the interpretation that there exists a value of x such that f(x) holds. Because x is binary, either f(0) or f(1) must hold. In other words, ∃xf(x) = f(1) + f(0). Similarly, the universal quantification means that for all values of x, f(x) holds. That is, f(0) and f(1) must hold; hence, ∀xf(x) = f(1) · f(0).

Therefore, once we have an algorithm to perform ITE operations on BDDs, we can perform any unary and binary Boolean operations on BDDs. The key to ITE operations is based on the following identity:

which shows that the problem can be reduced to a smaller problem by cofactoring with respect to a variable, and it lends itself to a recursive algorithm. When calls to ITE(A_x, B_x, C_x) and ITE(, , ) return, a BDD node x is created and its two edges are pointed to ITE(A_x, B_x, C_x) and ITE(, , ). The recursion stops when it reaches a terminal case for which the ITE operation is trivial. The terminal cases are the ITEs that are equal to either constants, one of its operands, or complement one of its operands. For example, these are terminal cases: ITE(1,X,Y), ITE(0,Y,X), ITE(X,1,0), ITE(Y,X,X), all of which are equal to X, and ITE(1, 1, Y), ITE(0, Y, 1), ITE(X, 1, 1), all of which are equal to 1.

This recursive operation is shown in Figure 8.10. The triangles are input BDDs of functions A, B, and C. Figure 8.10A is operation ITE(root(A), root(B), root(C)), where we use notation root(A) to emphasize that the operand is the root node of BDD A. The first variable x selected for cofactoring is the earliest ordered root variable of A, B, and C. Figure 8.10B depicts the situation after one recursive call: A BDD node for variable x is created and two ITE calls are invoked on the 1-node and 0-node of the root of BDD A, B, and C; that is, the two recursive calls are as follows, the operands of the ITE operator being BDD nodes: ITE(root(A_x), root(B_x), root(C_x)) and ITE(root(), root(), root()).

Figure 8.10. Recursive algorithm for computing the ITE operator. (A) Before an ITE call (B) After an ITE call on variable x

Directly using the cofactoring identity would generate an exponential number of subfunctions. To curb the exponential growth, dynamic programming is used to remember what subfunctions have been operated on. If there is a match, the result is returned immediately. A computed table stores results of computed ITEs and the results are indexed by their operands. A match is found if all the operands of a pending ITE operation match the operands of an entry in the computed table. In this case, the pending ITE operation terminates and returns with the result found in the table. Let us compute how many distinct entries are possible in a computed table. Because each operand in an ITE is a BDD node, there are only |A| · |B| · |C| possible combinations of operands. Therefore, at most |A| · |B| · |C| ITE operations are required, compared with 2ⁿ, where n is the number of variables. Hence, the complexity of BDD operations is O(|A| · |B| · |C|).

The previous algorithm will create BDDs that may not be reduced. Thus, we must modify the ITE procedure to include the merge and eliminate transformation so that the resulting BDDs are canonical. To incorporate the merge transformation, a unique table remembers all unique BDDs that have already been created, which are indexed by keys consisting of the node variable and its 1-node and 0-node. When calls of ITE(A_x, B_x, C_x) and ITE(, , ) return, and before ITE(A,B,C) = (x, ITE(A_x, B_x, C_x), ITE(, , )) is created, we first check the unique table for an entry with a key of node x, and with a 1-node and 0-node that are ITE(A_x, B_x, C_x) and ITE(, , ) respectively. If such an entry exists, the node found in the table is used. This extra checking step in effect does the merge transformation.

Second, to incorporate the eliminate transformation, we need to check whether the then node is identical to the else node. For example, ITE(A_x, B_x, C_x) = ITE(, , ). If they are, no new node will be created. Instead, either ITE(A_x, B_x, C_x) or ITE(, , ) is returned. This step eliminates redundant nodes. If neither of these two checks succeeds, a new node x is created and its edges are pointed to ITE(A_x, B_x, C_x) and ITE(, , ). Example 8.6 illustrates the ITE operations, dynamic programming, and merge and eliminate transformation embedding.

Example 8.6

In this example, we want to OR the two BDDs shown in Figure 8.11. The operation is ITE(X, 1, Y). For the convenience of referring to the nodes of the BDDs, we number the nodes. To refer to a node, we use notation, BDD_name.node_number, for instance, node c of BDD X is X.4.

To select the first variable for cofactoring, we examine the root nodes of both BDDs and select the one with an earlier ordering. In this case, both roots are the same, node a. Select variable a as the first cofactoring variable. The cofactors of a in BDD X are the BDDs rooted at X.2 and X.3. Similarly, the cofactors of a in BDD Y are the BDDs rooted at Y.2 and Y.3. Using the ITE cofactoring identity, we have

The algorithm recurs on ITE(X.3, 1, Y.3). Cofactoring variable b, ITE(X.3, 1, Y.3) = (b, ITE(X.4, 1, Y.3), ITE(X.6, 1, Y.3)). Here, the Y.3 root node is c and hence it remains the same in the cofactoring of b. At this step, because X.6 = 0, we have reached a terminal case—namely, ITE(X.6, 1, Y.3) = Y.3. Thus, the BDD rooted at Y.3 is returned as the result of ITE(X.6, 1, Y.3), and is entered into the compute and unique tables. The index for Y.3 in the compute table is (X.6, 1, Y.3), the operands of the ITE operator. Recur on the then component, ITE(X.4, 1, Y.3).

Before (c, 1, 0) is created, we need to consult the unique table and find a match, which is Y.3. Therefore, Y.3 is returned as the result for ITE(X.4, 1, Y.3). Now Y.3 indexed (X.4, 1, Y.3) is entered into the compute table. At this step we return from ITE(X.3, 1, Y.3) = (b, Y.3, Y.3). Because the two edges point to the same node, no BDD node is created; instead, Y.3 is returned as the result for ITE(X.3, 1, Y.3). Y.3 indexed (X.3, 1, Y.3) is entered into the compute table.

The other branch of recursion is ITE(X.2, 1, Y.2)). ITE(X.2, 1, Y.2) = (b, ITE(X.5, 1, Y.5), ITE(X.6, 1, Y.3)). Select ITE(X.5, 1, Y.5) for recursion, which is equal to ITE(1, 1, 0) = 1, a terminal case. Thus, ITE(X.5, 1, Y.5) returns 1 and is entered into the compute table. Next, recur on ITE(X.6, 1, Y.3). Because ITE(X.6, 1, Y.3) = ITE(0, 1, Y.3) = Y.3, a terminal case, we consult the unique table and find Y.3 there. Thus, Y.3 is returned as the result of ITE(X.6, 1, Y.3). Returning from ITE(X.2, 1, Y.2) = (b, ITE(X.5, 1, Y.5), ITE(X.6, 1, Y.3)), we have ITE(b, 1, Y.3). Because ITE(b, 1, Y.3) is not yet in the unique table, we create BBD node b with its 1-node pointing to constant node 1 and its 0-node pointing to Y.3. This new node is entered into the unique and compute tables. Let us call this node N1.

Returning from the top-level recursion ITE(X, 1, Y) = (a, ITE(X.2, 1, Y.2), ITE(X.3, 1, Y.3)), we have ITE(X, 1, Y) = (a, N1, Y.3). This is the resulting BDD. Figure 8.12A shows the ITE recursions and Figure 8.12B shows the final BDD. Notice how the embedded merge and eliminate transformations produced a reduced BDD at the end.

To verify the result, BDD X represents Boolean function ab + ābc, and BDD Y, . ORing the two functions gives

The BDD in Figure 8.12B represents ab + c.

Figure 8.11. Operant BDDs for ITE operation

Figure 8.12. Intermediate and final result from BDD ITE operations (A) BDD created by ITE operations (B) Reduced BDD

The ITE algorithm is summarized here:

Boolean Operations on BDDs: ITE(A, B, C)

Input: Three BDDs, A, B, and C.

Output: ROBDD representing ITE(A, B, C).

1. If ITE(A, B, C) is a terminal case, return with result.

2. If ITE(A, B, C) is in the computed table, return with result.

3. Select the root variable x that is ordered earliest.

4. Compute BDD₀ = ITE(, , ) and BDD₁ = ITE(A_x, B_x, C_x).

5. If (BDD₀ = BDD₁), return BDD₀.

6. If (x, root of BDD₁, root of BDD₀) is in the unique table, return the existing node.

7. Create BDD node x with 0-edge and 1-edge pointing to BDD₀ and BDD₁ respectively.

So far in our discussion of BDDs, we have assumed an arbitrary variable ordering. Different variable orderings can cause drastic differences in BDD size Example 8.7 dramatizes the effect and sheds some insight into what makes a variable ordering good.

Figure 8.13. Impact of variable ordering on BDD size. (A) BDD with variable ordering a₁, a₂, b₁, b₂, c₁, c₂ (B) BDD with variable ordering a₁, b₁, c₁, a₂, b₂, c₂

The following two observations provide insight into what makes up a good variable ordering. First, the “width” of a BDD, crudely defined as the number of paths from root to the constant nodes, is determined by the “height” of the BDD, which is the average number of variable nodes along paths, because each variable node branches to two paths. Thus, the more nodes there are on a path, the more branches do the nodes produce, and the wider the BDD. The size of a BDD is proportional to the product of the width and height; hence, the height determines the BDD size. Roughly speaking, the larger the average number of variable nodes along the paths, the bigger the BDD size. Now let’s relate variable ordering to the number of variable nodes along paths. The variable nodes on a path represent the minimum knowledge about the variables such that the value of the function is determined. Therefore, the less knowledge required to know about variables to determine the function’s value, the smaller the BDD size. Hence, a good variable ordering should have the property that, as variables are evaluated one by one in the order, the function value is decided with the fewest number of variables the sooner a function’s value is decided, the fewer variable nodes are on the paths.

Second, node sharing reduces BDD size. Let node v be shared by two paths. Let us call the variables ordered before v the predecessors, and the variables ordered after v the successors. The portions of the two paths from the root to v correspond to two sets of values assigned to the predecessors. The fact that the two paths share node v implies that the valuation of the function by variable v and its successors is independent of the two assigned values to the predecessors. Hence, the more independent the successors and predecessors are in a variable ordering, the more sharing that occurs and thus the smaller the resulting BDD. In other words, a good variable ordering groups interdependent variables closer together.

Deriving a variable ordering from circuits also follows these two principles but manifests slightly differently and uses the circuit structure to select the variables. The key is to arrange the variables such that as evaluation proceeds in the order, the function simplifies as quickly as possible and is as much independent of the already assigned values as possible. Many heuristics exist. An example heuristic is to level the gates from the primary output (the level of a gate being the shortest distance to the output and the distance being the number of gates in between) and order the inputs in increasing level number. The rationale is that variables closer to the output have a better chance of deciding the value of the circuit and hence create BDD paths with fewer nodes. In addition, order the primary input variables such that the intermediate node values are determined as soon as possible. The idea lies in the hope that when intermediate node values are determined, the circuit simplifies.

Figure 8.14. A sample circuit for variable ordering

When composing or computing an operation on several Boolean functions, each of which has its own good ordering, a question arises about how to derive a good ordering for the resulting BDD based on the orderings of the operands. A heuristic is to interleave variable orderings to form an initial overall ordering. For example, if operand 1 has variable ordering a, b, c, d, and operand 2 has x, y, z, then an interleaved ordering is a, x, b, y, c, z, d. How variables are interleaved also depends on the specific operators. After an initial overall ordering is obtained, dynamic algorithms can be used throughout the computing process to adjust the variable ordering to minimize the sizes of intermediate BDDs. Dynamic variable ordering is discussed next.

Dynamic Variable Ordering

So far, the discussion on ordering assumes that an ordering algorithm calculates an ordering of the variables involved in a Boolean computation beforehand and the ordering is used throughout the computation of the functions. Such an ordering algorithm is called static. When a function f is composed with another function g and the result is then operated with yet another function h, a method based on static ordering would first calculate a variable ordering for the variables in f, g, and h, and then use the ordering throughout these two operations. However, a better strategy is to choose a good variable ordering for each of the operations, as opposed to one ordering for all operations. Even during the process of computing a single operation, oftentimes BDD size varies over the entire computational process and peaks in the middle of the process. Therefore, it is difficult to predict an optimal or good ordering for the entire computing process. In fact, an optimal algorithm may have to change variable ordering during the computing process. A dynamic variable ordering algorithm changes the variable ordering as the BDD size approaches a threshold, and usually makes local and incremental adjustments. A typical application of a dynamic algorithm is to build a BDD with a variable ordering derived from a static algorithm, then use a dynamic algorithm to modify the ordering to improve the BDD size during subsequent computations. A requirement for dynamic algorithms is that they must have minimal computational cost so that their use, instead of finding a new ordering using a static algorithm, is justified.

A simple dynamic ordering algorithm is based on the repetitive application of the swap operation, which exchanges the position of two adjacent variables. Referring to Figure 8.15A, variable x is ordered ahead of y and we want to reverse their order. To swap variable x with y, the labels of the nodes are exchanged and the inner two nodes, b and c, are swapped. This swap operation preserves the functionality of the BDD, because for all possible values of x and y, the same child nodes (a, b, c, d) are reached in each case. For example, x = 1, y = 0 reaches node b before and after the swap. After swapping, a reduce operation may be required to maintain local canonicity, as is the case in Figure 8.15B. Therefore, we conclude that a swap operation has a low computational cost and can be done locally.

Figure 8.15. Swap two adjacent BDD variables. (A) Swap operation. (B) Swap operation followed by a reduce operation.

Any variable ordering can be obtained from an initial ordering through multiple swap operations, and thus, in theory, the optimal ordering can be achieved from an initial ordering using only swap operations. However, in practice, there is no known guidance for selecting variables for swapping for optimal ordering, except for exploring all permutations. Therefore, a greedy algorithm is often used with the swap operation. A sifting algorithm moves a selected variable to all possible positions and chooses the one with the smallest BDD size. For example, suppose the current variable ordering is a < b < c < d < e. Sifting variable d produces the five orderings shown in Table 8.2. In this example, the ordering a < d < b < c < e gives the smallest BDD and thus is kept. Sifting a single variable may be regarded as searching along the variable’s axis. Sifting multiple variables simultaneously explores more space and may produce a better result.

Table 8.2. Sifting Variable d

Operation	Variable Ordering	BDD Size
Sift right	a,b,c,e,d	121
Original	a,b,c,d,e	133
Sift left	a,b,d,c,e	118
Sift left	a,d,b,c,e	117
Sift left	d,a,b,c,d	127

Functions and BDD Sizes

Variable ordering algorithms are only useful for the functions that have a good ordering. There are functions that always have BDD sizes exponential in the number of input variables for any variable ordering. A well-known such function is the multiplication function. Specifically, let x₁, ..., x_n and y₁, ..., y_n be the Boolean variables of two multiplicands, and z₁, ...,z_2n, those of the result—that is, (z_2n, ..., z₁) = multiply(x_n, ... x₁, y_n, ..., y₁). The output functions of 3-bit multiplication are illustrated in Figure 8.16. Variable c_i is the carry from output bits before the ith bit. For example, c₃ is 1 only if the two product terms in z₂ are both 1. In other words, c₃ = x₁x₂y₁y₂ and z₃ = x₁y₃ + x₂y₂ + x₃y₁ + c₃. Then, at least one output bit function, z_i, has a BDD of size at least 2^n/8 for any ordering of x₁, ..., x_n, y₁, ..., y_n.

Figure 8.16. Output functions of a 3-bit multiplier

At the other extreme, there are functions with BDDs that are always of polynomial size with respect to any variable ordering. Because symmetric functions are invariant to variable interchanges, their BDD sizes are independent of variable ordering. Recall that a symmetric function is 1 if and only if there is a set of integers, {a₁, ..., a_k}, such that the number of 1s in the inputs is one of the integers. A symmetric function is completely specified by the set of integers. This fact leads to a universal implementation of symmetric functions. This implementation first adds up all input bits. The result is the number of 1s in the inputs. This result is connected to a multiplexor select line, which selects a 1 if the select value is one of the integers in the symmetric function. Figure 8.17 shows the universal implementation of symmetric function with integer set {a₁, ..., a_k}. This configuration of adder and multiplexor has a polynomial-size BDD. Therefore, all symmetric functions have polynomial BDD sizes for any ordering.

Figure 8.17. A universal implementation of symmetric functions

Unlike these two extreme cases, many functions are sensitive to variable ordering, and their BDDs can change from polynomial size to exponential size and vice versa. A practical and interesting property is how easy it is to find a variable ordering that yields a BDD of reasonable size.

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.

Example 8.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 8.18. The ratio of BDD sizes before and after sharing is 13:9.

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

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 8.19 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.

Figure 8.19. (A–D) Equivalent-edge attributes

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

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 8.21, the two transformations for the ZBDD are the following:

Figure 8.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 2ⁿ paths and 2ⁿ 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.

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

Figure 8.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).

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 Figure 8.24A. If the cofactor or the Boolean difference is not a constant, the expansion continues.

Figure 8.24. 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 Figure 8.24B, 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:

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.

Example 8.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 Figure 8.25A:

Now apply the reduction rules to simplify the OFDD. The reduced OFDD is shown in Figure 8.25B. 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 Figure 8.25B, 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 8.25. OFDD of (A) An OFDD (B) The reduced OFDD

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: M^k -> 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.

Figure 8.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: Bⁿ -> 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. Example 8.14 illustrates such an application.

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

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 Bⁿ to R, the inputs to the function can be conveniently expressed as “cubes.” For instance, referring to Table 8.4, 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 Bⁿ to R can be expressed as a polynomial. The function in Example 8.14 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 8.28. 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.

Figure 8.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 Figure 8.28A, we obtain the reduced BMD in Figure 8.28B.

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.

In practice, it is rare that these methods work outright without modification. The main problems are running out of memory space or runtime taking too long. To mitigate these problems, two common techniques are used. The first technique identifies as many possible pairs of internal or I/O nodes that are required or known to be equivalent. These nodes are called cut points. This can be done through user-defined mapping between pairs of nodes in the two circuits or by assuming that nodes with the same name correspond to each other. Equating nodes with the same name is based on the rationale that one circuit is often a synthesized version or slightly modified version of the other, and therefore most node names are preserved between the two circuits. Once such a mapping is obtained, the mapped nodes are broken so that the fanins to the nodes are considered as outputs, and the fanouts are considered inputs. The two circuits with these newly formed inputs and outputs, together with the original primary inputs and outputs, are checked for equivalence. The advantage of breaking the known equivalent points and creating new inputs and outputs is that, although there are more outputs to check, the BDDs for the outputs have become smaller, as illustrated in Example 8.15.

Figure 8.30. Circuits for equivalence checking (A) Gate-level model (B) RTL model

Figure 8.31. Compare the largest BDD sizes with and without node mapping. (A) BDD for node f (B) BDD for node x (C) BDD for node y (D) BDD for node z (E) BDD for node f in terms of new variables

Figure 8.32. Create intermediate inputs and outputs from cut points

Thus far, we have assumed that the inputs of the circuits undergoing equivalence checking are unconstrained (that is, the inputs can take on any values). When two circuits are equivalent only in a restricted input or state space, then the input or state space must be constrained. An example of equivalence under restricted space is comparing the next-state function of two finite-state machines. To perform equivalence checking in this situation, the FFs are removed and the next-state functions are compared as stand-alone combinational circuits. Because the next-state functions are now stand-alone functions, their inputs can take on any value. If the finite-state machines do not reach the entire state space, then the inputs to the next-state function must be constrained to the reachable state space of the finite-state machines; otherwise, it is possible that the next-state functions are not equivalent outside the reachable state space. Constraining eliminates the unreachable portion of search space from giving a false negative. Besides limiting input space, constraining can also restrict the structure of a circuit for equivalence checking (for example, by deactivating the scanning portion of a circuit by setting the scan mode to false). The following are some common applications for which constraining plays an important role:

Figure 8.33. Input constraining for checking embedded circuitry

Constraining can be done directly by mapping an unconstrained input space into a permissible input space, as illustrated in Figure 8.33, or indirectly by creating an exclusion function that defaults the two circuits to be equivalent when it detects an input that lies outside the permissible region, as illustrated in Figure 8.34. The entire input space, permission and forbidden, is applied to the circuits under comparison. The exclusion function outputs 1 when an input is forbidden, which then forces the comparison to be equal. Therefore, for the output of this comparison structure always to be 1, the circuits must be equivalent. This indirect method of constraining is easy to implement, as illustrated in Example 8.16.

Figure 8.34. Constrain by forcing output to be equal at forbidden inputs

This method is based on the following resolvent and consensus identity:

and

where A and B are sums of literals, and C and D are product of literals. A + B is called the resolvent of (x + A) and (). CD is called the consensus of xC and . The resolvent identity is applicable to the conjunctive form whereas the consensus identity is applicable to the disjunctive form. In the following discussion we will use the resolvent identity on conjunctive forms.

Now, we want to show that A + B is satisfiable if and only if (x + A)() is satisfiable. According to the resolvent identity, if A + B is satisfiable, then A, B, or both is satisfiable. Let us assume A is satisfiable. Then, when x = 0, (x + A)() becomes A and thus is satisfiable. Similarly, if B is satisfiable, then when x = 1, (x + A)() become B and thus is satisfiable. On the other hand, if (x + A)() is satisfiable, then (x + A)() is satisfiable when x = 0 or x = 1. Let us consider both cases. At x = 0, (x + A)() becomes A and therefore A must be satisfiable. At x = 1, (x + A)() becomes B and hence B must be satisfiable. Therefore, either A or B must be satisfiable if (x + A)() is satisfiable. In conclusion, (x + A)() is satisfiable if and only if A + B is satisfiable. Note that the variable assignments satisfying A + B do not necessarily satisfy (x + A)(). For a counterexample, see Example 8.18 on page 433. By translating the satisfiability problem of (x + A)() to that of A + B, the problem complexity is reduced by one variable—namely, variable x. Extending from two clauses to more clauses, consider (x + A)() (x + C)(). We form the resolvent for all pairs of clauses containing both phases of x. There are a total of four pairs: (x + A)(), (x + A)(), (x + C)(), and (x + C)(). For each pair, we obtain its resolvent. Combining all resolvents, we conclude that (x + A)()(x + C)() is satisfiable if and only if (A + B)(A + D)(C + B) (C + D) is satisfiable. Replacing clauses containing variable x or by their resolvents is called resolving variable x.

After a variable has been resolved, there are straightforward cases that other variable assignments can be easily inferred. If these straightforward cases exist, as many as possible variable assignments are inferred before resolving another variable. Here we will examine some of straightforward cases. First, if a resolvent contains both phases of a variable, such as the resolvent in resolving (x + y)(), then the resolvent, being 1, is removed.

If both phases of a variable are in a formula, the variable is called binate. If only one phase of the variable appears in the formula, the variable is unate. For example, in , a is unate, and b and c are binate. For a unate variable, we simply assign the variable to a value so that the clauses having the variable become 1. Consequently, the resulting formula formed by replacing the clauses containing the unate variable with 1 is satisfiable if and only if the original formula is satisfiable. This replacement operation is called the unate variable rule or the pure literal rule. Therefore, only binate variables need to be resolved.

Another straightforward case is when a clause contains only one literal. For instance, in (a + b + c)()(), the second clause contains only one literal, . Then the variable must be assigned to the value at which the clause is satisfied, which is b = 0 in this case. This rule is called the unit clause rule and the literal in the clause is called the unit literal.

We define an empty clause to be a clause that contains no literals. The resolvent of (x)() is an empty clause. A formula containing an empty clause is unsatisfiable. With this definition, the resolvent algorithm is as follows:

Example 8.18

Let us use the resolvent algorithm to determine the satisfiability of

Select variable a for resolution. For each pair of clauses containing both phases of a, form its resolvent. Clause pairs and their resolvents are shown in Table 8.5. The first column lists the clause pairs containing both phases of a. The second column is the resolvents. The third column is the simplified resolvents. Therefore,

is satisfiable if and only if is satisfiable. Because both variables, b and c, are unate, we apply the unate rule. So reduces to 1. Therefore, the original expression is satisfiable.

Note that the resolvent algorithm does not imply that variable assignments satisfying also satisfy the original expression. As a simple counterexample, a = b = c = 0 satisfies , but does not satisfy the original expression.

As demonstrated by Example 8.18, a resolvent is produced for every pair of clauses containing both phases of a variable. In the worst case, an exponential number of resolvents is computed in solving a SAT problem. Therefore, although mathematically elegant, the resolvent algorithm is reserved for small SAT problems. To deal with large problems, a more efficient search algorithm is required.

A search-based algorithm enumerates all input assignments and evaluates them to decide whether a formula is satisfiable. The set of all possible assignments of the variables in a formula forms the search space. The search space can be represented by a binary tree. A node in the tree represents a variable and has two edges. The left edge represents the variable taking value 1; and the right edge, value 0. A path from the root to a leaf node is a variable assignment, and the value of the leaf node is the value of the formula under the variable assignment. There are a total of 2ⁿ leaf nodes for n variables. A partial path gives a partial variable assignment. If the value of the formula evaluates to 1 at a leaf node, the formula is satisfiable. Therefore, a formula is satisfiable if there is a leaf node of value 1.

Although, in the worst case, a search-based algorithm has to traverse the entire binary tree, oftentimes pruning techniques are used to cut down the number of paths with values that can be deduced. Figure 8.35 illustrates the concept of the search strategy and pruning technique. Suppose we start the search following path P1. Path P1 is a variable assignment of a = 0, c = 1, d = 1, and b = 1. The leaf node for the path is 0. Thus, for this variable assignment, the formula is not satisfied. Let’s backtrack to the last decision node b and take the other choice, b = 0. Backtracking to a previous decision variable and selecting the other value for the variable is called flipping the variable. With this new assignment, the formula is satisfied. In general, backtracking does not have to return to the last decision node; it can return to any prior decision node (for example, decision node c).

Figure 8.35. A search strategy, search path, and pruning by deduction

Next let’s consider a situation in which pruning eliminates the necessity of visiting all paths. Partial path P2 represents the partial variable assignment a = 1, b = 1. Note that the all leaf nodes following this partial path have value 0, meaning that the formula cannot be satisfied if a = 1 and b = 1. Therefore, no further assignments need to be considered; that is, the tree rooted at the c node can be pruned. An intelligent pruning algorithm has to detect this type of subtree at the earliest time.

A search-based SAT solver finds a satisfying variable assignment by making one variable assignment at a time. The candidate variable for assignment is selected based on some heuristic that determines the variable with the “best” chance of making the formula satisfied. Then, after the assignment of the variable is done, the solver attempts to infer as many possible assignments to other variables that must be made to satisfy the formula. After the variable assignment and consequent inferred assignments are made, the formula is evaluated for the partial assignment and is simplified. For example, if x in is selected and assigned 0, the SAT solver substitutes 0 into x and evaluates it to be .

During the evaluation process, three cases are possible for a clause: First, the clause is resolved (evaluates to 1); second, the clause is conflicted (evaluates to 0); and third, the clause does not evaluate to a constant (is indeterminate). If the result of an evaluation of the formula turns out to be 0 and there are still unenumerated variable assignments, some prior variable assignments must be reversed; that is, the solver needs to backtrack. For the other two cases, the search continues. If an evaluation produces a result of 1 for the formula, the formula is satisfiable. On the other hand, if all assignments produce a result of 0, the formula is unsatisfiable.

An efficient search-based algorithm should not enumerate all assignments one by one, but should prune as many assignments as possible that would not satisfy the formula. An outline of the structure of a generic search-based algorithm is shown here. Almost all search-based SAT solvers follow this algorithmic structure and differ in the implementation specifics in routines select_branch() and backtrack(). Routine infer() deduces variable assignments based on the partial assignment made so far, and consists of a collection of special cases that imply other variable assignments:

      forever {
         state = select_branch(); // choose and assign a variable
         if (state == EXHAUSTED) return UNSAT;

         result = infer(); // infer variable values
         if ( result == SAT)
            return SAT;
         else if (result == UNSAT)
            backtrack(); // backtrack to a prior decision
         else // result == INDETERMINATE
            continue; // need further assignment
      }

Routine select_branch() selects a variable that has not yet been assigned, called a free variable, and assigns a value to it. Besides, this routine keeps track of previously visited paths and prunes paths based on the values of already assigned variables. If all assignments have been enumerated, it returns a state EXHAUSTED, which means the formula is unsatisfiable. To select a variable that may satisfy the formula as early as possible, select_branch() relies on some measure of predicting the quality of a new variable assignment. An assignment to a variable is of good quality if the assignment has a high probability of being part of a satisfying assignment or reveals that many paths can be pruned. A reliable quality measure is essential to the performance of a SAT solver. In addition to prediction accuracy, a good assignment quality measure must be easy to compute so that it does not become the bottleneck of the solver. Many heuristics exist for measuring assignment quality. An example predictive measure is the number of literals of a variable in the remaining unsatisfied clauses, the rationale being that an assignment to such a variable will satisfy most clauses. Using this quality measure, select_branch() returns an assignment to the variable that satisfies most remaining clauses. For example, if the remaining clauses of a formula are , then variable b assigned to 1 satisfies three clauses, whereas other variables satisfy fewer clauses. Therefore, select_branch() selects variable b and assigns 1 to it.

Routine infer() looks for special cases in the formula that imply immediate assignments for the remaining unassigned variables. These special cases are the same as those discussed in our study of resolvent algorithms: pure literal rule and unit clause rule. In the pure literal case, there is a variable that appears in only one phase in the formula. The assignment for the variable is then inferred such that the literal becomes 1. For example, a negative-phase literal implies x = 0. In the unit clause case, there is a clause that contains only one literal, so the literal is assigned to 1. The inferred assignments are then substituted into the formula, and the satisfied clauses are removed. This propagation of assignments is called Boolean constraint propagation (BCP). An important requirement in implementing BCP is that it must save a history of previous assignments so that, at the request of routine backtrack(), it can return a previously unassigned value. As an example of the operation of infer(), suppose that the current partial assignment is a = 0, b = 1 in satisfying . After BCP, the formula becomes ()(c + d). Hence it can be inferred that the first clause being a unit clause, c = 0. After a BCP for c = 0, it infers from the second clause that d = 1. In this case, the result is SAT. If the result of infer() is SAT, the formula is satisfiable. If the result is UNSAT, it has to backtrack to a prior decision.

When a partial assignment fails to satisfy the formula, some of the previous assignments must be reversed. Determining the variables to reverse their values is the task for routine backtrack(). Many heuristics exist for selecting variables. The simplest one is to flip the most recently assigned free variable selected by select_branch() that has not been flipped. Note that a variable most recently assigned by infer() must not be chosen for flipping, because such an assignment was forced by another assignment. Therefore, a candidate variable for flipping must be a variable that was assigned by select_branch(). This strategy of reversing the last decision is called chronological backtracking. On the other hand, nonchronological backtracking, when choosing variables to be flipped, does not necessarily flip the last decision variable. It first analyzes the reasons for a conflict, determines the variable assignments that are probable causes of the conflict, and then reverses the root, causing assignment.

If the current partial assignment is not sufficient to determine satisfiability of the formula, the result from infer() is UNDETERMINATE, and it calls select_branch() for the next branch.

Example 8.19

Determine satisfiability of the following formula:

With the select_branch() routine, we use the heuristic that chooses the literal with the highest count. In the formula, and a each appear four times. To break the tie, let’s arbitrarily select . Propagating d = 0 into the formula, we obtain

Now literals a and have the highest count of three each. Arbitrarily selecting a and propagating a = 1, we get .

From this, the first two clauses are unit clauses. So, we infer that b must be 1 and c must be 0. However, when we apply BCP to this expression, it becomes 0. Therefore, we backtrack chronologically to the last decision, a = 1. Reversing the decision, we assign 0 to a. Propagating this assignment to , we get .

We infer that b must be 1. After applying the unit clause rule to remove literal b, we have (c)(ē + f), from which we further infer that c must be 1. Again, using the unit clause rule to remove literal c, we arrive at (ē + f), to which we apply the pure literal rule to deduce e = 0, and conclude that the formula has been satisfied. Therefore, the formula is satisfiable and a satisfying assignment is d = 0, a = 0, b = 1, c = 1, and e = 0.

When an assignment is searched to satisfy a formula, some free variables are selected to take on certain values. The values form a branch in the decision diagram. The selected variables are called decision variables. If the assigned values cause a conflict, other values are assigned. When a decision variable is selected, we associate a decision-level number with it. The decision-level number keeps track of how deep the assignment is from the top of the search and it facilitates backtracking. Variables with values that are forced by the current decision variable, called implied variables, are consequences of the decision variables and are thus assigned the current decision-level number. The decision number starts with 1 when the first decision variable is selected.

To facilitate backtracking, we need to understand the causes of the conflict. The cause of a conflict is an assignment of decision variables that eventually leads to the conflict. To express causes of conflicts, implication graphs are useful. An implication graph is a DAG with vertices that represent assignments to variables and edges that represent consequences of variable assignments. A vertex is labeled with the variable name along with its decision level and is assigned a value. A conflict occurs if both 1 and 0 are in the implication graph. The variable of the conflicting vertices is the conflicting variable. Vertices without incident edges are decision variables, because they are not implied by values of other variables.

Figure 8.36. An implication graph showing the relationship between decision and implied variables

With an implication graph defined, some concepts of an implication graph must be discussed. Vertex v is said to dominate vertex u if any path from a decision variable at the decision level of v to u has to go through v. Intuitively, vertex v determines vertex u. For example, in Figure 8.36, vertex e dominates vertices c and h, because any path from decision vertex b to vertices c or h has to go through e. A unique implication point (UIP) is a vertex at the current decision level that dominates both vertices of a conflict. For example, the vertices of conflict are x(4) and −x(4), and vertex e(4) dominates these vertices; therefore, e(4) is a UIP. The concept of a UIP is used to identify variables to be reversed to resolve a conflict.

When a conflict exists, a cause of the conflict can be obtained by forming a cut on the implication graph such that the graph is partitioned into two parts: reason and conflict. The conflict part contains the conflicting vertices and possibly other implied variables. Note that there is no decision variable in the conflict part. The other part is called the reason part and it consists of all other vertices. Two cuts are shown in Figure 8.36.

The decision variables in the reason part that have an edge to the conflict part contribute to a cause of the conflict. The edges of decision variables crossing a cut represent assignments leading to the conflict and hence must be avoided.

When a search encounters a conflict, the path leading to the conflict should be avoided in any future search. This path of conflict can be learned by including a clause in the formula so that this particular variable assignment can be avoided early during the search. To do so, a cut of a conflict is first determined. Then, the edges of the decision variables crossing the cut are identified. These edges form a clause, which when satisfied avoids the conflict, resulting in an assignment. For example, cut 1 in Figure 8.36 corresponds to variable assignment e = 1, h = 0, d = 1, which results in a conflict. To avoid this partial assignment, any future assignment must satisfy one of the following: e = 0 or h = 1, or d = 0. In other words, clause must be satisfied. This new clause can be added to the original formula. Note that the added clause is redundant in the sense that it does not change the satisfiability of the formula. Its only function is to speed up decision making by preventing a repeat of known conflicting assignments.

There can be more than one cut per conflict. Different cuts give different learning clauses. A preferred cut is one that contains only one decision variable assigned at the current level and others assigned at lower levels, because this is the variable that has the most immediate impact on the conflict, and its value should be reversed in backtracking. Cuts with this property are called asserting cuts. At a given decision level, an asserting cut can always be found because the decision variable at the current level is always a UIP. Different cuts represent different learning schemes. For more in-depth information, consult the bibliography.

Example 8.21

Consider the satisfiability of

To satisfy the formula, variable e must be assigned 1. Because there is no decision variable chosen yet, variable e has decision level 0. At level 1, we choose variable a as a decision variable and assign it to 1. This selection reduces the formula to

which implies that variable c must be 0. Thus, the formula further simplifies to . The next decision variable selected is b. Suppose we assign it to 1. This assignment forces variable d in the first clause to be 0, and variable d in the second clause to be 1—a conflict. An implication graph for the process so far is shown in Figure 8.37. The cut shown gives clause which is ANDed with the original formula to prevent future decisions from arriving at this conflict. Therefore, the formula with this learned clause is

Now we can either decide this formula or backtrack. To continue the decision process, we infer that c = 0, which implies (through the learned clause) b = 0. This assignment satisfies the formula. If we backtrack, we first find a cut. The cut shown is an asserting cut, and the variable to flip is b. Assigning b to 0 satisfies the formula.

Figure 8.37. Implication result from a satisfiability process

The ability to simulate multiple inputs simultaneously allows one to verify conclusively and efficiently some properties or assertions that a traditional simulation methodology would have to enumerate explicitly for all possibilities. The properties, sometimes called assertions, are in the form of Boolean functions of states, internal variables, and external inputs. An example property is that if signal A is high then B must be low after, at most, two cycles.

A property or assertion can be categorized as bound or unbound. A bound property is defined over a finite time interval or a bound number of cycles; otherwise, it is an unbound property. An example of a bound property is that from cycle n to cycle m, at least one packet must arrive. The interval in which this property is defined is from cycle n to m. An example of an unbound property is that after a request has become active, the grant will become active eventually.

To verify a bound property, the circuit can be simulated symbolically for the interval of the property. If the property holds within the interval, the property is affirmed. Suppose that a property is f(x, y, z) = 1 from cycle 5 to cycle 6, where x, y, and z are nodes of a circuit. If f(x₅, y₅, z₅) · f(x₆, y₆, z₆) = 1, where x₅, y₅, z₅, x₆, y₆, and z₆ are results at cycles 5 and 6 from a symbolic simulation, then the property is affirmed.

An unbound property, sometimes called an invariant, is verified if it can be shown that the property holds for all possible inputs and states. A standard verification strategy is to apply mathematical induction on the cycle number: If the invariant holds at the initial cycle and at the n^th cycle, given that it holds at the n – 1 cycle, then it holds for all cycles. However, not all invariants are easy to recast into a form amicable for mathematical induction.

Variable constraining restricts some free variables, which can take on any value when unconstrained, to certain values. Two situations in which variable constraining is useful are case splitting and environment modeling.

As seen in the previous example, the complexity of node expressions grows rapidly if all inputs are allowed to be free variables. To reduce the complexity, we can restrict some free variables to take on specific values and, by doing so, the unconstrained become constants and the free variables are eliminated from the symbolic expressions. By constraining variables, we sacrifice the number of input points simulated simultaneously, and thus reduce the coverage of the symbolic run. To cover the entire input space, the other cases of the constrained variables have to be simulated on a separate run. For example, suppose that input c has been constrained to be 0 for the first two cycles in a symbolic run. Then the other cases of variable c, 10, 01, and 11 in the first two cycles, must be simulated in other runs. Furthermore, input variables can be constrained to an expression other than constants. For example, input a can be constrained to be equal to input c.

In a general setting of case splitting, input space is partitioned so that instead of verifying a circuit under the most general input conditions, one can verify the circuit under inputs in each of the subspaces. Within a subspace, the circuit simplifies, and thus verification is accelerated. An example of case splitting is to divide inputs to an ALU into four subspaces: logical operations, arithmetic operations, shift and rotation, and all other operations. For logical operations, the ALU is reduced only to the units responsible for logical operations. Therefore, in case-splitting verification, the input must be constrained to the subspace for the case. Case splitting is complementary to structural partitioning. Structural partitioning breaks down a system into components and verifies each component individually, and then verifies at the system level the components’ interoperation, whereas case splitting keeps the structure and partitions the data space.

Therefore, case splitting is a compromise between complexity and coverage. The more input space partitioned, the simpler the simulation complexity and the less the coverage of each run. Case splitting is the transition mechanism bridging traditional and symbolic simulation. If all free variables are constrained, symbolic simulation degenerates to traditional simulation.

The second situation in which constraining is applicable is modeling the input environment of the circuit under consideration. For instance, if the input bits to an encoder are always one-hot, then, in verifying the encoder, its inputs cannot be totally free variables, but must be constrained to the one-hot condition. To constrain, we create a set of new input variables (which are free variables) and a mapping from the new inputs to the original inputs. With the mapping, the circuit sees only the permissible inputs while the new inputs are allowed to take on any value. This is achieved by crafting the mapping such that every point in the new input space produces a point in the restricted space, and every point in the restricted space is produced by at least one point in the new input space. The mapping is then composed with the circuit. Assume that a circuit has n inputs, and R is the constrained input space, where R ⊆ Bⁿ. That is, only inputs in R are permissible. The mapping, from B^m to Bⁿ, maps B^m to R. This constraining process is conceptually illustrated in Figure 8.41. This process is also called parameterization.

Figure 8.41. Constraining input space with a onto mapping

Example 8.24

The environment feeding the inputs of an embedded circuit of three inputs x, y, z, and outputs p and q, where p = f(x, y, z) and q = h(x, y, z), can only produce 100, 111, 010, and 011. These values form the permissible input space. If we take out the embedded circuit and simulate it as a stand-alone, we must ensure that the inputs to the circuit are permissible. To constrain the inputs, we need to introduce two new inputs, v and w, and map the four permissible inputs to the inputs of the circuit. The mapping is shown in Table 8.10.

Translating the mapping into Boolean functions, we get x = , y = v + w, z = w. Now, substitute these functions into the circuit equations. We obtain

The new inputs v and w are free variables that always produce permissible inputs to the circuit.

Thus far in our discussion, circuits and constraining mappings are represented using I/O equations. An alternative is representation using characteristic functions. An I/O equation, say y = f(x, q), z = h(x, q), where x is input, y is output, q is state, and z is next state, can be represented by the following characteristic function:

If we use (a = b) to denote the characteristic function that produces 1 if a = b and 0 otherwise (XNOR operator), then the previous characteristic function can be written as (y = f(x,q))(z = h(x, q)). Using this representation, the values of the output y and the next state z after symbolically simulating one cycle are all the values y₁ and z₁ satisfying the following expression:

If state devices are DFFs, then the state value is equal to the next-state value computed during the previous cycle. Therefore, the result of symbolically simulating two cycles is

The first two terms are governed by the circuit’s output and next-state function. The third term computes the next-state function at cycle 1, which becomes the state value at cycle 2. The last term simply forces the state at cycle 2 to be equal to the next-state value computed at cycle 1.

Example 8.25

Let’s simulate the circuit in Figure 8.42 using characteristic functions. The circuit equations are y = xq and z = x ⊕ q.

Using a characteristic function, we obtain . The result of one cycle of the simulation is given by . Comparing this result with that from circuit equations, we assert that the characteristic function is 1 if and only if y₁ = x₁q₁ and z₁ = x₁ ⊕ q₁. So values produced by the characteristic function are identical to those derived using circuit equations.

The simulation result based on circuit equations at cycle 2 is y₂ = x₂(x₁ ⊕ q₁) and z₂ = x₂ ⊕ (x₁ ⊕ q₁). The result of the simulation at cycle 2 using characteristic functions is .

If the characteristic function is 1, then each of the four terms is equal to 1. That is, , , , and are all 1, which hold if and only if y₂ = x₂q₂, z₂ = x₂ ⊕ q₂, z₁ =x₁ ⊕ q₁, and q₂ = z₁. Eliminating intermediate variables q₂ and z₁, we have

and

which are identical to the result derived based on circuit equations. Therefore, we conclude that the simulation using characteristic functions yields the same result.

Figure 8.42. Symbolic simulation using characteristic functions

Constraining inputs is readily done when characteristic functions are used in symbolic simulation. Let μ(x) be a characteristic function representing the permissible input space. In other words, μ(x) = 1 if and only if x ε R. And let λ(y, z, x, q) be the characteristic function of the circuit. Then, the circuit with its inputs constrained to the permissible space R is μ(x) · λ(y, z, x, q). This is because the product is 1 if and only if the input lies in the permissible space and it satisfies the circuit. Notice how easily constraining is done using characteristic functions, compared with the method using circuit equation representation discussed earlier. This illustrates an advantage of using characteristic functions in symbolic manipulations.

Example 8.26

Let’s repeat Example 8.24 using characteristic functions. The restricted inputs are represented by

The characteristic function for the unconstrained circuit is

Therefore, the characteristic function of the constrained circuit is

As a check, if input (x,y,z) = 101, we want to know what output value the previous characteristic function would produce. Substituting the input vector, we have

which means no values of p and q are valid outputs. This is because 101 is not a permissible input. For any permissible input, Λ(x, y, z, p, q) reduces to λ(x, y, z, p, q).

In addition to being used in constraining input space, parameterization is also used to reduce representation complexity by taking advantage of functional dependency. A case in point is the functional dependency among the components of the state vector in a finite-state machine. For a vector Boolean function

parameterization of F(x₁, ..., x_n) creates another Boolean function

where variables t₁, ..., t_m are called parameters, and g_i: B^m->B, i = 1, ..., k.

Furthermore, F and G satisfy the following condition. For every (x₁, ..., x_n) there is a (t₁, ..., t_m) such that F(x₁, ..., x_n) = G(t₁, ..., t_m), and vice versa. In other words, G(t₁, ..., t_m) preserves the range of F(x₁, ..., x_n). Note that f_i and g_i may have different numbers of arguments. For practical purpose, G(t₁, ..., t_m) should be simpler than F(x₁, ..., x_n).

Before delving into parameterization on functional dependency, let’s first look at the simplifying effect of using parameterization with Example 8.28.

Example 8.28

Consider the circuit in Example 8.22. Because the state is only 1 bit, it can be replaced with a free variable at each cycle. (Here we assume the state is not a constant; thus, it can take on 1 or 0, just as a free variable.) The new variable is a parameter. For example, in cycle 2, the expression for node k is simply k₂, a free variable, as opposed to the computed value . Using this method of parameterization, the symbolic node values at cycle 2 are as shown in Table 8.11. The second column lists the values with state parameterization, and the last column lists the results without state parameterization. Note the reduction in complexity.

When simulation detects an error, a counterexample, which is just an input sequence that would produce the same error when run on a logic simulator, has to be generated. To generate a counterexample in symbolic simulation with parameterization, we may have to use the equations that replaced the parameters. A counterexample input sequence is formed by back tracing cycle by cycle from the time of error back to the first cycle. At the n^th cycle, a binary constant, say V_n, is picked that is consistent with the symbolic result at the current cycle such that V_n would cause V_{n + 1} in the n + 1^th cycle. Then time is moved back one cycle, and the same procedure is repeated. After the initial cycle is reached, the input sequence made of the Vs in reverse order is a counterexample.

As an example, suppose at cycle 2, the output f should not be 1. Based on our simulation, the value of f at cycle 2 is , which can be 1. Therefore, an error has occurred. To generate a counterexample, let’s search a value at cycle 2 at which node f is 1. Such a value is k₂ = b₂ = c₂ = 1. Because k₂ is a parameter, we have to use its original equation to back trace further. The equation that k₂ was replaced with is

From which we determine that if a₁ = c₁ = 0, then k₂ = 1. Therefore, a counterexample is as follows:

At cycle 1, a = 1, c = 0.

At cycle 2, b = 1, c = 1.

Parameterization when the state vector has more than 1 bit is more complicated. First, functional dependency among the state bits must be detected, and then parameters are created to minimize the state representation. It is important that the range of the original function be preserved. Example 8.29 illustrates this concept and process by parameterizing the next-state function.

Figure 8.43. Parameterization based on functional dependency

As seen in the previous examples, there are many ways to parameterize a function, and parameterized functions of various complexity result. For a more complete study of parameterization, consult the bibliography.