Book Fire Online by http://bookfire.net

Focus on Karnaugh Maps

3A.1 Introduction

In this chapter, we focused on Boolean expressions and their relationship to digital circuits. Minimizing these circuits helps reduce the number of components in the actual physical implementation. Having fewer components allows the circuitry to operate faster.

Reducing Boolean expressions can be done using Boolean identities; however, using identities can be very difficult because no rules are given on how or when to use the identities, and there is no well-defined set of steps to follow. In one respect, minimizing Boolean expressions is very much like doing a proof: You know when you are on the right track, but getting there can sometimes be frustrating and time-consuming. In this appendix, we introduce a systematic approach for reducing Boolean expressions.

3A.2 Description of Kmaps and Terminology

Karnaugh maps, or Kmaps, are a graphical way to represent Boolean functions. A map is simply a table used to enumerate the values of a given Boolean expression for different input values. The rows and columns correspond to the possible values of the function's inputs. Each cell represents the outputs of the function for those possible inputs.

If a product term includes all of the variables exactly once, either complemented or not complemented, this product term is called a minterm. For example, if there are two input values, x and y, there are four minterms, and xy, which represent all of the possible input combinations for the function. If the input variables are x, y, and z, then there are eight minterms: and xyz.

As an example, consider the Boolean function . Possible inputs for x and y are shown in Figure 3A.1.

Figure 3A.1: Minterms for Two Variables

The minterm represents the input pair (0,0). Similarly, the minterm represents (0,1), the minterm represents (1,0), and xy represents (1,1).

The minterms for three variables, along with the input values they represent, are shown in Figure 3A.2.

Figure 3A.2: Minterms for Three Variables

A Kmap is a table with a cell for each minterm, which means it has a cell for each line of the truth table for the function. Consider the function F(x,y) = xy and its truth table, as seen in Example 3A.1.

Example 3A.1:

F(x,y) = xy

The corresponding Kmap is:

Notice that the only cell in the map with a value of one occurs when x = 1 and y = 1, the same values for which xy = 1. Let's look at another example, F(x,y) = x + y.

Example 3A.2:

F(x,y) = x + y

Three of the minterms in Example 3A.2 have a value of 1, exactly the minterms for which the input to the function gives us a 1 for the output. To assign 1s in the Kmap, we simply place 1s where we find corresponding 1s in the truth table. We can express the function F(x,y) = x + y as the logical OR of all minterms for which the minterm has a value of 1. Then F(x,y) can be represented by the expression Obviously, this expression is not minimized (we already know this function is simply x + y). We can minimize using Boolean identities:

How did we know to add in an extra xy term? Algebraic simplification using Boolean identities can be very tricky. This is where Kmaps can help.

3A.3 Kmap Simplification for Two Variables

In the previous reduction for the function F(x,y), the goal was to group terms so we could factor out variables. We added the xy to give us a term to combine with the . This allowed us to factor out the y, leaving , which reduces to 1. However, if we use Kmap simplification, we won't have to worry about which terms to add or which Boolean identity to use. The maps take care of that for us.

Let's look at the Kmap for F(x,y) = x + y again in Figure 3A.3.

Figure 3A.3: Kmap for F(x,y) = x + y

To use this map to reduce a Boolean function, we simply need to group ones. This grouping is very similar to how we grouped terms when we reduced using Boolean identities, except we must follow specific rules. First, we group only ones. Second, we can group ones in the Kmap if the ones are in the same row or in the same column, but they cannot be on the diagonal (i.e., they must be adjacent cells). Third, we can group ones if the total number in the group is a power of 2. The fourth rule specifies we must make the groups as large as possible. As a fifth and final rule, all ones must be in a group (even if some are in a group of one). Let's examine some correct and incorrect groupings, as shown in Figures 3A.4 through 3A.7.

Figure 3A.4: Groups Contain Only 1s

Figure 3A.5: Groups Cannot Be Diagonal

Figure 3A.6: Groups Must Be Powers of 2

Figure 3A.7: Groups Must Be as Large as Possible

Notice in Figure 3A.6(b) and 3A.7(b) that one 1 belongs to two groups. This is the map equivalent of adding the term xy to the Boolean function, as we did when we were performing simplification using identities. The xy term in the map will be used twice in the simplification procedure.

