Implement the following function with two level nor gate circuit

167

c h a p t e r

4 Optimized Implementation of Logic

Functions

Chapter Objectives

In this chapter you will learn about:

• Synthesis of logic functions • Analysis of logic circuits • Techniques for deriving minimum-cost implementations of logic functions • Graphical representation of logic functions in the form of Karnaugh maps • Cubical representation of logic functions • Use of CAD tools and VHDL to implement logic functions

168 C H A P T E R 4 • Optimized Implementation of Logic Functions

In Chapter 2 we showed that algebraic manipulation can be used to find the lowest-cost implementations of logic functions. The purpose of that chapter was to introduce the basic concepts in the synthesis process. The reader is probably convinced that it is easy to derive a straightforward realization of a logic function in a canonical form, but it is not at all obvious how to choose and apply the theorems and properties of section 2.5 to find a minimum-cost circuit. Indeed, the algebraic manipulation is rather tedious and quite impractical for functions of many variables.

If CAD tools are used to design logic circuits, the task of minimizing the cost of implementation does not fall to the designer; the tools perform the necessary optimizations automatically. Even so, it is essential to know something about this process. Most CAD tools have many features and options that are under control of the user. To know when and how to apply these options, the user must have an understanding of what the tools do.

In this chapter we will introduce some of the optimization techniques implemented in CAD tools and show how these techniques can be automated. As a first step we will discuss a graphical approach, known as the Karnaugh map, which provides a neat way to manually derive minimum-cost implementations of simple logic functions. Although it is not suitable for implementation in CAD tools, it illustrates a number of key concepts. We will show how both two-level and multilevel circuits can be designed. Then we will describe a cubical representation for logic functions, which is suitable for use in CAD tools. We will also continue our discussion of the VHDL language.

4.1 Karnaugh Map

In section 2.6 we saw that the key to finding a minimum-cost expression for a given logic function is to reduce the number of product (or sum) terms needed in the expression, by applying the combining property 14a (or 14b) as judiciously as possible. The Karnaugh map approach provides a systematic way of performing this optimization. To understand how it works, it is useful to review the algebraic approach from Chapter 2. Consider the function f in Figure 4.1. The canonical sum-of-products expression for f consists of minterms m0, m2, m4, m5, and m6, so that

f = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 The combining property 14a allows us to replace two minterms that differ in the value of only one variable with a single product term that does not include that variable at all. For example, both m0 and m2 include x1 and x3, but they differ in the value of x2 because m0 includes x2 while m2 includes x2. Thus

x1x2x3 + x1x2x3 = x1(x2 + x2)x3 = x1 · 1 · x3 = x1x3

4.1 Karnaugh Map 169

Row number x1 x2 x3 f

0 0 0 0 1 1 0 0 1 0 2 0 1 0 1 3 0 1 1 0 4 1 0 0 1 5 1 0 1 1 6 1 1 0 1 7 1 1 1 0

Figure 4.1 The function f (x1, x2, x3) = ∑ m(0, 2, 4, 5, 6).

Hence m0 and m2 can be replaced by the single product term x1x3. Similarly, m4 and m6 differ only in the value of x2 and can be combined using

x1x2x3 + x1x2x3 = x1(x2 + x2)x3 = x1 · 1 · x3 = x1x3

Now the two newly generated terms, x1x3 and x1x3, can be combined further as

x1x3 + x1x3 = (x1 + x1)x3 = 1 · x3 = x3

These optimization steps indicate that we can replace the four minterms m0, m2, m4, and m6 with the single product term x3. In other words, the minterms m0, m2, m4, and m6 are all included in the term x3. The remaining minterm in f is m5. It can be combined with m4, which gives

x1x2x3 + x1x2x3 = x1x2 Recall that theorem 7b in section 2.5 indicates that

m4 = m4 + m4 which means that we can use the minterm m4 twice—to combine with minterms m0, m2, and m6 to yield the term x3 as explained above and also to combine with m5 to yield the term x1x2.

We have now accounted for all the minterms in f ; hence all five input valuations for which f = 1 are covered by the minimum-cost expression

f = x3 + x1x2

170 C H A P T E R 4 • Optimized Implementation of Logic Functions

The expression has the product term x3 because f = 1 when x3 = 0 regardless of the values of x1 and x2. The four minterms m0, m2, m4, and m6 represent all possible minterms for which x3 = 0; they include all four valuations, 00, 01, 10, and 11, of variables x1 and x2. Thus if x3 = 0, then it is guaranteed that f = 1. This may not be easy to see directly from the truth table in Figure 4.1, but it is obvious if we write the corresponding valuations grouped together:

x1 x2 x3

m0 0 0 0

m2 0 1 0

m4 1 0 0

m6 1 1 0

In a similar way, if we look at m4 and m5 as a group of two

x1 x2 x3

m4 1 0 0

m5 1 0 1

it is clear that when x1 = 1 and x2 = 0, then f = 1 regardless of the value of x3. The preceding discussion suggests that it would be advantageous to devise a method

that allows easy discovery of groups of minterms for which f = 1 that can be combined into single terms. The Karnaugh map is a useful vehicle for this purpose.

The Karnaugh map [1] is an alternative to the truth-table form for representing a function. The map consists of cells that correspond to the rows of the truth table. Consider the two-variable example in Figure 4.2. Part (a) depicts the truth-table form, where each of the four rows is identified by a minterm. Part (b) shows the Karnaugh map, which has four cells. The columns of the map are labeled by the value of x1, and the rows are labeled by x2. This labeling leads to the locations of minterms as shown in the figure. Compared to the truth table, the advantage of the Karnaugh map is that it allows easy recognition of minterms that can be combined using property 14a from section 2.5. Minterms in any two cells that are adjacent, either in the same row or the same column, can be combined. For example, the minterms m2 and m3 can be combined as

m2 + m3 = x1x2 + x1x2 = x1(x2 + x2) = x1 · 1 = x1

4.1 Karnaugh Map 171

� �

� �

(a) Truth table (b) Karnaugh map

0

1

0 1

� �

� �

� �

� �

� � � �

0 0

0 1

1 0

1 1

� �

� �

� �

� �

Figure 4.2 Location of two-variable minterms.

The Karnaugh map is not just useful for combining pairs of minterms. As we will see in several larger examples, the Karnaugh map can be used directly to derive a minimum-cost circuit for a logic function.

Two-Variable Map A Karnaugh map for a two-variable function is given in Figure 4.3. It corresponds to

the function f of Figure 2.15. The value of f for each valuation of the variables x1 and x2 is indicated in the corresponding cell of the map. Because a 1 appears in both cells of the bottom row and these cells are adjacent, there exists a single product term that can cause f to be equal to 1 when the input variables have the values that correspond to either of these cells. To indicate this fact, we have circled the cell entries in the map. Rather than using the combining property formally, we can derive the product term intuitively. Both of the cells are identified by x2 = 1, but x1 = 0 for the left cell and x1 = 1 for the right cell. Thus if x2 = 1, then f = 1 regardless of whether x1 is equal to 0 or 1. The product term representing the two cells is simply x2.

Similarly, f = 1 for both cells in the first column. These cells are identified by x1 = 0. Therefore, they lead to the product term x1. Since this takes care of all instances where f = 1, it follows that the minimum-cost realization of the function is

f = x2 + x1 Evidently, to find a minimum-cost implementation of a given function, it is necessary

to find the smallest number of product terms that produce a value of 1 for all cases where

� �

� �

1 0

1 1

� � �

��+= 0

1

0 1

Figure 4.3 The function of Figure 2.15.

172 C H A P T E R 4 • Optimized Implementation of Logic Functions

f = 1. Moreover, the cost of these product terms should be as low as possible. Note that a product term that covers two adjacent cells is cheaper to implement than a term that covers only a single cell. For our example once the two cells in the bottom row have been covered by the product term x2, only one cell (top left) remains. Although it could be covered by the term x1x2, it is better to combine the two cells in the left column to produce the product term x1 because this term is cheaper to implement.

Three-Variable Map A three-variable Karnaugh map is constructed by placing 2 two-variable maps side

