Binary Decision Diagrams:Basic Concepts

Basic Concepts

Binary decision diagrams (BDDs), which were introduced in Chapter 26, Section 26.1, are a powerful means for computer processing of logic functions because in many cases, with BDDs, smaller memory space is required for storing logic functions and values of functions can be calculated faster than with truth tables or logic expressions. As logic design has been done in recent years with computers, BDDs are extensively used because of these features. BDDs are used in computer programs for automation of logic design, verification (i.e., identifying whether two logic networks represent the identical logic functions), diagnosis of logic networks, simplification of transistor circuits (such as ECL and MOSFET circuits, as explained in Chapters 38, 39, and 40), and other areas, including those not related to logic design.

In this chapter, we discuss the basic data structures and algorithms for manipulating BDDs. Then we describe the variable ordering problem, which is important for the effective use of BDDs. The concept of BDD was devised by Lee in 1959 [15]. Binary decision programs that Lee discussed are essentially binary decision diagrams. Then, in 1978, its usefulness for expressing logic functions was shown by Akers [3,4]. But since Bryant [6] developed a reduction method in 1986, it has been extensively used for design automation for logic design and related areas.

From a truth table, we can easily derive the corresponding binary decision diagram. For example, the truth table shown in Figure 29.1(a) can be converted into the BDD in Figure 29.1(b). But there are generally many BDDs for a given truth table, that is, the logic function expressed by this truth table. For example, all BDDs shown in Figure 29.1(c) through (e) represent the logic function that the truth table in Figure 29.1(a) expresses. Here, note that in each of Figures 29.1 (b), (c), and (d), the variables appear in the same order and none of them appears more than once in every path from the top node. But in (e), they appear in different orders in different paths. BDDs in Figures 29.1(b), (c), and (d) are called ordered BDDs (or OBDDs). But the BDD in Figure 29.1(e) is called an unordered BDD. These BDDs can be reduced into a simple BDD by the following procedure.

In a BDD, the top node is called the root that represents the given function f(x1, x2, …, xn). Rectangles that have 1 or 0 inside are called terminal nodes. They are also called 1-terminal and 0-terminal. Other nodes are called non-terminal nodes denoted by circles with variables inside. They are also called simply nodes, differentiating themselves from the 0- and 1-terminals. From a node with xi inside, two lines go down. The solid line is called 1-edge, representing xi = 1; and the dotted line is called 0-edge, representing xi = 0.

In an OBDD, the value of the function f can be evaluated by following a path of edges from the root node to one of the terminal nodes. If the nodes in every path from the root node to a terminal node are assigned with variables, x1, x2, x3, … , and xn, in this order, then f can be expressed as follows, according to the Shannon expansion (described in Chapter 27). By branching with respect to x1 from the root node, f(x1, x2, … , xn) can be expanded as follows, where f (0, x2, … , xn) and f(1, x2, … , xn) are functions that the nodes at the low ends of 0-edge and 1-edge from the root represent, respectively:

And so on. As we go down from the root node toward the 0- or 1-terminal, more variables of f are set to 0 or 1. Each term excluding xi or xi in each of these expansions [i.e., f (0, x2, … , xn) and f(1, x2, … , xn) in the first expansion, f (0, 0, … , xn) and f (0, 1, … , xn) in the second expansion, etc.], are called cofactors. Each node at the low ends of 0-edge and 1-edge from a node in an OBDD represents cofactors of the Shannon expansion of the logic function at the node, from which these 0-edge and 1-edge come down.

Procedure 29.1: Reduction of a BDD

1. For the given BDD, apply the following steps in any order.

a. If two nodes, va and vb , that represent the same variable xi, branch to the same nodes in a lower level for each of xi = 0 and xi = 1, then combine them into one node that still represents variable xi.

In Figure 29.2(a), two nodes, va and vb , that represent variable xi, go to the same node vu for xi = 0 and the same node vv for xi = 1. Then, according to Step a, two nodes, va and vb, are merged into one node vab, as shown in Figure 29.2(b). The node vab represents variable xi.

b. If a node that represents a variable xi branches to the same node in a lower level for both xi = 0 and xi = 1, then that node is deleted, and the 0- and 1-edges that come down to the former are extended to the latter.

In Figure 29.3(a), node va that represents variable xi branches to the same node vb for both xi = 0 and xi = 1. Then, according to Step b, node va is deleted, as shown in Figure 29.3(b), where the node va is a don’t-care for xi, and the edges that come down to va are extended to vu.

c. Terminals nodes with the same value, 0 or 1, are merged into the terminal node with the same original value.

All the 0-terminals in Figure 29.1(b) are combined into one 0-terminal in each of Figures 29.1(c), (d), and (e). All the 1-terminals are similarly combined.

2. When we cannot apply any step after repeatedly applying these steps (a), (b), and (c), the reduced ordered BDD (i.e., ROBDD) or simply called the reduced BDD (i.e., RBDD), is obtained for the given function.

The following process is faster than the repeated application of Step 1(a) of Procedure 29.1. Suppose a BDD contains two nodes, va and vb, both of which represent xi, such that a sub-BDD, B1, that stretches downward from va is completely identical to another sub-BDD, B2, that stretches downward from vb. In this case, each sub-BDD is said to be isomorphic to the other. Then the two sub-BDDs can be merged. For example, the two sub-BDDs, B1 and B2, shown in the two dotted rectangles in Figure 29.4(a), both representing x4, can be merged into one, B3, as shown in Figure 29.4(b).

Theorem 29.1: Any completely or incompletely specified function has a unique reduced ordered BDD and any other ordered BDD for the function in the same order of variables (i.e., not reduced) has more nodes.

According to this theorem, the ROBDD is unique for a given logic function when the order of the variables is fixed. (A BDD that has don’t-cares can be expressed with addition of the d-terminal or two BDDs for the ON-set and OFF-set completely specified functions, as explained with Figure 23.5. For details, see Ref. 24.) Thus, ROBDDs give canonical forms for logic functions. This property is very important to practical applications, as we can easily check the equivalence of two logic functions by only checking the isomorphism of their ROBDDs. Henceforth in this chapter, ROBDDs will be referred to as BDDs for the sake of simplicity.

It is known that a BDD for an n-variable function requires an exponentially increasing memory space in the worst case, as n increases [16]. However, the size of memory space for the BDD varies with the types of functions, unlike truth tables which always require memory space proportional to 2n. But many logic functions that we encounter in design practice can be shown with BDDs without large memory space [14]. This is an attractive feature of BDDs. Figure 29.5 shows the BDDs repre- senting typical functions, AND, OR, and the parity function with three and n input variables. The parity function for n variables, x1 ⊕ x2 ⊕ … ⊕ xn , can be shown with the BDD of 2(n – 1) + 1 nodes and 2 terminals; whereas, if a truth table or a logic expression is used, the size increases exponentially as n increases.

A set of BDDs representing many functions can be combined into a graph that consists of BDDs sharing sub-graphs among them, as shown in Figure 29.6. This idea saves time and space for duplicating isomorphic BDDs. By sharing all the isomorphic sub-graphs completely, no two nodes that express the same function coexist in the graph. We call it shared BDDs (SBDDs) [25], or multi-rooted BDDs. In a shared BDD, no two root nodes express the same function.

Shared BDDs are now widely used and those algorithms are more concise than ordinary BDDs. In the remainder of this chapter, we deal with shared BDD only.