Digital electronics problems

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

� �

� �

� �

� �