by side. Figure 4.4 shows the map and indicates the locations of minterms in it. In this case each valuation of x1 and x2 identifies a column in the map, while the value of x3 distinguishes the two rows. To ensure that minterms in the adjacent cells in the map can always be combined into a single product term, the adjacent cells must differ in the value of only one variable. Thus the columns are identified by the sequence of (x1, x2) values of 00, 01, 11, and 10, rather than the more obvious 00, 01, 10, and 11. This makes the second and third columns different only in variable x1. Also, the first and the fourth columns differ only in variable x1, which means that these columns can be considered as being adjacent. The reader may find it useful to visualize the map as a rectangle folded into a cylinder where the left and the right edges in Figure 4.4b are made to touch. (A sequence of codes, or valuations, where consecutive codes differ in one variable only is known as the Gray code. This code is used for a variety of purposes, some of which will be encountered later in the book.)

Figure 4.5a represents the function of Figure 2.18 in Karnaugh-map form. To synthe- size this function, it is necessary to cover the four 1s in the map as efficiently as possible. It is not difficult to see that two product terms suffice. The first covers the 1s in the top row, which are represented by the term x1x3. The second term is x2x3, which covers the 1s in the bottom row. Hence the function is implemented as

f = x1x3 + x2x3 which describes the circuit obtained in Figure 2.19a.

� � � �

� � 00 01 11 10

0

1

(b) Karnaugh map

� � � �

0 0

0 1

1 0

1 1

� �

� �

� �

� �

0

0

0

0

0 0

0 1

1 0

1 1

1

1

1

1

� �

� �

� �

� �

� �

(a) Truth table

� �

� �

� �

� �

� �

� �

� �

� �

Figure 4.4 Location of three-variable minterms.

4.1 Karnaugh Map 173

� � � � �

� � � �

+=

� � � �

� �

0 0

1 0

1 1

0 1

� � � �

� �

1 1

0 0

1 1

0 1

(a) The function of Figure 2.18

� � �

� � � �

+=

(b) The function of Figure 4.1

00 01 11 10

0

1

00 01 11 10

0

1

Figure 4.5 Examples of three-variable Karnaugh maps.

In a three-variable map it is possible to combine cells to produce product terms that correspond to a single cell, two adjacent cells, or a group of four adjacent cells. Realization of a group of four adjacent cells using a single product term is illustrated in Figure 4.5b, using the function from Figure 4.1. The four cells in the top row correspond to the (x1, x2, x3) valuations 000, 010, 110, and 100. As we discussed before, this indicates that if x3 = 0, then f = 1 for all four possible valuations of x1 and x2, which means that the only requirement is that x3 = 0. Therefore, the product term x3 represents these four cells. The remaining 1, corresponding to minterm m5, is best covered by the term x1x2, obtained by combining the two cells in the right-most column. The complete realization of f is

f = x3 + x1x2 It is also possible to have a group of eight 1s in a three-variable map. This is the trivial case where f = 1 for all valuations of input variables; in other words, f is equal to the con- stant 1.

The Karnaugh map provides a simple mechanism for generating the product terms that should be used to implement a given function. A product term must include only those variables that have the same value for all cells in the group represented by this term. If the variable is equal to 1 in the group, it appears uncomplemented in the product term; if it is equal to 0, it appears complemented. Each variable that is sometimes 1 and sometimes 0 in the group does not appear in the product term.

Four-Variable Map A four-variable map is constructed by placing 2 three-variable maps together to create

four rows in the same fashion as we used 2 two-variable maps to form the four columns in a three-variable map. Figure 4.6 shows the structure of the four-variable map and the location

174 C H A P T E R 4 • Optimized Implementation of Logic Functions

� � � �

� � � � 00 01 11 10

00

01

11

10

� �

� �

� �

� �

� �

� �

� �

� �

� ��

� ��

� �

� �

� �

� �

�

�

� ��

� ��

� ��

� ��

Figure 4.6 A four-variable Karnaugh map.

of minterms. We have included in this figure another frequently used way of designating the rows and columns. As shown in blue, it is sufficient to indicate the rows and columns for which a given variable is equal to 1. Thus x1 = 1 for the two right-most columns, x2 = 1 for the two middle columns, x3 = 1 for the bottom two rows, and x4 = 1 for the two middle rows.

Figure 4.7 gives four examples of four-variable functions. The function f1 has a group of four 1s in adjacent cells in the bottom two rows, for which x2 = 0 and x3 = 1—they are represented by the product term x2x3. This leaves the two 1s in the second row to be covered, which can be accomplished with the term x1x3x4. Hence the minimum-cost implementation of the function is

f1 = x2x3 + x1x3x4 The function f2 includes a group of eight 1s that can be implemented by a single term, x3. Again, the reader should note that if the remaining two 1s were implemented separately, the result would be the product term x1x3x4. Implementing these 1s as a part of a group of four 1s, as shown in the figure, gives the less expensive product term x1x4.

Just as the left and the right edges of the map are adjacent in terms of the assignment of the variables, so are the top and the bottom edges. Indeed, the four corners of the map are adjacent to each other and thus can form a group of four 1s, which may be implemented by the product term x2x4. This case is depicted by the function f3. In addition to this group of 1s, there are four other 1s that must be covered to implement f3. This can be done as shown in the figure.

In all examples that we have considered so far, a unique solution exists that leads to a minimum-cost circuit. The function f4 provides an example where there is some choice. The groups of four 1s in the top-left and bottom-right corners of the map are realized by the terms x1x3 and x1x3, respectively. This leaves the two 1s that correspond to the term x1x2x3. But these two 1s can be realized more economically by treating them as a part of a group of four 1s. They can be included in two different groups of four, as shown in the figure.

4.1 Karnaugh Map 175

� � � �

� � � �

1

00 01 11 10

0 0 1

0 0 0 0

1 1 1 0

1 1 0 1

00

01

11

10

� � � �

� � � �

1

00 01 11 10

1 1 0

1 1 1 0

0 0 1 1

0 0 1 1

00

01

11

10

� � � �

� � � �

0

00 01 11 10

0 0 0

0 0 1 1

1 0 0 1

1 0 0 1

00

01

11

10

� � � �

� � � �

0

00 01 11 10

0 0 0

0 0 1 1

1 1 1 1

1 1 1 1

00

01

11

10

� �

� � � �

� � � � � �

+= � �

� �

� � � �

+=

� �

� � � �

� � � �

� � � � � �

+ += � �

� � � �

� � � �

+ += � � � �

� � ��

or

Figure 4.7 Examples of four-variable Karnaugh maps.

One choice leads to the product term x1x2, and the other leads to x2x3. Both of these terms have the same cost; hence it does not matter which one is chosen in the final circuit. Note that the complement of x3 in the term x2x3 does not imply an increased cost in comparison with x1x2, because this complement must be generated anyway to produce the term x1x3, which is included in the implementation.

Five-Variable Map We can use 2 four-variable maps to construct a five-variable map. It is easy to imagine

a structure where one map is directly behind the other, and they are distinguished by x5 = 0 for one map and x5 = 1 for the other map. Since such a structure is awkward to draw, we can simply place the two maps side by side as shown in Figure 4.8. For the logic function given in this example, two groups of four 1s appear in the same place in both four-variable maps; hence their realization does not depend on the value of x5. The same is true for the two groups of two 1s in the second row. The 1 in the top-right corner appears only in the

176 C H A P T E R 4 • Optimized Implementation of Logic Functions

� � � �

� � � � 00 01 11 10

1 1

1 1

1 1

00

01

11

10

� � � �

� � � � 00 01 11 10

1

1 1

1 1

1 1

00

01

11

10

� �

� � � �

� � � � � �

� � � � � � � �

+ +=

� �

�=� �

�=

Figure 4.8 A five-variable Karnaugh map.

right map, where x5 = 1; it is a part of the group of two 1s realized by the term x1x2x3x5. Note that in this map we left blank those cells for which f = 0, to make the figure more readable. We will do likewise in a number of maps that follow.

Using a five-variable map is obviously more awkward than using maps with fewer variables. Extending the Karnaugh map concept to more variables is not useful from the practical point of view. This is not troublesome, because practical synthesis of logic functions is done with CAD tools that perform the necessary minimization automatically. Although Karnaugh maps are occasionally useful for designing small logic circuits, our main reason for introducing the Karnaugh maps is to provide a simple vehicle for illustrating the ideas involved in the minimization process.

4.2 Strategy for Minimization

For the examples in the preceding section, we used an intuitive approach to decide how the 1s in a Karnaugh map should be grouped together to obtain the minimum-cost implementation of a given function. Our intuitive strategy was to find as few as possible and as large as possible groups of 1s that cover all cases where the function has a value of 1. Each group of 1s has to comprise cells that can be represented by a single product term. The larger the group of 1s, the fewer the number of variables in the corresponding product term. This approach worked well because the Karnaugh maps in our examples were small. For larger logic functions, which have many variables, such intuitive approach is unsuitable. Instead, we must have an organized method for deriving a minimum-cost implementation. In this section we will introduce a possible method, which is similar to the techniques that are

