3.6 Grouping and reading terms

Why this matters

A truth table tells you what a circuit must do, but it does not tell you how to build it cheaply. A K-map is the fastest hand method for turning a truth table into a small sum of products: a few AND gates feeding one OR gate. You will use the same skill again in Chapter 5, where it shrinks the next-state logic of a state machine.

Learning goals

Draw groups of 1s on a map that obey the grouping rules, including groups that wrap around an edge or use all four corners.
Read the product term that a group stands for.
Explain why a larger group gives a shorter term.
Decide whether a proposed group is valid, and name the rule it breaks.
Recognize when a function has more than one minimal sum of products.

Intuition first

Suppose a function is 1 for the input row where A, B and C are all 1, and also for the row where A and B are 1 but C is 0. Those two rows differ only in C. So the function is 1 when A and B are both 1, and C does not matter. You can write the pair of rows as the single term $AB$ , with C gone. That is the uniting theorem of Definition 3.4.5, applied to two rows.

That is the whole idea of grouping. Whenever two 1-rows differ in exactly one variable, they merge into one term that leaves that variable out. A K-map is a layout of the truth table chosen so that rows differing in one variable sit next to each other, and your eye can find such pairs. A bigger group is the same trick repeated: four cells that all agree on everything except two variables lose both of them.

If you write software, you have seen the same move in a branch where both sides do the same thing. if (c) x = a; else x = a; is just x = a, and the test on c disappears. The analogy breaks in one place: the two branches of an if/else never overlap, but groups on a map may, because OR does not mind covering a 1 twice.

This section assumes you can already fill in a map from a truth table. The previous section built the maps (see Definition 3.5.2 and Example 3.5.1), with the course's Gray-code layout; here we only draw on them.

What a group is

Definition 3.6.1(group).

