By the end of this chapter you should be able to:
- Explain why the rows and columns of a Karnaugh map are labelled in Gray code, and why the map wraps round at its edges.
- Plot a function of two, three, four or five variables on a map from its minterm list or truth table.
- Apply the grouping rules to read a minimal sum-of-products expression, and justify each group by the combining theorem \(AB + AB' = A\).
- Distinguish implicants, prime implicants and essential prime implicants, and use distinguished 1s to build a minimal cover systematically.
- Obtain a minimal product-of-sums expression by grouping the zeros and applying De Morgan's theorem.
- Use don't-care conditions to enlarge groups, and state when a don't-care must not be grouped.
A truth table says what a circuit must do; it says nothing about how few gates will do it. Chapter 7 turned any specification into a canonical sum of minterms, and that expression is always correct and almost always wasteful — a four-variable function with nine minterms needs nine four-input AND gates and a nine-input OR gate if it is built as written. Chapter 6 supplied theorems that shorten such an expression, but applying them is an art: there is no way of telling, part-way through, whether the remaining terms can still be reduced or whether an earlier step has closed off the shortest route.
The Karnaugh map replaces that judgement with a picture. It is a rearrangement of the truth table in which the single theorem that does all the simplifying — \(AB + AB' = A\) — corresponds to two squares sitting next to each other, so the eye finds in a moment what the algebra finds only with luck. This chapter builds the map from that idea, states the grouping rules and where they come from, and works through minimisation in both sum-of-products and product-of-sums form, with don't-care conditions and with five variables.
1 Why the Map Is Ordered in Gray Code
Chapter 7 left every function expressible as a canonical sum of minterms, and Chapter 6 gave the algebra needed to shorten that sum. What it did not give was any way of knowing when to stop. Algebraic simplification depends on spotting which theorem to apply next, and a step that looks like progress can lead to a dead end from which the minimum is no longer reachable. The Karnaugh map, published by Maurice Karnaugh in 1953, removes the guesswork for functions of up to five or six variables by turning the one theorem that actually does the work into something you can see.
That theorem is the combining, or adjacency, theorem:
Two product terms that are identical except for one variable, which appears uncomplemented in one and complemented in the other, merge into a single term with that variable removed. Every reduction a K-map performs is an application of this and nothing else.
Two minterms can be merged exactly when their binary codes differ in one bit position. Minterms \(m_5 = A'BC'D\) and \(m_7 = A'BCD\) have codes 0101 and 0111, which differ only in \(C\), so they merge to \(A'BD\). Call such a pair logically adjacent. The whole idea of the map is to arrange the \(2^n\) cells so that logically adjacent minterms are also physically adjacent squares — then merging is something the eye does.
Ordinary binary counting order will not do this. In the sequence 00, 01, 10, 11 the step from 01 to 10 changes two bits, so those two squares would sit side by side without being combinable. The reflected binary or Gray code of Chapter 4 changes exactly one bit between successive words, so labelling the rows and columns 00, 01, 11, 10 guarantees that horizontal and vertical neighbours differ in a single variable. The price is that the cells no longer appear in numerical order, which is why the top row of a four-variable map reads 0, 1, 3, 2 and not 0, 1, 2, 3.
The wrap-around follows from the same property. The first and last labels, 00 and 10, also differ in one bit, so the leftmost and rightmost columns are adjacent, as are the top and bottom rows. The map is not a flat rectangle but the surface of a torus, drawn flat because that is easier to print.
Any two neighbouring cells — including cells that neighbour each other only round the edge of the map — hold minterms whose codes differ in exactly one variable, and can therefore be merged into a term with that variable deleted. Everything in the rest of this chapter is a consequence of that sentence.
2 Two-, Three- and Four-Variable Maps
A map for \(n\) variables has \(2^n\) cells, one per minterm, and is filled straight from the truth table: a 1 in every cell whose minterm is present in the function, a 0 in the rest. Nothing is lost and nothing is added in the transfer — the map is the truth table redrawn on a grid whose geometry happens to expose adjacency.
The two-variable map is a 2 × 2 grid. For \(F(A,B) = \Sigma m(1,2,3)\):
| A \ B | 0 | 1 |
|---|---|---|
| 0 | 0 (m0) | 1 (m1) |
| 1 | 1 (m2) | 1 (m3) |
The right-hand column is a pair in which \(A\) changes and \(B = 1\) throughout, giving \(B\); the bottom row is a pair in which \(B\) changes and \(A = 1\), giving \(A\). Hence \(F = A + B\), the three minterms of the canonical form having collapsed to two literals. Cell \(m_3\) belongs to both groups, which is allowed and often necessary: the idempotent law \(X + X = X\) means a minterm may be covered any number of times without changing the function.
The three-variable map is drawn as two rows (\(A\)) by four Gray-ordered columns (\(BC\)). Take \(F(A,B,C) = \Sigma m(0,2,4,5,6)\):
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 (0) | 0 (1) | 0 (3) | 1 (2) |
| 1 | 1 (4) | 1 (5) | 0 (7) | 1 (6) |
Cells 0, 2, 4 and 6 form a block of four occupying the first and last columns of both rows — legal because those columns wrap. Across that block \(A\) takes both values and \(B\) takes both values, while \(C\) is 0 throughout, so the block is \(C'\). Cells 4 and 5 form a pair in which \(C\) changes with \(A = 1\) and \(B = 0\), giving \(AB'\). The minimal sum is \(F = C' + AB'\), three literals in place of the fifteen of the canonical form.
The four-variable map of Figure 8.1 is the largest that stays comfortable. Rows carry \(AB\), columns carry \(CD\), and the cell number is \(8A + 4B + 2C + D\). Each cell now has four neighbours rather than three, and it is worth checking one wrap case by hand until it stops looking like a trick: \(m_0 = A'B'C'D'\) is 0000 and \(m_8 = AB'C'D'\) is 1000, differing only in \(A\), so the top-left and bottom-left cells really are adjacent even though the drawing separates them.
3 Grouping Rules and Wrap-Around
Reading a minimal expression off the map means covering every 1 with as few groups as possible, each group as large as possible. The rules that make a group legal all come from the combining theorem being applied repeatedly.
- A group must contain a number of cells that is a power of two: 1, 2, 4, 8 or 16. Merging halves a term count at each step, so only powers of two survive as single product terms. A group of six cells is not a term and cannot be read as one.
- A group must be a rectangle in the wrapped geometry — a run of cells that is contiguous horizontally and vertically. An L-shape of four cells is not a group, because the four minterms in it do not agree on any set of variables.
- Groups may overlap, and a cell may be used again in another group. What is not allowed is a group that contains a 0.
- Groups may wrap round the edges. The four corner cells of a four-variable map form a legal group of four.
- Every 1 must be in at least one group; make each group as large as the 1s allow, and use as few groups as will cover the map.
The pay-off of a large group is fixed by counting. A group of \(2^k\) cells in an \(n\)-variable map holds \(2^k\) minterms that agree on \(n-k\) variables and disagree on the other \(k\), so it yields a product term of \(n-k\) literals:
Doubling the size of a group always removes exactly one literal. That is why grouping greedily by size is the right instinct: a pair costs three literals on a four-variable map, a quad costs two, an octet costs one.
Minimise \(F(A,B,C,D) = \Sigma m(0,1,2,5,8,9,10)\).
Plot the seven 1s as in Figure 8.2 and look for the largest legal blocks. Cells 0, 2, 8 and 10 are the four corners; across them \(A\) and \(C\) both change while \(B = 0\) and \(D = 0\), so the group is \(B'D'\). Cells 0, 1, 8 and 9 form a block spanning the top and bottom rows in the first two columns; there \(A\) and \(D\) change while \(B = 0\) and \(C = 0\), giving \(B'C'\). Cell 5 is left over. Its only 1-valued neighbour is cell 1, and the pair 1, 5 has \(B\) changing with \(A = 0\), \(C = 0\), \(D = 1\), giving \(A'C'D\). Every 1 is now covered:
Seven literals and four gates, against seven four-input AND gates and a seven-input OR gate for the canonical form. Note that cells 0, 8 and 9 are each covered twice; overlapping costs nothing and here it is what allows both four-cell groups to be taken at full size.
A minimisation is easy to verify and expensive to get wrong. Substitute every input combination into the reduced expression and confirm it reproduces the original minterm list — with four variables that is sixteen rows. In Example 8.1, \(ABCD = 1010\) gives \(B'D' = 1\), so \(F = 1\), and \(m_{10}\) is indeed in the list; \(ABCD = 0011\) gives \(B'D' = 0\), \(B'C' = 0\), \(A'C'D = 0\), so \(F = 0\), and \(m_3\) is indeed absent.
4 Implicants, Prime Implicants and Essential Prime Implicants
"As large as possible, as few as possible" is good advice but not a procedure, and on a busy map it can be followed carefully and still miss the minimum. Three definitions turn it into something systematic, and they are also the vocabulary that Chapter 9 needs in order to do the same job by table.
- An implicant is any product term that implies the function: whenever the term is 1 the function is 1. On the map it is any legal group of 1s, of any allowed size, including a single cell.
- A prime implicant (PI) is an implicant that cannot be enlarged: combining it with any adjacent group would take in a 0. On the map it is a group that is not contained in a bigger legal group.
- An essential prime implicant (EPI) is a prime implicant that covers at least one 1 covered by no other prime implicant. That 1 is said to be distinguished, and it forces the EPI into every minimal expression.
The minimal sum is then found by a procedure rather than by inspection: identify all prime implicants; select every essential prime implicant; and cover whatever 1s remain with the smallest number of the leftover prime implicants, preferring the largest. A prime implicant that is not essential may or may not be needed, and one that is neither essential nor needed is redundant — including it would cost gates and change nothing.
Minimise \(F(A,B,C,D) = \Sigma m(0,1,2,3,5,7,13,14,15)\).
Four prime implicants exist, shown in Figure 8.3:
| Prime implicant | Cells covered | Distinguished 1? | Status |
|---|---|---|---|
| \(A'B'\) | 0, 1, 2, 3 | cells 0 and 2 | essential |
| \(BD\) | 5, 7, 13, 15 | cell 13 | essential |
| \(ABC\) | 14, 15 | cell 14 | essential |
| \(A'D\) | 1, 3, 5, 7 | none | not essential |
Cell 2 lies only in \(A'B'\), cell 13 only in \(BD\) and cell 14 only in \(ABC\), so those three are forced. Together they cover 0, 1, 2, 3, 5, 7, 13, 14 and 15 — every 1 in the function — so the fourth prime implicant is redundant:
\(A'D\) is a perfectly legitimate group of four, and a student who marks it first and then patches the rest of the map around it will finish with \(A'B' + A'D + BD + ABC\): correct, but a gate and three literals more expensive. The lesson is to look for distinguished 1s before drawing any loop, not after.
Not every function is so obliging. If no prime implicant is essential, every 1 is covered at least twice and the map offers no starting point; such a chart is called cyclic, and the smallest example is \(F = \Sigma m(0,1,2,5,6,7)\) of three variables, which has six prime implicants, no essential ones, and two different minimal answers of three terms each. Chapter 9 handles that case properly with Petrick's method.
5 Minimising to Product-of-Sums from the Zeros
Everything so far has produced a sum of products, because groups were made of 1s. A product-of-sums form is often cheaper, and on some technologies it is the natural one, so it is worth being able to produce both and choose. The route is to minimise the complement and then invert.
Group the zeros of \(F\) exactly as the 1s were grouped. A group of zeros is a product term of \(F'\), because \(F' = 1\) precisely where \(F = 0\). Minimising the zeros therefore gives a minimal sum of products for \(F'\), and De Morgan's theorem from Chapter 6 turns that into a minimal product of sums for \(F\): complement each literal and change every AND to an OR.
Take \(F(A,B,C,D) = \Sigma m(0,1,2,5,8,9,10)\) again. Its zeros are at cells 3, 4, 6, 7, 11, 12, 13, 14 and 15, so
Grouping those zeros gives three prime implicants of \(F'\), all essential: cells 3, 7, 11 and 15 form the \(CD\) column; cells 4, 6, 12 and 14 give \(BD'\); cells 12, 13, 14 and 15 give \(AB\). Hence
Complementing both sides and applying De Morgan's theorem twice:
Both forms describe the same seven minterms; substituting all sixteen input combinations into each confirms it. The SOP version needs 7 literals — three AND gates with 2, 2 and 3 inputs feeding a three-input OR, so 10 gate inputs in all. The POS version needs 6 literals — three two-input OR gates feeding a three-input AND, so 9 gate inputs. Here the POS implementation is the cheaper of the two, and there is no way to know that without doing both.
You can also read the POS directly by grouping zeros and writing each group as a sum term with every literal complemented relative to the SOP rule. The group of zeros with \(C = 1, D = 1\) is written \((C' + D')\), the group with \(B = 1, D = 0\) is written \((B' + D)\), and so on. It is the same operation as above with De Morgan's theorem applied in your head — reliable once you trust it, and worth checking against the long route the first few times.
A function whose 1s cluster gives a cheap SOP; a function whose 0s cluster gives a cheap POS. The two minimal forms are rarely the same size, and the difference is a real saving in silicon area and in delay. Chapter 10 shows that a two-level SOP maps directly onto NAND gates and a two-level POS onto NOR gates, so the choice also decides which single gate type the circuit needs.
6 Don't-Care Conditions
Some input combinations never occur, or occur but with an output nobody looks at. A BCD digit uses only the codes 0000 to 1001; the six patterns 1010 to 1111 are not produced by any decimal digit, so what a BCD circuit does with them is unconstrained. Such a combination is a don't-care, written \(\times\) or d on the map and listed separately in the function specification:
A don't-care is not a 1 and not a 0; it is a cell whose value the designer is free to choose, and the choice is made independently for every group. Include a don't-care in a group when doing so makes the group bigger, and ignore it otherwise. The one rule that must not be broken is that a group made entirely of don't-cares is never taken, because it covers no 1 and contributes nothing but a gate.
Design a circuit whose output is 1 when a BCD digit is 5 or more. The 1s are at 5, 6, 7, 8 and 9; the codes 10 to 15 are don't-cares.
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 (0) | 0 (1) | 0 (3) | 0 (2) |
| 01 | 0 (4) | 1 (5) | 1 (7) | 1 (6) |
| 11 | × (12) | × (13) | × (15) | × (14) |
| 10 | 1 (8) | 1 (9) | × (11) | × (10) |
Treating the six don't-cares as 1s where it helps, the bottom two rows become a full block of eight, which is \(A\); cells 5, 7, 13 and 15 make a quad, which is \(BD\); cells 6, 7, 14 and 15 make another, which is \(BC\). So
five literals, three gates. Now repeat the exercise with the don't-cares forced to 0, as they would be if the specification insisted on a defined output everywhere:
nine literals and four gates, with three AND gates of three inputs each. The don't-cares have saved four literals and a gate on a circuit this small; on a seven-segment decoder, where six of sixteen codes are unused on every one of seven outputs, the saving is what makes the device practical. Chapter 18 designs that decoder in full.
Two habits are worth forming. First, decide the don't-cares group by group and not once for the whole map: cell 11 may usefully be a 1 in one group and be ignored in another, because the algebra never asks what value it "really" has. Second, remember that the circuit will produce some output for an unused code even though the design ignored it. If an unused code can actually reach the inputs — through a fault, a noisy bus or a counter that powers up in an illegal state — the output it produces is whatever the minimisation happened to choose, and Chapter 24 shows how that leads to a counter with no way back into its intended sequence.
7 Five-Variable Maps
Thirty-two cells cannot be laid out on a plane so that every logically adjacent pair is a physical neighbour. The usual compromise is to draw two four-variable maps side by side, one for \(A = 0\) holding minterms 0 to 15 and one for \(A = 1\) holding 16 to 31, and to treat them as sheets stacked one behind the other. Within each sheet the ordinary rules apply. Between sheets, the cell in the same position of each map is an adjacent pair, because those two minterms differ only in \(A\).
So there are three kinds of group. A group lying wholly in the \(A = 0\) map carries the literal \(A'\); a group lying wholly in the \(A = 1\) map carries \(A\); and a group occupying identical cells in both maps loses \(A\) altogether. Group sizes double: the largest useful groups are now blocks of eight and sixteen, and a term of a five-variable function has \(5 - \log_2(\text{cells})\) literals.
Minimise \(F(A,B,C,D,E) = \Sigma m(0,2,4,6,9,13,21,23,25,29,31)\).
Split the minterm list at 16. The \(A = 0\) map receives 0, 2, 4, 6, 9 and 13; the \(A = 1\) map receives 21, 23, 25, 29 and 31, which are plotted at positions 5, 7, 9, 13 and 15 of that map.
Cells 0, 2, 4 and 6 form a quad in the \(A = 0\) map with no counterpart opposite, so \(A\) is retained: \(B = 0\), \(E = 0\), and \(C\) and \(D\) both change, giving \(A'B'E'\). Cells 21, 23, 29 and 31 form a quad in the \(A = 1\) map alone, with \(C = 1\) and \(E = 1\), giving \(ACE\). That leaves 9 and 13 in one map and 25 and 29 in the other, at the same two positions in each — a group of four spanning both sheets, with \(B = 1\), \(D = 0\), \(E = 1\) and both \(A\) and \(C\) changing, so \(A\) drops out and the term is \(BD'E\). Hence
Nine literals for a function of eleven minterms, verified by evaluating all thirty-two input combinations. Minterm 29 is covered twice, by \(ACE\) and again by \(BD'E\); overlap between the sheets is as harmless as overlap within one.
Six variables can be drawn as four four-variable maps, with adjacency between the horizontal pair, the vertical pair and the diagonal pair, but by then the bookkeeping is worse than the algebra it replaces and errors of omission are the norm. That is the point at which the map has to be given up in favour of a procedure that a machine can follow, which is what Chapter 9 provides.
8 Summary and Key Results
| Item | Definition or rule | Consequence |
|---|---|---|
| Cell adjacency | Neighbouring cells differ in exactly one variable, edges included | Any adjacent pair merges by \(AB + AB' = A\) |
| Group of \(2^k\) cells | Legal only for a power-of-two rectangle in the wrapped map | Yields a term of \(n-k\) literals; each doubling removes one literal |
| Prime implicant | A group that cannot be enlarged without taking in a 0 | The only terms that can appear in a minimal expression |
| Essential prime implicant | The only prime implicant covering some 1 (a distinguished 1) | Must appear in every minimal expression; select these first |
| Grouping the zeros | Gives a minimal SOP for \(F'\); De Morgan gives POS for \(F\) | The cheaper of the two forms is not predictable — minimise both |
| Don't-care \(\times\) | An input combination that cannot occur or whose output is unused | Take it as 1 when it enlarges a group, as 0 otherwise; never group don't-cares alone |
| Five-variable map | Two four-variable maps, one per value of the fifth variable | A group in the same cells of both maps loses that variable |
9 Common Mistakes
Writing the columns 00, 01, 10, 11 destroys the property the map exists for: the second and third columns then differ in two bits and cannot be combined, while cells that are genuinely adjacent end up apart. Every group read from such a map is wrong. The headers are Gray code — 00, 01, 11, 10 — and the cell numbers along a row of a four-variable map consequently run 0, 1, 3, 2.
Six adjacent 1s look tempting but no single product term covers exactly six cells; they must be taken as a four and a two, overlapping. The opposite error costs just as much: leaving the four corner cells as four separate single-cell terms, when they form one legal group of four, turns a two-literal term into sixteen literals.
A don't-care earns its place only by making a group of 1s larger. Drawing a loop round a block of don't-cares adds a gate whose output is never wanted, and a group containing one 1 and three don't-cares is legal but should be checked — if that 1 is already covered elsewhere, the whole group is redundant.
10 Chapter Review
1. Minimise \(F(A,B,C,D) = \Sigma m(0,2,5,7,8,10,13,15)\) and state how many gates the result needs.
The 1s at 0, 2, 8 and 10 are the four corners, giving \(B'D'\); the 1s at 5, 7, 13 and 15 occupy the two middle columns of the second and third rows, giving \(BD\). Both are essential and together they cover all eight 1s, so \(F = B'D' + BD\) — four literals, two AND gates and one OR gate, plus inverters for \(B'\) and \(D'\). (The function is the XNOR of \(B\) and \(D\), which Chapter 5 would write as \((B \oplus D)'\).)
2. Why can a group never contain six cells, when six 1s may certainly be adjacent to one another?
Each merge by \(AB + AB' = A\) halves the number of terms and removes one variable, so a single product term always covers a number of cells that is a power of two. Six is not a power of two, and the six minterms concerned agree on no fixed set of variables. They are covered instead by a group of four and an overlapping group of two, which is two product terms.
3. A four-variable function has prime implicants \(A'B'\) (cells 0, 1, 2, 3), \(A'D\) (1, 3, 5, 7), \(BD\) (5, 7, 13, 15) and \(ABC\) (14, 15), and its 1s are at 0, 1, 2, 3, 5, 7, 13, 14, 15. Which are essential and what is the minimal sum?
Cell 0 and cell 2 lie only in \(A'B'\), cell 13 lies only in \(BD\), and cell 14 lies only in \(ABC\), so those three are essential. Selecting them covers 0, 1, 2, 3, 5, 7, 13, 14 and 15 — every 1 — so \(A'D\) is redundant and \(F = A'B' + BD + ABC\), seven literals.
4. A circuit must give 1 when a BCD digit is prime (2, 3, 5 or 7). Minimise it with and without the use of don't-cares, and compare.
With the six unused codes 10–15 taken as don't-cares, cells 2, 3, 11 and 10 form a quad giving \(B'C\), and cells 5, 7, 15 and 13 form a quad giving \(BD\); both are essential and cover all four 1s, so \(F = B'C + BD\) — four literals. Forcing the unused codes to 0 leaves only the pairs 2, 3 and 5, 7, giving \(F = A'B'C + A'BD\) — six literals and two three-input AND gates. The don't-cares save two literals and reduce both AND gates to two inputs.
5. On a five-variable map, a group of four cells occupies positions 1 and 5 of the \(A = 0\) map and the same two positions of the \(A = 1\) map. What is the resulting term, and how would it differ if the group lay in the \(A = 1\) map alone?
Positions 1 and 5 of a map whose rows are \(BC\) and columns \(DE\) hold \(BCDE = 0001\) and \(0101\), which differ only in \(C\); the two sheets differ only in \(A\). Both \(C\) and \(A\) are therefore eliminated and the term is \(B'D'E\) — three literals, as \(5 - \log_2 4 = 3\) requires, and with no \(A\) in it. A group of four lying in the \(A = 1\) map alone also gives three literals, but one of them is \(A\) itself: four cells inside one sheet eliminate two of \(B, C, D, E\) and retain \(A\), whereas the spanning group eliminates one of them and \(A\) as well.