4.2 Strategy for Minimization 177

automated in CAD tools. To illustrate the main ideas, we will use Karnaugh maps. Later, in section 4.8, we will describe a different way of representing logic functions, which is used in CAD tools.

4.2.1 Terminology

A huge amount of research work has gone into the development of techniques for synthesis of logic functions. The results of this research have been published in numerous papers. To facilitate the presentation of the results, certain terminology has evolved that avoids the need for using highly descriptive phrases. We define some of this terminology in the following paragraphs because it is useful for describing the minimization process.

Literal A given product term consists of some number of variables, each of which may appear

either in uncomplemented or complemented form. Each appearance of a variable, either uncomplemented or complemented, is called a literal. For example, the product term x1x2x3 has three literals, and the term x1x3x4x6 has four literals.

Implicant A product term that indicates the input valuation(s) for which a given function is equal

to 1 is called an implicant of the function. The most basic implicants are the minterms, which we introduced in section 2.6.1. For an n-variable function, a minterm is an implicant that consists of n literals.

Consider the three-variable function in Figure 4.9. There are 11 possible implicants for this function. This includes the five minterms: x1x2x3, x1x2x3, x1x2x3, x1x2x3, and x1x2x3. Then there are the implicants that correspond to all possible pairs of minterms that can be combined, namely, x1x2 (m0 and m1), x1x3 (m0 and m2), x1x3 (m1 and m3), x1x2 (m2 and m3), and x2x3 (m3 and m7). Finally, there is one implicant that covers a group of four minterms, which consists of a single literal x1.

� � � �

� �

1 1

1 1

� �

0 0

1 0

00 01 11 10

0

1

� � � �

Figure 4.9 Three-variable function f (x1, x2, x3) =∑ m(0, 1, 2, 3, 7).

178 C H A P T E R 4 • Optimized Implementation of Logic Functions

Prime Implicant An implicant is called a prime implicant if it cannot be combined into another implicant

that has fewer literals. Another way of stating this definition is to say that it is impossible to delete any literal in a prime implicant and still have a valid implicant.

In Figure 4.9 there are two prime implicants: x1 and x2x3. It is not possible to delete a literal in either of them. Doing so for x1 would make it disappear. For x2x3, deleting a literal would leave either x2 or x3. But x2 is not an implicant because it includes the valuation (x1, x2, x3) = 110 for which f = 0, and x3 is not an implicant because it includes (x1, x2, x3) = 101 for which f = 0.

Cover A collection of implicants that account for all valuations for which a given function is

equal to 1 is called a cover of that function. A number of different covers exist for most functions. Obviously, a set of all minterms for which f = 1 is a cover. It is also apparent that a set of all prime implicants is a cover.

A cover defines a particular implementation of the function. In Figure 4.9 a cover consisting of minterms leads to the expression

f = x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 + x1x2x3 Another valid cover is given by the expression

f = x1x2 + x1x2 + x2x3 The cover comprising the prime implicants is

f = x1 + x2x3 While all of these expressions represent the function f correctly, the cover consisting of prime implicants leads to the lowest-cost implementation.

Cost In Chapter 2 we suggested that a good indication of the cost of a logic circuit is the

number of gates plus the total number of inputs to all gates in the circuit. We will use this definition of cost throughout the book. But we will assume that primary inputs, namely, the input variables, are available in both true and complemented forms at zero cost. Thus the expression

f = x1x2 + x3x4 has a cost of nine because it can be implemented using two AND gates and one OR gate, with six inputs to the AND and OR gates.

If an inversion is needed inside a circuit, then the corresponding NOT gate and its input are included in the cost. For example, the expression

g = x1x2 + x3(x4 + x5) is implemented using two AND gates, two OR gates, and one NOT gate to complement (x1x2 + x3), with nine inputs. Hence the total cost is 14.

4.2 Strategy for Minimization 179

4.2.2 Minimization Procedure

We have seen that it is possible to implement a given logic function with various circuits. These circuits may have different structures and different costs. When designing a logic circuit, there are usually certain criteria that must be met. One such criterion is likely to be the cost of the circuit, which we considered in the previous discussion. In general, the larger the circuit, the more important the cost issue becomes. In this section we will assume that the main objective is to obtain a minimum-cost circuit.

Having said that cost is the primary concern, we should note that other optimization criteria may be more appropriate in some cases. For instance, in Chapter 3 we described several types of programmable-logic devices (PLDs) that have a predefined basic structure and can be programmed to realize a variety of different circuits. For such devices the main objective is to design a particular circuit so that it will fit into the target device. Whether or not this circuit has the minimum cost is not important if it can be realized successfully on the device. A CAD tool intended for design with a specific device in mind will automatically perform optimizations that are suitable for that device. We will show in section 4.6 that the way in which a circuit should be optimized may be different for different types of devices.

In the previous subsection we concluded that the lowest-cost implementation is achieved when the cover of a given function consists of prime implicants. The ques- tion then is how to determine the minimum-cost subset of prime implicants that will cover the function. Some prime implicants may have to be included in the cover, while for others there may be a choice. If a prime implicant includes a minterm for which f = 1 that is not included in any other prime implicant, then it must be included in the cover and is called an essential prime implicant. In the example in Figure 4.9, both prime implicants are essential. The term x2x3 is the only prime implicant that covers the minterm m7, and x1 is the only one that covers the minterms m0, m1, and m2. Notice that the minterm m3 is covered by both of these prime implicants. The minimum-cost realization of the function is

f = x1 + x2x3 We will now present several examples in which there is a choice as to which prime

implicants to include in the final cover. Consider the four-variable function in Figure 4.10. There are five prime implicants: x1x3, x2x3, x3x4, x1x2x4, and x2x3x4. The essential ones (highlighted in blue) are x2x3 (because of m11), x3x4 (because of m14), and x2x3x4 (because of m13). They must be included in the cover. These three prime implicants cover all minterms for which f = 1 except m7. It is clear that m7 can be covered by either x1x3 or x1x2x4. Because x1x3 has a lower cost, it is chosen for the cover. Therefore, the minimum-cost realization is

f = x2x3 + x3x4 + x2x3x4 + x1x3 From the preceding discussion, the process of finding a minimum-cost circuit involves

the following steps:

1. Generate all prime implicants for the given function f .

2. Find the set of essential prime implicants.

180 C H A P T E R 4 • Optimized Implementation of Logic Functions

� � � �

� � � � 00 01 11 10

11

1 1

1 1

00

01

11

10

� � � �

1 1

1

� � � �

� � � � � �

� � � �

� � � � � �

Figure 4.10 Four-variable function f (x1, . . . , x4) =∑ m(2, 3, 5, 6, 7, 10, 11, 13, 14).

3. If the set of essential prime implicants covers all valuations for which f = 1, then this set is the desired cover of f . Otherwise, determine the nonessential prime implicants that should be added to form a complete minimum-cost cover.

The choice of nonessential prime implicants to be included in the cover is governed by the cost considerations. This choice is often not obvious. Indeed, for large functions there may exist many possibilities, and some heuristic approach (i.e., an approach that considers only a subset of possibilities but gives good results most of the time) has to be used. One such approach is to arbitrarily select one nonessential prime implicant and include it in the cover and then determine the rest of the cover. Next, another cover is determined assuming that this prime implicant is not in the cover. The costs of the resulting covers are compared, and the less-expensive cover is chosen for implementation.

We can illustrate the process by using the function in Figure 4.11. Of the six prime implicants, only x3x4 is essential. Consider next x1x2x3 and assume first that it will be

� � � �

� � � � 00 01 11 10

1

1 111

1

00

01

11

10

� � � � � �

1

1

� � � �

� � � � � �

� � � � � �

� � � � � �

� � � � � �

Figure 4.11 The function f (x1, . . . , x4) =∑ m(0, 4, 8, 10, 11, 12, 13, 15).

4.2 Strategy for Minimization 181

included in the cover. Then the remaining three minterms, m10, m11, and m15, will require two more prime implicants to be included in the cover. A possible implementation is

f = x3x4 + x1x2x3 + x1x3x4 + x1x2x3 The second possibility is that x1x2x3 is not included in the cover. Then x1x2x4 becomes essential because there is no other way of covering m13. Because x1x2x4 also covers m15, only m10 and m11 remain to be covered, which can be achieved with x1x2x3. Therefore, the alternative implementation is