A group on a K-map is a rectangle of cells that are all 1 (the next section lets don't-care cells join a group too, but a group never holds a 0), whose width and height are each a power of two (1, 2 or 4 cells). So a group holds 1, 2, 4, 8 or 16 cells. The rectangle may wrap around the left and right edges, the top and bottom edges, or both at once.

Wrapping is not a trick. The columns are in Gray order (Definition 3.5.1), so the last column differs from the first in a single variable, exactly as every other pair of neighbors does. The same is true of the top and bottom rows. The four corners of a four-variable map form a group. Each corner is a neighbor of the corner across the left and right edges and of the corner across the top and bottom edges, so the four make a 2×2 block that wraps both ways.

Definition 3.6.2(the term of a group).

The term of a group is the product of the variables that have the same value in every cell of the group. A variable that is 1 throughout appears plain. A variable that is 0 throughout appears with a bar. A variable that takes both values inside the group drops out.

This is why larger groups are better. Each time a group doubles in size, one more variable changes inside it and one more variable drops out of the term. A group of $2^k$ cells on a map of $n$ variables has a term of $n-k$ variables. One cell gives a term that uses every variable, and a group that fills the whole map gives the constant 1.

The rest of the rules say how to choose among groups.

A group never contains a 0. Until the next section every cell in a group is a 1; Definition 3.7.1 adds don't-care cells, which may be in a group when that helps.
Make groups as large as you can. A group that could be doubled should be.
Cover every 1 at least once. Groups may overlap: a cell in two groups is fine, because OR does not mind hearing the same 1 twice.
Use a single cell on its own only when no neighbor is 1.
Use as few groups as you can. If every 1 in some group is already covered by other groups, leave that group out.

The function is the sum, an OR, of the terms of the groups. A sum of products with as few terms as possible, and then as few literals as possible, is the one we want:

Definition 3.6.3(minimal sum of products).

A sum of products is minimal when no other sum of products for the same function has fewer terms, and among those with the same number of terms, none has fewer variables written in total (fewer literals).

This book counts terms first and literals second.

A first example: majority

Example 3.6.1(majority of three inputs).

The majority function F is 1 when at least two of A, B and C are 1. Figure 3.6.1 shows its map. Each 1 has a neighbor that is also 1, so no 1 stands alone, and we look for the largest rectangles.

The vertical pair in the column where A=1 and B=1 holds two cells, with C changing from 0 to 1. A and B are 1 in both cells, so the term is $AB$ . The horizontal pair in the row where C=1 and the columns where B=1 has A changing and B and C both 1, giving $BC$ . The horizontal pair in the row where C=1 and the columns where A=1 has B changing, giving $AC$ .

All three groups contain the cell where A, B and C are all 1. That is allowed, and it is what lets every group be as large as possible. No group can be bigger. A group of four on this map is either a whole row or a 2×2 block. The row where C is 1 has a 0 in it, and a 2×2 block would need two 1s in the row where C is 0, which has only one.

F = $AB + BC + AC$

$AB$ vertical pair: the column where A=1 and B=1 (2 cells)
$BC$ horizontal pair: the row where C=1 and the columns where B=1 (2 cells)
$AC$ horizontal pair: the row where C=1 and the columns where A=1 (2 cells)

Karnaugh map of F: columns AB, rows C; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
C=0	0	0	1	0
C=1	0	1	1	1

Groups drawn:

A and B: vertical pair in the column where A=1 and B=1; 2 cells.
B and C: horizontal pair in the row where C=1 and the columns where B=1; 2 cells.
A and C: horizontal pair in the row where C=1 and the columns where A=1; 2 cells.

Figure 3.6.1. Majority of three inputs, drawn with brackets. Every group is a pair, and all three contain the cell where A, B and C are all 1.

A harder map: the rules map

Look at Figure 3.6.2 in the next example before reading on. Three 1s sit side by side in the row where C and D are both 1. Is circling all three a valid group? Yes, they are in one row and all three are 1 No, a group must have a power-of-two number of cells

Example 3.6.2(every rule at once).

The map in Figure 3.6.2 has nine 1s. A tempting first move is to circle the three 1s in the row where C and D are both 1. The red dashed box is that proposal. It is not a group, because its width is three cells, and three is not a power of two. If you tried to read a term from it, you would get $CD$ , because A and B both change across the three cells. But $CD$ is 1 in all four cells of that row, including the cell where A, B, C and D are 0, 0, 1, 1, and F is 0 there.

Not a valid group: it has 3 cells; a group has 1, 2, 4, 8 or 16.

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
CD=00	1	0	0	1
CD=01	0	1	1	0
CD=11	0	1	1	1
CD=10	1	0	0	1

Not valid groups, drawn dashed in red:

it has 3 cells; a group has 1, 2, 4, 8 or 16.

Figure 3.6.2. Three 1s in a row. The red dashed box is not a group: its width is three cells.

So we look for rectangles that are legal. The 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11 is one: A changes between its two columns and C changes between its two rows, while B and D stay 1, so its term is $BD$ . The four corners in rows CD=10 and 00, columns AB=10 and 00 is another group of four: A and C change, B and D stay 0, so the term is $\overline{B}\,\overline{D}$ . The two 1s at the ends of the row where C and D are both 0 also form a valid group by themselves, the horizontal pair wrapping around the left and right edges in row CD=00, columns AB=10 and 00. But the corner group already contains both of those cells and is larger, so the pair would be a wasted term.

That leaves one 1 uncovered: the cell where A, B, C and D are 1, 0, 1, 1. A useful order is to start with a 1 that can be grouped in only one way, because that group must be in every answer. This 1 is not one of those: it has two good neighbors, and either one gives a pair. Taking the horizontal pair in row CD=11, columns AB=11 and 10 makes A, C and D the fixed 1s and B the variable that changes, so the term is $ACD$ . Taking the vertical pair in rows CD=11 and 10, column AB=10 instead fixes A and C at 1 and B at 0 and lets D change, so the term is $A\overline{B}C$ . Both pairs have three variables, and each is as small as it can be.

F = $BD + \overline{B}\,\overline{D} + ACD$

$BD$ 2-by-2 square: rows 01 and 11, columns 01 and 11
$\overline{B}\,\overline{D}$ four corners: rows 10 and 00, columns 10 and 00
$ACD$ horizontal pair: row 11, columns 11 and 10 (2 cells)

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
CD=00	1	0	0	1
CD=01	0	1	1	0
CD=11	0	1	1	1
CD=10	1	0	0	1

Groups drawn:

B and D: 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11; 4 cells.
not B and not D: four corners in rows CD=10 and 00, columns AB=10 and 00; 4 cells.
A and C and D: horizontal pair in row CD=11, columns AB=11 and 10; 2 cells.

Figure 3.6.3. The rules map with the pair in which B changes.

F = $BD + \overline{B}\,\overline{D} + A\overline{B}C$

$BD$ 2-by-2 square: rows 01 and 11, columns 01 and 11
$\overline{B}\,\overline{D}$ four corners: rows 10 and 00, columns 10 and 00
$A\overline{B}C$ vertical pair: rows 11 and 10, column 10 (2 cells)

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
CD=00	1	0	0	1
CD=01	0	1	1	0
CD=11	0	1	1	1
CD=10	1	0	0	1

Groups drawn:

B and D: 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11; 4 cells.
not B and not D: four corners in rows CD=10 and 00, columns AB=10 and 00; 4 cells.
A and not B and C: vertical pair in rows CD=11 and 10, column AB=10; 2 cells.

Figure 3.6.4. The same map with the other pair, in which D changes.

This is one of 2 minimal sum-of-products forms of F; all 2 use 3 terms and 7 literals. Any of them is a correct answer.

Neither answer is more correct than the other. When someone asks for "the minimal form" of this function, the honest reply is that there are two, and either is right. Say "a minimal form" in your own answers, and check whether a leftover 1 could be paired in more than one equally good way.

Starting from an expression

Sometimes you are not given a map at all. You have a sum of products that someone wrote down, and you want to know whether it is as small as it could be. You can draw it on a map: each product term marks the block of cells where that term is 1, and you OR the blocks together.

Example 3.6.3(shrinking four terms to two).

Take $\overline{A}D + BD + \overline{B}C + A\overline{B}D$ . Each product marks the block of cells where it is 1, and the map is the OR of the four blocks. $\overline{A}D$ marks the 2-by-2 square in rows CD=01 and 11, columns AB=00 and 01. $BD$ marks the 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11. $\overline{B}C$ marks the 2-by-2 square wrapping around the left and right edges in rows CD=11 and 10, columns AB=10 and 00. $A\overline{B}D$ marks the vertical pair in rows CD=01 and 11, column AB=10. Together they give the 1s in Figure 3.6.5.

Now look for the biggest rectangles. The two rows where D is 1 are entirely 1, so together they form a group of eight, with A, B and C all changing and D fixed at 1. Its term is just D. Only two 1s are left over: the cells where B is 0, C is 1 and D is 0. A takes both values there, so they are neighbors across the left and right edges. Those two cells and the two cells next to them in the group of eight make a 2-by-2 square wrapping around the left and right edges. Overlapping is allowed, and the block reads as $\overline{B}C$ : B is 0 in both columns, C is 1 in both rows, and A and D change.

F = $D + \overline{B}C$

$D$ group of eight: rows 01 and 11 (8 cells)
$\overline{B}C$ 2-by-2 square, wraps left and right: rows 11 and 10, columns 10 and 00

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
CD=00	0	0	0	0
CD=01	1	1	1	1
CD=11	1	1	1	1
CD=10	1	0	0	1

Groups drawn:

D: group of eight in rows CD=01 and 11; 8 cells.
not B and C: 2-by-2 square wrapping around the left and right edges in rows CD=11 and 10, columns AB=10 and 00; 4 cells.

Figure 3.6.5. Four terms collapse to two: a group of eight in the two rows where D is 1, and a group of four that wraps around the left and right edges in the columns where B is 0 and the rows where C is 1.

The two expressions describe the same function, and the check below confirms it: $\overline{A}D +$ $BD +$ $\overline{B}C +$ $A\overline{B}D$ $= D +$ $\overline{B}C$ . We went from four terms and nine literals to two terms and three.

Course conventions

How CSE 369 writes this

The K-map layout is the course's: for four variables the columns are AB and the rows are CD, both in the order 00, 01, 11, 10. For three variables the columns are AB and the rows are C; the course also shows an alternate layout with columns BC and rows A, which some textbooks use as their default. A bracket along an edge marks where a variable is 1, and the group outlines are rounded. NOT is always an overbar, never a prime. If a textbook or website puts the variables on different edges, or in a different order, its cells sit in different places, so read its axis labels before comparing its groups with these.

ReadingBeyond four variables

By hand, maps stop being practical above four variables. A program can do the same job systematically. The classic exact method, Quine–McCluskey, lists every group that cannot be made any larger and then chooses the cheapest set of them that covers every 1. The checker behind this book's maps uses it, which is how the book knows that a form it calls minimal is minimal. Synthesis tools use faster methods built on the same idea. Running it by hand is not something this book asks of you.

Pitfalls

Common pitfall

Circling three cells, or any number that is not a power of two. Split them into groups of 1, 2, 4 or 8, and let the groups overlap if they need to.
Treating the edges of the map as walls. The left and right edges are neighbors, and so are the top and bottom. A group you missed because of this leaves you with extra terms.
Writing the variables that change instead of the ones that stay fixed. The term keeps what is constant across the group, and it drops everything that varies.
Forgetting a bar. A variable that is 0 in every cell of the group appears complemented.
Including a 0 to make a group bigger. Every cell in a group must be 1 (or, from the next section, a don't care).
Calling your answer the minimal form when a different answer of the same size exists.

Check your understanding

Take the quiz (6 questions)

Exercises

Exercise 3.6.1

The map below is for a function F of three variables. Find the groups that give the fewest terms, and write the sum of products they give.

Figure 3.6.6. A three-variable map with no groups drawn.

Hint

One of the groups is not a rectangle until you let the map wrap. Look at the left and right edges.

Solution

The map has four 1s. The horizontal pair wrapping around the left and right edges in row C=0, columns AB=10 and 00 works because the left and right edges are neighbors. In it A changes while B and C are 0, so its term is $\overline{B}\,\overline{C}$ . The 1 where A, B and C are all 1 has only one neighbor that is 1, the cell next to it in the same column, so it can pair only that way: the vertical pair in column AB=11 has the term $AB$ . These two groups cover all four 1s, and no group of four exists, because the row where C is 1 has a single 1 and the row where C is 0 has a 0. A third valid pair, the horizontal pair in row C=0, columns AB=11 and 10, also exists, but both of its cells are already covered, so adding its term $A\overline{C}$ would only add a term.

F = $\overline{B}\,\overline{C} + AB$

$\overline{B}\,\overline{C}$ horizontal pair, wraps left and right: the row where C=0 and the columns where B=0 (2 cells)
$AB$ vertical pair: the column where A=1 and B=1 (2 cells)

Karnaugh map of F: columns AB, rows C; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
C=0	1	0	1	1
C=1	0	0	1	0

Groups drawn:

not B and not C: horizontal pair wrapping around the left and right edges in the row where C=0 and the columns where B=0; 2 cells.
A and B: vertical pair in the column where A=1 and B=1; 2 cells.

Figure 3.6.7. The wrapped pair and the vertical pair.

Tags: Warm-upKarnaugh maps

Exercise 3.6.2

A classmate circles three 1s as a single group on the map below. Say which rule the circle breaks, then give a correct cover of every 1 with as few terms as possible.

Not a valid group: it has 3 cells; a group has 1, 2, 4, 8 or 16.

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=01	AB=11
CD=00	1	1
CD=01	1	1
CD=11	1	1
CD=10	0	0

Not valid groups, drawn dashed in red:

it has 3 cells; a group has 1, 2, 4, 8 or 16.

Figure 3.6.8. The proposed group is drawn dashed in red.

Hint

Count the cells, and ask whether that number is allowed. After that, look for the largest rectangle that covers each of the 1s.

Solution

The circle holds three cells in a column, and a group must be a rectangle with a power-of-two width and height. Three is not a power of two. All six 1s are in the two columns where B is 1. The 2-by-2 square in rows CD=00 and 01, columns AB=01 and 11 is the group for $B\overline{C}$ . The 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11 is the group for $BD$ . The two squares share one row, and overlapping is allowed.

F = $B\overline{C} + BD$

$B\overline{C}$ 2-by-2 square: rows 00 and 01, columns 01 and 11
$BD$ 2-by-2 square: rows 01 and 11, columns 01 and 11

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=01	AB=11
CD=00	1	1
CD=01	1	1
CD=11	1	1
CD=10	0	0

Groups drawn:

B and not C: 2-by-2 square in rows CD=00 and 01, columns AB=01 and 11; 4 cells.
B and D: 2-by-2 square in rows CD=01 and 11, columns AB=01 and 11; 4 cells.

Figure 3.6.9. Two squares that overlap on one row.

Tags: StandardKarnaugh maps

Exercise 3.6.3

Find a minimal sum of products for $\overline{A}\,\overline{C} +$ $A\overline{B}\,\overline{D} +$ $BCD +$ $\overline{A}BD$ . Start by marking each product on a four-variable map.

Hint

Mark the products one at a time. Then ask of each block of 1s whether every cell in it is already covered by the others.

Solution

Each product marks a block of cells. $\overline{A}\,\overline{C}$ marks the 2-by-2 square in rows CD=00 and 01, columns AB=00 and 01. $A\overline{B}\,\overline{D}$ marks the vertical pair wrapping around the top and bottom edges in rows CD=10 and 00, column AB=10. $BCD$ marks the horizontal pair in row CD=11, columns AB=01 and 11. $\overline{A}BD$ marks the vertical pair in rows CD=01 and 11, column AB=01. The last block adds nothing: one of its two cells lies in the first block and the other lies in the third. Leave that term out, as rule 5 says. What remains is $\overline{A}\,\overline{C} + A\overline{B}\,\overline{D} + BCD$ . Each of its three groups covers a 1 that no other group covers, so none can be dropped, and none can be made larger.

F = $\overline{A}\,\overline{C} + A\overline{B}\,\overline{D} + BCD$

$\overline{A}\,\overline{C}$ 2-by-2 square: rows 00 and 01, columns 00 and 01
$A\overline{B}\,\overline{D}$ vertical pair, wraps top and bottom: rows 10 and 00, column 10 (2 cells)
$BCD$ horizontal pair: row 11, columns 01 and 11 (2 cells)

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
CD=00	1	1	0	1
CD=01	1	1	0	0
CD=11	0	1	1	0
CD=10	0	0	0	1

Groups drawn:

not A and not C: 2-by-2 square in rows CD=00 and 01, columns AB=00 and 01; 4 cells.
A and not B and not D: vertical pair wrapping around the top and bottom edges in rows CD=10 and 00, column AB=10; 2 cells.
B and C and D: horizontal pair in row CD=11, columns AB=01 and 11; 2 cells.

Figure 3.6.10. The three groups that remain.

Tags: StandardKarnaugh maps

Exercise 3.6.4

Write a minimal sum of products for the function on this map.

Figure 3.6.11. A four-variable map with six 1s.

Hint

Four of the 1s are far apart on the map, but not far apart in the sense that matters.

Solution

The four corners form a group of four, as in the rules map, and its term is $\overline{B}\,\overline{D}$ . The other two 1s are a vertical pair in rows CD=01 and 11, column AB=01, with C changing, so they read as $\overline{A}BD$ . Neither of those 1s has a 1 neighbor except the other one, and the corner 1s have no 1 neighbors except other corners, so both groups are forced. This cover is therefore the only minimal one.

F = $\overline{B}\,\overline{D} + \overline{A}BD$

$\overline{B}\,\overline{D}$ four corners: rows 10 and 00, columns 10 and 00
$\overline{A}BD$ vertical pair: rows 01 and 11, column 01 (2 cells)

Karnaugh map of F: columns AB, rows CD; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=10
CD=00	1	0	1
CD=01	0	1	0
CD=11	0	1	0
CD=10	1	0	1

Groups drawn:

not B and not D: four corners in rows CD=10 and 00, columns AB=10 and 00; 4 cells.
not A and B and D: vertical pair in rows CD=01 and 11, column AB=01; 2 cells.

Figure 3.6.12. The corner group and the vertical pair.

Tags: StandardKarnaugh maps

Exercise 3.6.5

Six cells of this three-variable map are 1. Find two different minimal sums of products.

Figure 3.6.13. Six 1s around a ring, with a 0 in the second column and a 0 in the fourth.

Hint

Every 1 has two neighbors that are 1. Try covering the ring with three pairs, and notice that you can start the first pair in two different places.

Solution

Every 1 has exactly two neighbors that are 1, so each group is a pair, and three pairs are needed to cover six cells. One way to cut the ring: the vertical pair in column AB=00 reads as $\overline{A}\,\overline{B}$ ; the horizontal pair in row C=1, columns AB=01 and 11 reads as $BC$ ; and the horizontal pair in row C=0, columns AB=11 and 10 reads as $A\overline{C}$ . The other way shifts every pair one cell around the ring: the horizontal pair wrapping around the left and right edges in row C=0, columns AB=10 and 00 reads as $\overline{B}\,\overline{C}$ ; the horizontal pair in row C=1, columns AB=00 and 01 reads as $\overline{A}C$ ; and the vertical pair in column AB=11 reads as $AB$ . Both covers have three terms and six literals, and neither can be improved.

F = $\overline{A}\,\overline{B} + BC + A\overline{C}$

$\overline{A}\,\overline{B}$ vertical pair: column 00 (2 cells)
$BC$ horizontal pair: row 1, columns 01 and 11 (2 cells)
$A\overline{C}$ horizontal pair: row 0, columns 11 and 10 (2 cells)

Karnaugh map of F: columns AB, rows C; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
C=0	1	0	1	1
C=1	1	1	1	0

Groups drawn:

not A and not B: vertical pair in column AB=00; 2 cells.
B and C: horizontal pair in row C=1, columns AB=01 and 11; 2 cells.
A and not C: horizontal pair in row C=0, columns AB=11 and 10; 2 cells.

Figure 3.6.14. One way around the ring.

F = $\overline{B}\,\overline{C} + \overline{A}C + AB$

$\overline{B}\,\overline{C}$ horizontal pair, wraps left and right: row 0, columns 10 and 00 (2 cells)
$\overline{A}C$ horizontal pair: row 1, columns 00 and 01 (2 cells)
$AB$ vertical pair: column 11 (2 cells)

Karnaugh map of F: columns AB, rows C; cell values are 0, 1 or X for don't care
	AB=00	AB=01	AB=11	AB=10
C=0	1	0	1	1
C=1	1	1	1	0

Groups drawn:

not B and not C: horizontal pair wrapping around the left and right edges in row C=0, columns AB=10 and 00; 2 cells.
not A and C: horizontal pair in row C=1, columns AB=00 and 01; 2 cells.
A and B: vertical pair in column AB=11; 2 cells.

Figure 3.6.15. The other way around.

This is one of 2 minimal sum-of-products forms of F; all 2 use 3 terms and 6 literals. Any of them is a correct answer.

Tags: ChallengeKarnaugh maps