K-Maps and Simplification
Boolean algebra can simplify a formula, but it never tells you when you have finished. A Karnaugh map does. This volume draws truth tables as maps, shows how to circle groups of 1s and read the simplest formula off them, how don't cares make circuits smaller still, how grouping the 0s gives a product of sums, and why the smallest circuit can glitch.
- How a K-map is laid out, and why its rows and columns are in Gray-code order
- The five grouping rules, and how to read a group as a term
- Four-variable maps, prime implicants and essential prime implicants
- How don't cares make the answer smaller
- How to get a product of sums from the 0s, and how to remove a static hazard
- Volume 03 of this course: sum of products, minterms and the consensus theorem.
4.1 Two- and three-variable maps
A Karnaugh map is a truth table redrawn as a grid, arranged so that every cell differs from its neighbours in just one input. Circle neighbouring 1s in groups, and each group reads off as one short AND term.
Algebra can simplify a formula, but it never tells you when you have finished. A K-map shows the answer at a glance. It turns the rule A·B + A·B' = A into a picture: two terms that differ in one letter become two 1s side by side, and merge into one.
The layout
A three-input map has two rows, one for A = 0 and one for A = 1, and four columns for B and C. The columns do not run 00, 01, 10, 11. They run in Gray code order, 00, 01, 11, 10, so that each column differs from the next in one bit only. Here is where each truth-table row lands:
A=0: 0 1 3 2
A=1: 4 5 7 6
The map also wraps round: the left edge and the right edge are neighbours, because 00 and 10 differ in one bit too. Figure 4.1 shows the majority function from Volume 03 on a map. The small number in each cell is its row.
Grouping the 1s
Now circle the 1s in groups, following five rules:
- Group sizes are 1, 2, 4 or 8 - powers of two - because each halving drops one letter.
- Groups are rectangles, and they may wrap round the edges.
- Every 1 must be in at least one group. Groups may overlap.
- Make each group as large as possible, because a bigger group has fewer letters.
- Use as few groups as possible, because each group is one AND gate.
To read a group, look at which inputs stay the same across all its cells. Those inputs make the term; any input that changes inside the group drops out.
That is the same answer Volume 03 reached after six steps of algebra, found here in one look:
F = A·B + A·C + B·C
Bigger groups, fewer letters
A group of four drops two letters. In Figure 4.3 the four 1s all have C = 1, while A and B take every value, so the whole group reads as just C.
A group can also wrap round the edge. In Figure 4.4 the 1s sit in the outer two columns, which are neighbours:
Grouping three cells, or an L-shape. A group must be a rectangle of 1, 2, 4 or 8 cells, because only then does every letter either stay fixed or take every value. Three 1s in a row need two overlapping groups of two.
On a three-input map, a group covers the cells for rows 4, 5, 6 and 7. What term does it give?
Show the answer
Answer: B. Rows 4 to 7 are the whole A = 1 row of the map. B and C take every value across them, so they drop out, and the group reads as A.
4.2 Four-variable maps
A four-input map is a 4 by 4 grid, with Gray-code order down the side and across the top. It wraps in both directions, so even the four corners are neighbours. Look for the biggest groups first.
Rows are labelled by A and B, and columns by C and D, both in Gray-code order:
AB=00: 0 1 3 2
AB=01: 4 5 7 6
AB=11: 12 13 15 14
AB=10: 8 9 11 10
A worked example
Take F = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14). Eleven 1s would need eleven 4-input AND gates as a sum of minterms. On the map, three groups cover them all:
F = C' + A'·D' + B·D'
The four corners
Because the map wraps both ways, the four corner cells form a group of four. They all have B = 0 and D = 0:
Prime implicants and essential ones
When groups overlap, it helps to have names for them. A group that cannot be made any bigger is a prime implicant. A prime implicant that is the only one covering some 1 is an essential prime implicant: every answer must use it.
The best order is: take every essential prime implicant first, then cover the 1s that are left as cheaply as you can. Here is a map where that matters:
essential and not: F(A, B, C, D) = Σm(0, 1, 6, 7, 8, 12, 14, 15)
prime implicants: B·C, B'·C'·D', A'·B'·C', A·C'·D', A·B·D'
essential: A'·B'·C', B·C
F = B·C + A'·B'·C' + A·C'·D'
The two essentials cover every 1 except cells 8 and 12. Three primes could help - B'·C'·D' covers 8, and A·B·D' covers 12 - but only A·C'·D' covers both, so it is the one to take.
Sometimes two answers are equally good
Not every map has one best answer. The function Σm(0, 1, 2, 5, 6, 7) has no essential prime implicants at all. Two different choices of three groups each give 6 letters:
F = A'·C' + A·B + B'·C
F = A'·B' + A·C + B·C'
Both are correct, and both are equally cheap. Either one is a right answer in an exam.
On a four-input map, the 1s are exactly the four corner cells. What is F?
Show the answer
Answer: D. The corners are cells 0, 2, 8 and 10. In all of them B = 0 and D = 0, while A and C take both values, so the group reads B'·D'.
4.3 Don't-care conditions
Some input patterns can never happen. Their outputs are don't cares, marked X. You may count each X as a 1 or a 0, whichever makes the groups bigger.
A BCD digit uses four bits, but only the patterns for 0 to 9 are ever sent. Say a circuit must answer "is this digit 5 or more?":
| Digit | A B C D | F |
|---|---|---|
| 0 | 0 0 0 0 | 0 |
| 1 | 0 0 0 1 | 0 |
| 2 | 0 0 1 0 | 0 |
| 3 | 0 0 1 1 | 0 |
| 4 | 0 1 0 0 | 0 |
| 5 | 0 1 0 1 | 1 |
| 6 | 0 1 1 0 | 1 |
| 7 | 0 1 1 1 | 1 |
| 8 | 1 0 0 0 | 1 |
| 9 | 1 0 0 1 | 1 |
Rows 10 to 15 never happen, so their outputs do not matter. Mark them X, and use them wherever they help:
with the don't cares: F = A + B·C + B·D (5 letters)
without them: F = A'·B·C + A'·B·D + A·B'·C' (9 letters)
The first answer uses the don't cares, and needs 5 letters. The second treats them as 0s, and needs 9. Both give the right output for every digit that can really happen.
Covering an X that does not help. A don't care never has to be covered. Group it only if it makes a group bigger; a group that holds nothing but Xs is a wasted gate.
What may you do with an X in a K-map?
Show the answer
Answer: A. A don't care stands for an input that never happens, so its output can be anything. Include it in a group when that makes the group bigger, and leave it out otherwise.
4.4 Product of sums from a K-map
Group the 0s instead of the 1s and you get a product of sums. Each group of 0s becomes one OR term, and the terms are ANDed together. Sometimes this answer is smaller than the sum of products.
The method is the same, with every 0 and 1 swapped. Circle the 0s in groups, then read each group as an OR term. Because the group is where the output is 0, each letter is written the other way round. An input that stays 0 across the group appears plain, and one that stays 1 appears inverted.
F = (A + B)·(A + C)·(B + C)
When the product of sums wins
For some functions, grouping the 0s gives a much smaller circuit:
sum of products: F = A'·B' + A'·D' + B'·C·D + B·C·D' (10 letters)
product of sums: F = (A' + C)·(B' + D')·(A' + B + D) (7 letters)
It is worth trying both groupings on any map and keeping the smaller one.
A group of 0s covers every cell where A = 1 and C = 0. What OR term does it give?
Show the answer
Answer: C. The OR term must be 0 exactly on those cells. A' + C is 0 only when A' = 0 and C = 0, that is when A = 1 and C = 0. So the letters are written the opposite way to how they appear in the group.
4.5 Hazards: when a correct circuit glitches
A circuit can have the right truth table and still misbehave for a moment. When an input changes and the output should stay the same, gate delays can make it flicker. This flicker is a hazard, and a K-map shows where it can happen - and how to remove it.
Take Y = A·B + A'·C, with B = 1 and C = 1. Whatever A is, one of the two terms is 1, so Y should stay at 1. Now let A fall from 1 to 0, with every gate taking one step:
The dip is a static hazard: the output should have stayed static, but it glitched. It happens because the NOT gate makes A' change a step later than A. For that step, the term that is turning off has already gone, and the term that is turning on has not yet arrived.
Seeing it on the map
On the map, the two groups of Y = A·B + A'·C touch at cells 3 and 7, but no group covers both. Moving between those two cells changes A, and passes from one group to the other. Add a group that bridges them - here B·C - and one term stays 1 throughout the change:
The extra term changes nothing in the truth table, because it is the consensus term from Volume 03:
A·B + A'·C + B·C = A·B + A'·C on every row: True
But it holds the output steady while A changes:
The smallest circuit is not always the best one. When glitches matter - on a clock line, a reset, or anything that drives another circuit without waiting for a clock edge - add the bridging terms that remove hazards.
Why does adding B·C remove the glitch in Y = A·B + A'·C?
Show the answer
Answer: B. B·C does not depend on A, so it holds Y at 1 during the change of A, while A·B and A'·C swap over. The truth table is unchanged, because B·C is the consensus of the other two terms.
What you learned
- A K-map is a truth table in Gray-code order, so neighbouring cells differ in one input, and the edges wrap round.
- Groups hold 1, 2, 4 or 8 cells in a rectangle; bigger groups give fewer letters, fewer groups give fewer gates.
- A group reads as the inputs that stay the same across it.
- A prime implicant cannot grow any bigger; an essential one is the only group covering some 1. Take the essentials first.
- Some maps have two equally cheap answers, and either is right.
- Don't cares may be counted as 1 or 0, whichever makes the groups bigger.
- Grouping the 0s gives a product of sums, which is sometimes smaller.
- A static hazard is a glitch where the output should stay put. A bridging group, the consensus term, removes it.
Key words from this volume
Every word below has a plain-English entry in the glossary.
- Karnaugh map (K-map)
- Gray code
- Prime implicant
- Essential prime implicant
- Don't care (X)
- Product of sums
- Hazard
Practice
A group of four and a pair
Simplify F(A, B, C) = Σm(0, 1, 2, 3, 6) with a K-map.
Show the solution
Rows 0 to 3 are the whole A = 0 row, a group of four that reads A'. Cell 6 is left; it pairs with cell 2, above it, and that pair has B = 1 and C = 0:
F = A' + B·C'
Two variables
A two-input function is 1 on rows 1, 2 and 3. Simplify it.
Show the solution
The column B = 1 is one group, and the row A = 1 is another; they overlap on cell 3, which is allowed:
F = A + B
It is the OR gate - which makes sense, since it is 0 only on row 0.
Count the savings
For "is this BCD digit 5 or more?", how many letters does the answer need with the don't cares, and how many without them?
Show the solution
With the don't cares the answer is A + B·C + B·D: 5 letters. Without them it is A'·B·C + A'·B·D + A·B'·C': 9 letters. Using the patterns that can never happen almost halves the circuit.
Interview corner
Why Gray-code order?
"Why are the rows and columns of a K-map in Gray-code order instead of counting order?"
Show the solution
"So that any two neighbouring cells differ in exactly one input. That is what makes grouping work: two neighbouring 1s differ in one letter, and A·B + A·B' = A, so the letter that changes drops out. In counting order, 01 and 10 would sit side by side while differing in two bits, and a group across them would be wrong."
What is a static hazard?
"What is a static hazard, and how do you remove one?"
Show the solution
"A static-1 hazard is a short dip to 0 in an output that should stay at 1 while an input changes. It comes from different path delays: one AND term turns off before the other turns on. On the K-map, it shows up where two groups touch without overlapping. You remove it by adding the consensus term, a group bridging the two, which stays 1 through the change. It costs a gate, but the truth table is unchanged."
Volume 05 moves from single functions to whole building blocks: multiplexers, decoders and more.