f = x3x4 + x1x2x4 + x1x2x3 Clearly, this implementation is a better choice.

Sometimes there may not be any essential prime implicants at all. An example is given in Figure 4.12. Choosing any of the prime implicants and first including it, then excluding it from the cover leads to two alternatives of equal cost. One includes the prime implicants indicated in black, which yields

f = x1x3x4 + x2x3x4 + x1x3x4 + x2x3x4 The other includes the prime implicants indicated in blue, which yields

f = x1x2x4 + x1x2x3 + x1x2x4 + x1x2x3 This procedure can be used to find minimum-cost implementations of both small and

large logic functions. For our small examples it was convenient to use Karnaugh maps to determine the prime implicants of a function and then choose the final cover. Other techniques based on the same principles are much more suitable for use in CAD tools; we will introduce such techniques in sections 4.9 and 4.10.

The previous examples have been based on the sum-of-products form. We will next illustrate that the same concepts apply for the product-of-sums form.

� � � �

� � � � 00 01 11 10

1

1

1

1

1

1

00

01

11

10 1

1

� � � � � �

� � � � � �

� � � � � �

� � � � � �

� � � � � �

� � � � � �

� � � � � �

� � � � � �

Figure 4.12 The function f (x1, . . . , x4) =∑ m(0, 2, 4, 5, 10, 11, 13, 15).

182 C H A P T E R 4 • Optimized Implementation of Logic Functions

4.3 Minimization of Product-of-Sums Forms

Now that we know how to find the minimum-cost sum-of-products (SOP) implementations of functions, we can use the same techniques and the principle of duality to obtain minimum- cost product-of-sums (POS) implementations. In this case it is the maxterms for which f = 0 that have to be combined into sum terms that are as large as possible. Again, a sum term is considered larger if it covers more maxterms, and the larger the term, the less costly it is to implement.

Figure 4.13 depicts the same function as Figure 4.9 depicts. There are three maxterms that must be covered: M4, M5, and M6. They can be covered by two sum terms shown in the figure, leading to the following implementation:

f = (x1 + x2)(x1 + x3) A circuit corresponding to this expression has two OR gates and one AND gate, with two inputs for each gate. Its cost is greater than the cost of the equivalent SOP implementation derived in Figure 4.9, which requires only one OR gate and one AND gate.

The function from Figure 4.10 is reproduced in Figure 4.14. The maxterms for which f = 0 can be covered as shown, leading to the expression

f = (x2 + x3)(x3 + x4)(x1 + x2 + x3 + x4) This expression represents a circuit with three OR gates and one AND gate. Two of the OR gates have two inputs, and the third has four inputs; the AND gate has three inputs. Assuming that both the complemented and uncomplemented versions of the input variables x1 to x4 are available at no extra cost, the cost of this circuit is 15. This compares favorably with the SOP implementation derived from Figure 4.10, which requires five gates and 13 inputs at a total cost of 18.

In general, as we already know from section 2.6.1, the SOP and POS implementations of a given function may or may not entail the same cost. The reader is encouraged to find the POS implementations for the functions in Figures 4.11 and 4.12 and compare the costs with the SOP forms.

We have shown how to obtain minimum-cost POS implementations by finding the largest sum terms that cover all maxterms for which f = 0. Another way of obtaining

� � � �

� �

1

00 01 11 10

0

1

1 0 0

1 1 1 0

� �

� �

+( )

� �

� �

+( )

Figure 4.13 POS minimization of f (x1, x2, x3) = �M (4, 5, 6).

4.3 Minimization of Product-of-Sums Forms 183

� � � �

� � � �

0

00 01 11 10

0 0 0

0 1 1 0

1 1 0 1

1 1 1 1

00

01

11

10

� �

� �

+( )

� �

� �

+( )

� �

� �

� �

� �

+ + +( )

Figure 4.14 POS minimization of f (x1, . . . , x4) = �M (0, 1, 4, 8, 9, 12, 15).

the same result is by finding a minimum-cost SOP implementation of the complement of f . Then we can apply DeMorgan’s theorem to this expression to obtain the simplest POS

realization because f = f . For example, the simplest SOP implementation of f in Figure 4.13 is

f = x1x2 + x1x3 Complementing this expression using DeMorgan’s theorem yields

f = f = x1x2 + x1x3 = x1x2 · x1x3 = (x1 + x2)(x1 + x3)

which is the same result as obtained above. Using this approach for the function in Figure 4.14 gives

f = x2x3 + x3x4 + x1x2x3x4 Complementing this expression produces

f = f = x2x3 + x3x4 + x1x2x3x4 = x2x3 · x3x4 · x1x2x3x4 = (x2 + x3)(x3 + x4)(x1 + x2 + x3 + x4)

which matches the previously derived implementation.

184 C H A P T E R 4 • Optimized Implementation of Logic Functions

4.4 Incompletely Specified Functions

In digital systems it often happens that certain input conditions can never occur. For example, suppose that x1 and x2 control two interlocked switches such that both switches cannot be closed at the same time. Thus the only three possible states of the switches are that both switches are open or that one switch is open and the other switch is closed. Namely, the input valuations (x1, x2) = 00, 01, and 10 are possible, but 11 is guaranteed not to occur. Then we say that (x1, x2) = 11 is a don’t-care condition, meaning that a circuit with x1 and x2 as inputs can be designed by ignoring this condition. A function that has don’t-care condition(s) is said to be incompletely specified.

Don’t-care conditions, or don’t-cares for short, can be used to advantage in the design of logic circuits. Since these input valuations will never occur, the designer may assume that the function value for these valuations is either 1 or 0, whichever is more useful in trying to find a minimum-cost implementation. Figure 4.15 illustrates this idea. The required function has a value of 1 for minterms m2, m4, m5, m6, and m10. Assuming the above- mentioned interlocked switches, the x1 and x2 inputs will never be equal to 1 at the same time; hence the minterms m12, m13, m14, and m15 can all be used as don’t-cares. The don’t-

� � � �

� � � �

0

00 01 11 10

1 d 0

0 1 d 0

0 0 d 0

1 1 d 1

00

01

11

10

� �

� �

+( )

� �

� �

+( )

� � � �

� � � �

0

00 01 11 10

1 d 0

0 1 d 0

0 0 d 0

1 1 d 1

00

01

11

10

� � � �

� � � �

(a) SOP implementation

(b) POS implementation

Figure 4.15 Two implementations of the function f (x1, . . . , x4) =∑ m(2, 4, 5, 6, 10) + D(12, 13, 14, 15).

4.4 Incompletely Specified Functions 185

cares are denoted by the letter d in the map. Using the shorthand notation, the function f is specified as

f (x1, . . . , x4) = ∑

m(2, 4, 5, 6, 10) + D(12, 13, 14, 15) where D is the set of don’t-cares.

Part (a) of the figure indicates the best sum-of-products implementation. To form the largest possible groups of 1s, thus generating the lowest-cost prime implicants, it is necessary to assume that the don’t-cares D12, D13, and D14 (corresponding to minterms m12, m13, and m14) have the value of 1 while D15 has the value of 0. Then there are only two prime implicants, which provide a complete cover of f . The resulting implementation is

f = x2x3 + x3x4 Part (b) shows how the best product-of-sums implementation can be obtained. The

same values are assumed for the don’t cares. The result is

f = (x2 + x3)(x3 + x4) The freedom in choosing the value of don’t-cares leads to greatly simplified realizations. If we were to naively exclude the don’t-cares from the synthesis of the function, by assuming that they always have a value of 0, the resulting SOP expression would be

f = x1x2x3 + x1x3x4 + x2x3x4 and the POS expression would be

f = (x2 + x3)(x3 + x4)(x1 + x2) Both of these expressions have higher costs than the expressions obtained with a more appropriate assignment of values to don’t-cares.

Although don’t-care values can be assigned arbitrarily, an arbitrary assignment may not lead to a minimum-cost implementation of a given function. If there are k don’t-cares, then there are 2k possible ways of assigning 0 or 1 values to them. In the Karnaugh map we can usually see how best to do this assignment to find the simplest implementation.

In the example above, we chose the don’t-cares D12, D13, and D14 to be equal to 1 and D15 equal to 0 for both the SOP and POS implementations. Thus the derived expressions represent the same function, which could also be specified as

∑ m(2, 4, 5, 6, 10, 12, 13, 14).