To simplify using Kmaps, first create the groups as specified by the rules above. After you have found all groups, examine each group and discard the variable that differs within each group. For example, Figure 3A.7(b) shows the correct grouping for F(x,y) = x + y. Let's begin with the group represented by the second row (where x = 1). The two minterms are and xy. This group represents the logical OR of these two terms, or + xy. These terms differ in y, so y is discarded, leaving only x. (We can see that if we use Boolean identities, this would reduce to the same value. The Kmap allows us to take a shortcut, helping us to automatically discard the correct variable.) The second group represents + xy. These differ in x, so x is discarded, leaving y. If we OR the results of the first group and the second group, we have x + y, which is the correct reduction of the original function, F.

3A.4 Kmap Simplification for Three Variables

Kmaps can be applied to expressions of more than two variables. In this focus section, we show three-variable and four-variable Kmaps. These can be extended for situations that have five or more variables. We refer you to Maxfield (1995) in the "Further Reading" section of this chapter for thorough and enjoyable coverage of Kmaps.

You already know how to set up Kmaps for expressions involving two variables. We simply extend this idea to three variables, as indicated by Figure 3A.8.

Figure 3A.8: Minterms and Kmap Format for Three Variables

The first difference you should notice is that two variables, y and z, are grouped together in the table. The second difference is that the numbering for the columns is not sequential. Instead of labeling the columns as 00, 01, 10, 11 (a normal binary progression), we have labeled them 00, 01, 11, 10. The input values for the Kmap must be ordered so that each minterm differs in only one variable from each neighbor. By using this order (for example 01 followed by 11), the corresponding minterms, and , differ only in the y variable. Remember, to reduce, we need to discard the variable that is different. Therefore, we must ensure that each group of two minterms differs in only one variable.

The largest groups we found in our two-variable examples were composed of two 1s. It is possible to have groups of four or even eight 1s, depending on the function. Let's look at a couple of examples of map simplification for expressions of three variables.

Example 3A.3:

We again follow the rules for making groups. You should see that you can make groups of two in several ways. However, the rules stipulate we must create the largest groups whose sizes are powers of two. There is one group of four, so we group these as follows:

It is not necessary to create additional groups of two. The fewer groups you have, the fewer terms there will be. Remember, we want to simplify the expression, and all we have to do is guarantee that every 1 is in some group.

How, exactly, do we simplify when we have a group of four 1s? Two 1s in a group allowed us to discard one variable. Four 1s in a group allows us to discard two variables: The two variables in which all four terms differ. In the group of four from the preceding example, we have the following minterms: and xyz. These all have z in common, but the x and y variables differ. So we discard x and y, leaving us with F(x,y,z) = z as the final reduction. To see how this parallels simplification using Boolean identities, consider the same reduction using identities. Note that the function is represented originally as the logical OR of the minterms with a value of 1.

The end result using Boolean identities is exactly the same as the result using map simplification.

From time to time, the grouping process can be a little tricky. Let's look at an example that requires more scrutiny.

Example 3A.4:

This is a tricky problem for two reasons: We have overlapping groups, and we have a group that "wraps around." The leftmost 1s in the first column can be grouped with the rightmost 1s in the last column, because the first and last columns are logically adjacent (envision the map as being drawn on a cylinder). The first and last rows of a Kmap are also logically adjacent, which becomes apparent when we look at four-variable maps in the next section.

The correct groupings are as follows:

The first group reduces to (this is the only term the four have in common), and the second group reduces to , so the final minimized function is .

Example 3A.5:

A Kmap with all 1s

Suppose we have the following Kmap:

The largest group of 1s we can find is a group of eight, which puts all of the 1s in the same group. How do we simplify this? We follow the same rules we have been following. Remember, groups of two allowed us to discard one variable, and groups of four allowed us to discard two variables; therefore, groups of eight should allow us to discard three variables. But that's all we have! If we discard all the variables, we are left with F(x,y,z) = 1. If you examine the truth table for this function, you will see that we do indeed have a correct simplification.

3A.5 Kmap Simplification for Four Variables

We now extend the map simplification techniques to four variables. Four variables give us 16 minterms, as shown in Figure 3A.9. Notice the special order of 11 followed by 10 applies for the rows as well as the columns.

Figure 3A.9: Minterms and Kmap Format for Four Variables

Example 3A.6 illustrates the representation and simplification of a function with four variables. We are only concerned with the terms that are 1s, so we omit entering the 0s into the map.

Example 3A.6:

Group 1 is a "wrap-around" group, as we saw previously. Group 3 is easy to find as well. Group 2 represents the ultimate wrap-around group: It consists of the 1s in the four corners. Remember, these corners are logically adjacent. The final result is that F reduces to three terms, one from each group: (from Group 1), (from Group 2), and (from Group 3). The final reduction for F is then .

Occasionally, there are choices to make when performing map simplification. Consider Example 3A.7.

Example 3A.7:

A Choice of Groups

The first column should clearly be grouped. Also, the and terms should be grouped. However, we have a choice as to how to group the term. It could be grouped with or with (as a wrap-around). These two solutions are indicated below.

The first map simplifies to . The second map simplifies to . The last terms are different. F₁ and F₂, however, are equivalent. We leave it up to you to produce the truth tables for F₁ and F₂ to check for equality. They both have the same number of terms and variables as well. If we follow the rules, Kmap minimization results in a minimized function (and thus a minimal circuit), but these minimized functions need not be unique in representation.

Before we move on to the next section, here are the rules for Kmap simplification.

The groups can only contain 1s; no 0s.
Only 1s in adjacent cells can be grouped; diagonal grouping is not allowed.
The number of 1s in a group must be a power of 2.
The groups must be as large as possible while still following all rules.
All 1s must belong to a group, even if it is a group of one.
Overlapping groups are allowed.
Wrap around is allowed.
Use the fewest number of groups possible.

Using these rules, let's complete one more example for a four-variable function. Example 3A.8 shows several applications of the various rules.

Example 3A.8:

In this example, we have one group with a single element. Note there is no way to group this term with any others if we follow the rules. The function represented by this Kmap simplifies to .

If you are given a function that is not written as a sum of minterms, you can still use Kmaps to help minimize the function. However, you have to use a procedure that is somewhat the reverse of what we have been doing to set up the Kmap before reduction can occur. Example 3A.9 illustrates this procedure.

Example 3A.9:

A Function Not Represented as a Sum of Minterms

Suppose you are given the function . The last two terms are minterms, and we can easily place 1s in the appropriate positions in the Kmap. However the term is not a minterm. Suppose this term were the result of a grouping you had performed on a Kmap. The term that was discarded was the z term, which means this term is equivalent to the two terms . You can now use these two terms in the Kmap, because they are both minterms. We now get the following Kmap:

So we know the function simplifies to .

3A.6 Don't Care Conditions

There are certain situations where a function may not be completely specified, meaning there may be some inputs that are undefined for the function. For example, consider a function with 4 inputs that act as bits to count, in binary, from 0 to 10 (decimal). We use the bit combinations 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, and 1010. However, we do not use the combinations 1011, 1100, 1101, 1110, and 1111. These latter inputs would be invalid, which means if we look at the truth table, these values wouldn't be either 0 or 1. They should not be in the truth table at all.

We can use these don't care inputs to our advantage when simplifying Kmaps. Because they are input values that should not matter (and should never occur), we can let them have values of either 0 or 1, depending on which helps us the most. The basic idea is to set these don't care values in such a way that they either contribute to make a larger group, or they don't contribute at all. Example 3A.10 illustrates this concept.

Example 3A.10:

Don't Care Conditions

Don't care values are typically indicated with an "X" in the appropriate cell. The following Kmap shows how to use these values to help with minimization. We treat the don't care values in the first row as 1s to help form a group of four. The don't care values in rows 01 and 11 are treated as 0s. This reduces to .

There is another way these values can be grouped:

Using the above groupings, we end up with a simplification of F2(w, x, y, z) = . Notice that in this case, F₁ and F₂ are not equal. However, if you create the truth tables for both functions, you should see that they are not equal only in those values for which we "don't care."

3A.7 Summary

In this section we have given a brief introduction to Kmaps and map simplification. Using Boolean identities for reduction is awkward and can be very difficult. Kmaps, on the other hand, provide a precise set of steps to follow to find the minimal representation of a function, and thus the minimal circuit that function represents.

Exercises

Write a simplified expression for the Boolean function defined by each of the following Kmaps:
1. Hints and Answers
2. Hints and Answers
Create the Kmaps and then simplify for the following functions:
Write a simplified expression for the Boolean function defined by each of the following Kmaps:
Create the Kmaps and then simplify for the following functions:
Hints and Answers Given the following Kmap, show algebraically (using Boolean identities) how the four terms reduce to one term.
Write a simplified expression for the Boolean function defined by each of the following Kmaps:
1. Hints and Answers