Assigning the same values to the don’t-cares for both SOP and POS implementations is not always a good choice. Sometimes it may be advantageous to give a particular don’t-care the value 1 for SOP implementation and the value 0 for POS implementation, or vice versa. In such cases the optimal SOP and POS expressions will represent different functions, but these functions will differ only for the valuations that correspond to these don’t-cares. Example 4.24 in section 4.14 illustrates this possibility.

Using interlocked switches to illustrate how don’t-care conditions can occur in a real system may seem to be somewhat contrived. However, in Chapters 6, 8, and 9 we will encounter many examples of don’t-cares that occur in the course of practical design of digital circuits.

186 C H A P T E R 4 • Optimized Implementation of Logic Functions

4.5 Multiple-Output Circuits

In all previous examples we have considered single functions and their circuit implemen- tations. In practical digital systems it is necessary to implement a number of functions as part of some large logic circuit. Circuits that implement these functions can often be combined into a less-expensive single circuit with multiple outputs by sharing some of the gates needed in the implementation of individual functions.

Example 4.1 An example of gate sharing is given in Figure 4.16. Two functions, f1 and f2, of the same variables are to be implemented. The minimum-cost implementations for these functions

� � � �

� � � � 00 01 11 10

1 1

1 1

1 1 1

1 1

00

01

11

10

� � � �

� � � � 00 01 11 10

1 1

1 1

1 1

1 1

00

01

11

10

(a) Function (b) Function

1

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

(c) Combined circuit for � � � �and

Figure 4.16 An example of multiple-output synthesis.

4.5 Multiple-Output Circuits 187

are obtained as shown in parts (a) and (b) of the figure. This results in the expressions

f1 = x1x3 + x1x3 + x2x3x4 f2 = x1x3 + x1x3 + x2x3x4

The cost of f1 is four gates and 10 inputs, for a total of 14. The cost of f2 is the same. Thus the total cost is 28 if both functions are implemented by separate circuits. A less-expensive realization is possible if the two circuits are combined into a single circuit with two outputs. Because the first two product terms are identical in both expressions, the AND gates that implement them need not be duplicated. The combined circuit is shown in Figure 4.16c. Its cost is six gates and 16 inputs, for a total of 22.

In this example we reduced the overall cost by finding minimum-cost realizations of f1 and f2 and then sharing the gates that implement the common product terms. This strategy does not necessarily always work the best, as the next example shows.

Example 4.2Figure 4.17 shows two functions to be implemented by a single circuit. Minimum-cost realizations of the individual functions f3 and f4 are obtained from parts (a) and (b) of the figure.

f3 = x1x4 + x2x4 + x1x2x3 f4 = x1x4 + x2x4 + x1x2x3x4

None of the AND gates can be shared, which means that the cost of the combined circuit would be six AND gates, two OR gates, and 21 inputs, for a total of 29.

But several alternative realizations are possible. Instead of deriving the expressions for f3 and f4 using only prime implicants, we can look for other implicants that may be shared advantageously in the combined realization of the functions. Figure 4.17c shows the best choice of implicants, which yields the realization

f3 = x1x2x4 + x1x2x3x4 + x1x4 f4 = x1x2x4 + x1x2x3x4 + x2x4

The first two implicants are identical in both expressions. The resulting circuit is given in Figure 4.17d . It has the cost of six gates and 17 inputs, for a total of 23.

Example 4.3In Example 4.1 we sought the best SOP implementation for the functions f1 and f2 in Figure 4.16. We will now consider the POS implementation of the same functions. The minimum-cost POS expressions for f1 and f2 are

f1 = (x1 + x3)(x1 + x2 + x3)(x1 + x3 + x4) f2 = (x1 + x3)(x1 + x2 + x3)(x1 + x3 + x4)

188 C H A P T E R 4 • Optimized Implementation of Logic Functions

� � � �

� � � � 00 01 11 10

1

1 1

1

00

01

11

10

(a) Optimal realization of (b) Optimal realization of

1

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

(d) Combined circuit for � � � �and

(c) Optimal realization of � �

1

1

� � � �

� � � � 00 01 11 10

1

1 1

1

00

01

11

10

11

1

� � � �

� � � � 00 01 11 10

1 1

1

1

00

01

11

10

1

1 1

� � � �

� � � � 00 01 11 10

1 1

1

1

00

01

11

10

1

1 1

and together� �

� �

Figure 4.17 Another example of multiple-output synthesis.

4.6 Multilevel Synthesis 189

There are no common sum terms in these expressions that could be shared in the imple- mentation. Moreover, from the Karnaugh maps in Figure 4.16, it is apparent that there is no sum term (covering the cells where f1 = f2 = 0) that can be profitably used in realizing both f1 and f2. Thus the best choice is to implement each function separately, according to the preceding expressions. Each function requires three OR gates, one AND gate, and 11 inputs. Therefore, the total cost of the circuit that implements both functions is 30. This realization is costlier than the SOP realization derived in Example 4.1.

Example 4.4Consider now the POS realization of the functions f3 and f4 in Figure 4.17. The minimum- cost POS expressions for f3 and f4 are

f3 = (x3 + x4)(x2 + x4)(x1 + x4)(x1 + x2) f4 = (x3 + x4)(x2 + x4)(x1 + x4)(x1 + x2 + x4)

The first three sum terms are the same in both f3 and f4; they can be shared in a combined circuit. These terms require three OR gates and six inputs. In addition, one 2-input OR gate and one 4-input AND gate are needed for f3, and one 3-input OR gate and one 4-input AND gate are needed for f4. Thus the combined circuit comprises five OR gates, two AND gates, and 19 inputs, for a total cost of 26. This cost is slightly higher than the cost of the circuit derived in Example 4.2.

These examples show that the complexities of the best SOP or POS implementations of given functions may be quite different. For the functions in Figures 4.16 and 4.17, the SOP form gives better results. But if we are interested in implementing the complements of the four functions in these figures, then the POS form would be less costly.

Sophisticated CAD tools used to synthesize logic functions will automatically perform the types of optimizations illustrated in the preceding examples.

4.6 Multilevel Synthesis

In the preceding sections our objective was to find a minimum-cost sum-of-products or product-of-sums realization of a given logic function. Logic circuits of this type have two levels (stages) of gates. In the sum-of-products form, the first level comprises AND gates that are connected to a second-level OR gate. In the product-of-sums form, the first-level OR gates feed the second-level AND gate. We have assumed that both true and complemented versions of the input variables are available so that NOT gates are not needed to complement the variables.

A two-level realization is usually efficient for functions of a few variables. However, as the number of inputs increases, a two-level circuit may result in fan-in problems. Whether

190 C H A P T E R 4 • Optimized Implementation of Logic Functions

Part of a PAL-like block

(from interconnection wires) � �

� �

� �

� �

� �

� �

� � unused

f

Figure 4.18 Implementation in a CPLD.

or not this is an issue depends on the type of technology that is used to implement the circuit. For example, consider the following function:

f (x1, . . . , x7) = x1x3x6 + x1x4x5x6 + x2x3x7 + x2x4x5x7 This is a minimum-cost SOP expression. Now consider implementing f in two types of PLDs: a CPLD and an FPGA. Figure 4.18 shows a part of one of the PAL-like blocks from Figure 3.33. The figure indicates in blue the circuitry used to realize the function f . Clearly, the SOP form of the function is well suited to the chip architecture of the CPLD.

Next, consider implementing f in an FPGA. For this example we will use the FPGA shown in Figure 3.39, which contains two-input LUTs. Since the SOP expression for f requires three- and four-input AND operations and a four-input OR, it cannot be directly implemented in this FPGA. The problem is that the fan-in required to implement the function is too high for our target chip architecture.

To solve the fan-in problem, f must be expressed in a form that has more than two levels of logic operations. Such a form is called a multilevel logic expression. There are several different approaches for synthesis of multilevel circuits. We will discuss two important techniques known as factoring and functional decomposition.

4.6.1 Factoring

The distributive property in section 2.5 allows us to factor the preceding expression for f as follows

f = x1x6(x3 + x4x5) + x2x7(x3 + x4x5) = (x1x6 + x2x7)(x3 + x4x5)

4.6 Multilevel Synthesis 191

0 0 0 1

0 1 1 1

� �

� �

�

�

�

�

� �

� �

� � �

0 1 1 1

0 0 0 1

� �

�

�

�

�

�

� �

� �

� �

� �

0 0 0 1

� �

� �

�

0 0 1 0

� �

� �

�

Figure 4.19 Implementation in an FPGA.

The corresponding circuit has a maximum fan-in of two; hence it can be realized using two-input LUTs. Figure 4.19 gives a possible implementation using the FPGA from Figure 3.39. Note that a two-variable function that has to be realized by each LUT is indicated in the box that represents the LUT.

Fan-in Problem In the preceding example, the fan-in restrictions were caused by the fixed structure

of the FPGA, where each LUT has only two inputs. However, even when the target chip architecture is not fixed, the fan-in may still be an issue. To illustrate this situation, let us consider the implementation of a circuit in a custom chip. Recall that custom chips usually contain a large number of gates. If the chip is fabricated using CMOS technology, then there will be fan-in limitations as discussed in section 3.8.8. In this technology the number of inputs to a logic gate should be small. For instance, we may wish to limit the number of inputs to an AND gate to be less than five. Under this restriction, if a logic expression includes a seven-input product term, we would have to use 2 four-input AND gates, as indicated in Figure 4.20.

Factoring can be used to deal with the fan-in problem. Suppose again that the available gates have a maximum fan-in of four and that we want to realize the function

f = x1x2x3x4x5x6 + x1x2x3x4x5x6

192 C H A P T E R 4 • Optimized Implementation of Logic Functions

7 inputs

Figure 4.20 Using four-input AND gates to realize a seven-input product term.

� �

� �

� �

� �

� �

� �

� �

� �

� �

Figure 4.21 A factored circuit.

This is a minimal sum-of-products expression. Using the approach of Figure 4.20, we will need four AND gates and one OR gate to implement this expression. A better solution is to factor the expression as follows

f = x1x4x6(x2x3x5 + x2x3x5) Then three AND gates and one OR gate suffice for realization of the required function, as shown in Figure 4.21.

Example 4.5 In practical situations a designer of logic circuits often encounters specifications that natu- rally lead to an initial design where the logic expressions are in a factored form. Suppose we need a circuit that meets the following requirements. There are four inputs: x1, x2, x3, and x4. An output, f1, must have the value 1 if at least one of the inputs x1 and x2 is equal to 1 and both x3 and x4 are equal to 1; it must also be 1 if x1 = x2 = 0 and either x3 or x4 is 1. In all other cases f1 = 0. A different output, f2, is to be equal to 1 in all cases except when both x1 and x2 are equal to 0 or when both x3 and x4 are equal to 0.

4.6 Multilevel Synthesis 193

� �

� �

� �

� �

� �

� �

Figure 4.22 Circuit for Example 4.5.

From this specification, the function f1 can be expressed as

f1 = (x1 + x2)x3x4 + x1x2(x3 + x4) This expression can be simplified to

f1 = x3x4 + x1x2(x3 + x4) which the reader can verify by using a Karnaugh map.

The second function, f2, is most easily defined in terms of its complement, such that

f 2 = x1x2 + x3x4 Then using DeMorgan’s theorem gives

f2 = (x1 + x2)(x3 + x4) which is the minimum-cost expression for f2; the cost increases significantly if the SOP form is used.

Because our objective is to design the lowest-cost combined circuit that implements f1 and f2, it seems that the best result can be achieved if we use the factored forms for both functions, in which case the sum term (x3 + x4) can be shared. Moreover, observing that x1x2 = x1 + x2, the sum term (x1 + x2) can also be shared if we express f1 in the form

f1 = x3x4 + x1 + x2(x3 + x4) Then the combined circuit, shown in Figure 4.22, comprises three OR gates, three AND gates, one NOT gate, and 13 inputs, for a total of 20.

Impact on Wiring Complexity The space on integrated circuit chips is occupied by the circuitry that implements logic

gates and by the wires needed to make connections among the gates. The amount of space

194 C H A P T E R 4 • Optimized Implementation of Logic Functions

needed for wiring is a substantial portion of the chip area. Therefore, it is useful to keep the wiring complexity as low as possible.

In a logic expression each literal corresponds to a wire in the circuit that carries the desired logic signal. Since factoring usually reduces the number of literals, it provides a powerful mechanism for reducing the wiring complexity in a logic circuit. In the synthesis process the CAD tools consider many different issues, including the cost of the circuit, the fan-in, and the wiring complexity.

4.6.2 Functional Decomposition

In the preceding examples, which illustrated the factoring approach, multilevel circuits were used to deal with fan-in limitations. However, such circuits may be preferable to their two-level equivalents even if fan-in is not a problem. In some cases the multilevel circuits may reduce the cost of implementation. On the other hand, they usually imply longer propagation delays, because they use multiple stages of logic gates. We will explore these issues by means of illustrative examples.

Complexity of a logic circuit, in terms of wiring and logic gates, can often be reduced by decomposing a two-level circuit into subcircuits, where one or more subcircuits implement functions that may be used in several places to construct the final circuit. To achieve this objective, a two-level logic expression is replaced by two or more new expressions, which are then combined to define a multilevel circuit. We can illustrate this idea by a simple example.

Example 4.6 Consider the minimum-cost sum-of-products expression

f = x1x2x3 + x1x2x3 + x1x2x4 + x1x2x4 and assume that the inputs x1 to x4 are available only in their true form. Then the expression defines a circuit that has four AND gates, one OR gate, two NOT gates, and 18 inputs (wires) to all gates. The fan-in is three for the AND gates and four for the OR gate. The reader should observe that in this case we have included the cost of NOT gates needed to complement x1 and x2, rather than assume that both true and complemented versions of all input variables are available, as we had done before.

Factoring x3 from the first two terms and x4 from the last two terms, this expression becomes

f = (x1x2 + x1x2)x3 + (x1x2 + x1x2)x4 Now let g(x1, x2) = x1x2 + x1x2 and observe that

g = x1x2 + x1x2 = x1x2 · x1x2 = (x1 + x2)(x1 + x2) = x1x1 + x1x2 + x2x1 + x2x2 = 0 + x1x2 + x1x2 + 0 = x1x2 + x1x2

4.6 Multilevel Synthesis 195

Then f can be written as

f = gx3 + gx4 which leads to the circuit shown in Figure 4.23. This circuit requires an additional OR gate and a NOT gate to invert the value of g. But it needs only 15 inputs. Moreover, the largest fan-in has been reduced to two. The cost of this circuit is lower than the cost of its two-level equivalent. The trade-off is an increased propagation delay because the circuit has three more levels of logic.

In this example the subfunction g is a function of variables x1 and x2. The subfunction is used as an input to the rest of the circuit that completes the realization of the required function f . Let h denote the function of this part of the circuit, which depends on only three inputs: g, x3, and x4. Then the decomposed realization of f can be expressed algebraically as

f (x1, x2, x3, x4) = h[g(x1, x2), x3, x4] The structure of this decomposition can be described in block-diagram form as shown in Figure 4.24.

� �

� �

� �

� �

�

g

Figure 4.23 Logic circuit for Example 4.6.

� �

� �

� �

� �

�

g

h

Figure 4.24 The structure of decomposition in Example 4.6.

196 C H A P T E R 4 • Optimized Implementation of Logic Functions

While not evident from our first example, functional decomposition can lead to great reductions in the complexity and cost of circuits. The reader will get a good indication of this benefit from the next example.

Example 4.7 Figure 4.25a defines a five-variable function f in the form of a Karnaugh map. In searching for a good decomposition for this function, it is necessary to first identify the variables that will be used as inputs to a subfunction. We can get a useful clue from the patterns of 1s in the map. Note that there are only two distinct patterns in the rows of the map. The second and fourth rows have one pattern, highlighted in blue, while the first and third rows have the other pattern. Once we specify which row each pattern is in, then the pattern itself

1 11 1

1 11 1

� � � �

� � � � 00 01 11 10

00

01

11

10

� � � �

� � � � 00 01 11 10

1 1

1 1

1

1

1

00

01

11

10

1

� �

�= � �

�= (a) Karnaugh map for the function f

� �

� �

� �

� �

���

g

k

(b) Circuit obtained using decomposition

Figure 4.25 Decomposition for Example 4.7.

4.6 Multilevel Synthesis 197

depends only on the variables that define columns in each row, namely, x1, x2, and x5. Let a subfunction g(x1, x2, x5) represent the pattern in rows 2 and 4. This subfunction is just

g = x1 + x2 + x5 because the pattern has a 1 wherever any of these variables is equal to 1. To specify the location of rows where the pattern g occurs, we use the variables x3 and x4. The terms x3x4 and x3x4 identify the second and fourth rows, respectively. Thus the expression (x3x4 + x3x4) · g represents the part of f that is defined in rows 2 and 4.

Next, we have to find a realization for the pattern in rows 1 and 3. This pattern has a 1 only in the cell where x1 = x2 = x5 = 0, which corresponds to the term x1x2x5. But we can make a useful observation that this term is just a complement of g. The location of rows 1 and 3 is identified by terms x3x4 and x3x4, respectively. Thus the expression (x3x4 +x3x4) ·g represents f in rows 1 and 3.

We can make one other useful observation. The expressions (x3x4 + x3x4) and (x3x4 + x3x4) are complements of each other, as shown in Example 4.6. Therefore, if we let k(x3, x4) = x3x4 + x3x4, the complete decomposition of f can be stated as

f (x1, x2, x3, x4, x5) = h[g(x1, x2, x5), k(x3, x4)] = kg + kg

where g = x1 + x2 + x5 k = x3x4 + x3x4

The resulting circuit is given in Figure 4.25b. It requires a total of 11 gates and 19 inputs. The largest fan-in is three.

For comparison, a minimum-cost sum-of-products expression for f is

f = x1x3x4 + x1x3x4 + x2x3x4 + x2x3x4 + x3x4x5 + x3x4x5 + x1x2x3x4x5 + x1x2x3x4x5 The corresponding circuit requires a total of 14 gates (including the five NOT gates to complement the primary inputs) and 41 inputs. The fan-in for the output OR gate is eight. Obviously, functional decomposition results in a much simpler implementation of this function.

In both of the preceding examples, the decomposition is such that a decomposed sub- function depends on some primary input variables, whereas the remainder of the imple- mentation depends on the rest of the variables. Such decompositions are called disjoint decompositions in the technical literature. It is possible to have a non-disjoint decomposi- tion, where the variables of the subfunction are also used in realizing the remainder of the circuit. The following example illustrates this possibility.

Example 4.8Exclusive-OR (XOR) is a very useful function. In section 3.9.1 we showed how it can be realized using a special circuit. It can also be realized using AND and OR gates as shown

198 C H A P T E R 4 • Optimized Implementation of Logic Functions

� �

� �

� �

� �

⊕

� �

� �

� �

� �

g

� �

� �

⊕

� �

� �

⊕

(a) Sum-of-products implementation

(b) NAND gate implementation

(c) Optimal NAND gate implementation

Figure 4.26 Implementation of XOR.

in Figure 4.26a. In section 2.7 we explained how any AND-OR circuit can be realized as a NAND-NAND circuit that has the same structure.

Let us now try to exploit functional decomposition to find a better implementation of XOR using only NAND gates. Let the symbol ↑ represent the NAND operation so that x1 ↑ x2 = x1 · x2. A sum-of-products expression for the XOR function is

x1 ⊕ x2 = x1x2 + x1x2

4.6 Multilevel Synthesis 199

From the discussion in section 2.7, this expression can be written in terms of NAND operations as

x1 ⊕ x2 = (x1 ↑ x2) ↑ (x1 ↑ x2) This expression requires five NAND gates, and it is implemented by the circuit in Figure 4.26b. Observe that an inverter is implemented using a two-input NAND gate by tying the two inputs together.

To find a decomposition, we can manipulate the term (x1 ↑ x2) as follows: (x1 ↑ x2) = (x1x2) = (x1(x1 + x2)) = (x1 ↑ (x1 + x2))

We can perform a similar manipulation for (x1 ↑ x2) to generate x1 ⊕ x2 = (x1 ↑ (x1 + x2)) ↑ ((x1 + x2) ↑ x2)

DeMorgan’s theorem states that x1 + x2 = x1 ↑ x2; hence we can write x1 ⊕ x2 = (x1 ↑ (x1 ↑ x2)) ↑ ((x1 ↑ x2) ↑ x2)

Now we have a decomposition

x1 ⊕ x2 = (x1 ↑ g) ↑ (g ↑ x2) g = x1 ↑ x2

The corresponding circuit, which requires only four NAND gates, is given in Figure 4.26c.

Practical Issues Functional decomposition is a powerful technique for reducing the complexity of cir-

cuits. It can also be used to implement general logic functions in circuits that have built-in constraints. For example, in programmable logic devices (PLDs) that were introduced in Chapter 3 it is necessary to “fit” a desired logic circuit into logic blocks that are available on these devices. The available blocks are a target for decomposed subfunctions that may be used to realize larger functions.

A big problem in functional decomposition is finding the possible subfunctions. For functions of many variables, an enormous number of possibilities should be tried. This situation precludes attempts at finding optimal solutions. Instead, heuristic approaches that lead to acceptable solutions are used.

Full discussion of functional decomposition and factoring is beyond the scope of this book. An interested reader may consult other references [2–5]. Modern CAD tools use the concept of decomposition extensively.

4.6.3 Multilevel NAND and NOR Circuits

In section 2.7 we showed that two-level circuits consisting of AND and OR gates can be easily converted into circuits that can be realized with NAND and NOR gates, using the same gate arrangement. In particular, anAND-OR (sum-of-products) circuit can be realized

200 C H A P T E R 4 • Optimized Implementation of Logic Functions

as a NAND-NAND circuit, while an OR-AND (product-of-sums) circuit becomes a NOR- NOR circuit. The same conversion approach can be used for multilevel circuits. We will illustrate this approach by an example.

Example 4.9 Figure 4.27a gives a four-level circuit consisting of AND and OR gates. Let us first derive a functionally equivalent circuit that comprises only NAND gates. Each AND gate is converted to a NAND by inverting its output. Each OR gate is converted to a NAND by inverting its inputs. This is just an application of DeMorgan’s theorem, as illustrated in Figure 2.21a. Figure 4.27b shows the necessary inversions in blue. Note that an inversion is applied at both ends of a given wire. Now each gate becomes a NAND gate. This accounts for most of the inversions added to the original circuit. But, there are still four inversions that are not a part of any gate; therefore, they must be implemented separately. These inversions are at inputs x1, x5, x6, and x7 and at the output f . They can be implemented as two-input NAND gates, where the inputs are tied together. The resulting circuit is shown in Figure 4.27c.

A similar approach can be used to convert the circuit in Figure 4.27a into a circuit that comprises only NOR gates. An OR gate is converted to a NOR gate by inverting its output. An AND becomes a NOR if its inputs are inverted, as indicated in Figure 2.21b. Using this approach, the inversions needed for our sample circuit are shown in blue in Figure 4.28a. Then each gate becomes a NOR gate. The three inversions at inputs x2, x3, and x4 can be realized as two-input NOR gates, where the inputs are tied together. The resulting circuit is presented in Figure 4.28b.

It is evident that the basic topology of a circuit does not change substantially when converting from AND and OR gates to either NAND or NOR gates. However, it may be necessary to insert additional gates to serve as NOT gates that implement inversions not absorbed as a part of other gates in the circuit.

4.7 Analysis of Multilevel Circuits

The preceding section showed that it may be advantageous to implement logic functions using multilevel circuits. It also presented the most commonly used approaches for syn- thesizing functions in this way. In this section we will consider the task of analyzing an existing circuit to determine the function that it implements.

For two-level circuits the analysis process is simple. If a circuit has an AND-OR (NAND-NAND) structure, then its output function can be written in the SOP form by inspection. Similarly, it is easy to derive a POS expression for an OR-AND (NOR-NOR) circuit. The analysis task is more complicated for multilevel circuits because it is difficult to write an expression for the function by inspection. We have to derive the desired expression by tracing the circuit and determining its functionality. The tracing can be done either starting from the input side and working towards the output, or by starting at the output side and working back towards the inputs. At intermediate points in the circuit, it is necessary to evaluate the subfunctions realized by the logic gates.

4.7 Analysis of Multilevel Circuits 201

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

f

f

f

(a) Circuit with AND and OR gates

(b) Inversions needed to convert to NANDs

(c) NAND-gate circuit

Figure 4.27 Conversion to a NAND-gate circuit.

202 C H A P T E R 4 • Optimized Implementation of Logic Functions

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

� �

f

f

(a) Inversions needed to convert to NORs

(b) NOR-gate circuit

Figure 4.28 Conversion to a NOR-gate circuit.

Example 4.10 Figure 4.29 replicates the circuit from Figure 4.27a. To determine the function f imple- mented by this circuit, we can consider the functionality at internal points that are the outputs of various gates. These points are labeled P1 to P5 in the figure. The functions realized at these points are

P1 = x2x3 P2 = x5 + x6 P3 = x1 + P1 = x1 + x2x3

4.7 Analysis of Multilevel Circuits 203

� �

� �

� �

� �

� �

� �

� �

f

� �

� �

� �

� �

� �

Figure 4.29 Circuit for Example 4.10.

P4 = x4P2 = x4(x5 + x6) P5 = P4 + x7 = x4(x5 + x6) + x7

Then f can be evaluated as

f = P3P5 = (x1 + x2x3)(x4(x5 + x6) + x7)

Applying the distributive property to eliminate the parentheses gives

f = x1x4x5 + x1x4x6 + x1x7 + x2x3x4x5 + x2x3x4x6 + x2x3x7 Note that the expression represents a circuit comprising six AND gates, one OR gate, and 25 inputs. The cost of this two-level circuit is higher than the cost of the circuit in Figure 4.29, but the circuit has lower propagation delay.

Example 4.11In Example 4.7 we derived the circuit in Figure 4.25b. In addition to AND gates and OR gates, the circuit has some NOT gates. It is reproduced in Figure 4.30, and the internal points are labeled from P1 to P10 as shown. The following subfunctions occur

P1 = x1 + x2 + x5 P2 = x4 P3 = x3 P4 = x3P2 P5 = x4P3 P6 = P4 + P5 P7 = P1 P8 = P6

204 C H A P T E R 4 • Optimized Implementation of Logic Functions

� �

� �

� �

� �

���

� �

� �

� �

� �

� �

� �

� �

� �

� �

�

Figure 4.30 Circuit for Example 4.11.

P9 = P1P6 P10 = P7P8

We can derive f by tracing the circuit from the output towards the inputs as follows

f = P9 + P10 = P1P6 + P7P8 = (x1 + x2 + x5)(P4 + P5) + P1P6 = (x1 + x2 + x5)(x3P2 + x4P3) + x1x2x5P4P5 = (x1 + x2 + x5)(x3x4 + x4x3) + x1x2x5(x3 + P2)(x4 + P3) = (x1 + x2 + x5)(x3x4 + x3x4) + x1x2x5(x3 + x4)(x4 + x3) = x1x3x4 + x1x3x4 + x2x3x4 + x2x3x4 + x5x3x4 + x5x3x4 +

x1x2x5x3x4 + x1x2x5x4x3 This is the same expression as stated in Example 4.7.

Example 4.12 Circuits based on NAND and NOR gates are slightly more difficult to analyze because each gate involves an inversion. Figure 4.31a depicts a simple NAND-gate circuit that illustrates the effect of inversions. We can convert this circuit into a circuit with AND and OR gates using the reverse of the approach described in Example 4.9. Bubbles that denote inversions can be moved, according to DeMorgan’s theorem, as indicated in Figure 4.31b. Then the circuit can be converted into the circuit in part (c) of the figure, which consists of AND and

4.7 Analysis of Multilevel Circuits 205

� �

� �

� �

� �

� �

f

� �

� �

� �

� �

� �

� �

� �

� �

f

� �

� �

� �

f � �

(c) Circuit with AND and OR gates

(b) Moving bubbles to convert to ANDs and ORs

(a) NAND-gate circuit

� �

Figure 4.31 Circuit for Example 4.12.

OR gates. Observe that in the converted circuit, the inputs x3 and x5 are complemented. From this circuit the function f is determined as

f = (x1x2 + x3)x4 + x5 = x1x2x4 + x3x4 + x5

It is not necessary to convert a NAND circuit into a circuit with AND and OR gates to determine its functionality. We can use the approach from Examples 4.10 and 4.11 to

206 C H A P T E R 4 • Optimized Implementation of Logic Functions

derive f as follows. Let P1, P2, and P3 label the internal points as shown in Figure 4.31a. Then

P1 = x1x2 P2 = P1x3 P3 = P2x4

f = P3x5 = P3 + x5 = P2x4 + x5 = P2x4 + x5 = P1x3x4 + x5 = (P1 + x3)x4 + x5 = (x1x2 + x3)x4 + x5 = (x1x2 + x3)x4 + x5 = x1x2x4 + x3x4 + x5

Example 4.13 The circuit in Figure 4.32 consists of NAND and NOR gates. It can be analyzed as follows.

P1 = x2x3 P2 = x1P1 = x1 + P1 P3 = x3x4 = x3 + x4 P4 = P2 + P3

f = P4 + x5 = P4x5 = P2 + P3 · x5

� �

� �

� �

� �

� �

�

� �

� �

� �

� �

Figure 4.32 Circuit for Example 4.13.

4.8 Cubical Representation 207

= (P2 + P3)x5 = (x1 + P1 + x3 + x4)x5 = (x1 + x2x3 + x3 + x4)x5 = (x1 + x2 + x3 + x4)x5 = x1x5 + x2x5 + x3x5 + x4x5

Note that in deriving the second to the last line, we used property 16a in section 2.5 to simplify x2x3 + x3 into x2 + x3.

Analysis of circuits is much simpler than synthesis. With a little practice one can develop an ability to easily analyze even fairly complex circuits.

We have now covered a considerable amount of material on synthesis and analysis of logic functions. We have used the Karnaugh map as a vehicle for illustrating the concepts involved in finding optimal implementations of logic functions. We have also shown that logic functions can be realized in a variety of forms, both with two levels of logic and with multiple levels. In a modern design environment, logic circuits are synthesized using CAD tools, rather than by hand. The concepts that we have discussed in this chapter are quite general; they are representative of the strategies implemented in CAD algorithms. As we have said before, the Karnaugh map scheme for representing logic functions is not appropriate for use in CAD tools. In the next section we discuss an alternative representation of logic functions, which is suitable for use in CAD algorithms.

4.8 Cubical Representation

The Karnaugh map is an excellent vehicle for illustrating concepts, and it is even useful for manual design if the functions have only a few variables. To deal with larger functions it is necessary to have techniques that are algebraic, rather than graphical, which can be applied to functions of any number of variables.

Many algebraic optimization techniques have been developed. We will not pursue these techniques in great detail, but we will attempt to provide the reader with an appreciation of the tasks involved. This helps in gaining an understanding of what the CAD tools can do and what results can be expected from them. The approaches that we will present make use of a cubical representation of logic functions.

4.8.1 Cubes and Hypercubes

So far in this book, we have encountered four different forms for representing logic func- tions: truth tables, algebraic expressions, Venn diagrams, and Karnaugh maps. Another possibility is to map a function of n variables onto an n-dimensional cube.

208 C H A P T E R 4 • Optimized Implementation of Logic Functions

Two-Dimensional Cube A two-dimensional cube is shown in Figure 4.33. The four corners in the cube are

called vertices, which correspond to the four rows of a truth table. Each vertex is identified by two coordinates. The horizontal coordinate is assumed to correspond to variable x1, and vertical coordinate to x2. Thus vertex 00 is the bottom-left corner, which corresponds to row 0 in the truth table. Vertex 01 is the top-left corner, where x1 = 0 and x2 = 1, which corresponds to row 1 in the truth table, and so on for the other two vertices.

We will map a function onto the cube by indicating with blue circles those vertices for which f = 1. In Figure 4.33 f = 1 for vertices 01, 10, and 11. We can express the function as a set of vertices, using the notation f = {01, 10, 11}. The function f is also shown in the form of a truth table in the figure.

An edge joins two vertices for which the labels differ in the value of only one variable. Therefore, if two vertices for which f = 1 are joined by an edge, then this edge represents that portion of the function just as well as the two individual vertices. For example, f = 1 for vertices 10 and 11. They are joined by the edge that is labeled 1x. It is customary to use the letter x to denote the fact that the corresponding variable can be either 0 or 1. Hence 1x means that x1 = 1, while x2 can be either 0 or 1. Similarly, vertices 01 and 11 are joined by the edge labeled x1, indicating that x1 can be either 0 or 1, but x2 = 1. The reader must not confuse the use of the letter x for this purpose, in contrast to the subscripted use where x1 and x2 refer to the variables.

Two vertices being represented by a single edge is the embodiment of the combining property 14a from section 2.5. The edge 1x is the logical sum of vertices 10 and 11. It essentially defines the term x1, which is the sum of minterms x1x2 and x1x2. The property 14a indicates that

x1x2 + x1x2 = x1 Therefore, finding edges for which f = 1 is equivalent to applying the combining property. Of course, this is also analogous to finding pairs of adjacent cells in a Karnaugh map for which f = 1.

The edges 1x and x1 define fully the function in Figure 4.33; hence we can represent the function as f = {1x, x1}. This corresponds to the logic expression

f = x1 + x2 which is also obvious from the truth table in the figure.