By the end of this chapter you should be able to:
- State why the Karnaugh map becomes unusable beyond five or six variables, in terms of the number of cells and the number of prime implicants.
- Group minterms and don't-cares by weight, and explain why only adjacent groups need to be compared.
- Carry out the combining passes with the tick notation, and identify every prime implicant as an unticked entry.
- Construct a prime implicant chart, extract the essential prime implicants from columns holding a single cross, and complete a minimal cover.
- Recognise a cyclic chart and solve it with Petrick's method, obtaining every minimal solution rather than just one.
- Handle don't-care conditions correctly, including them when generating prime implicants and excluding them from the chart.
Chapter 8 finished with a five-variable map drawn as two four-variable maps, and the admission that six variables need four maps and seven need eight. The Karnaugh map works because a person can see a rectangle; nothing about it scales, and the point at which it fails is not far beyond the examples in a textbook. A six-variable function is entirely ordinary in a real design — an address decoder, a state machine output, an instruction decoder — and it is past the practical limit of the map.
The tabular method of Quine and McCluskey does exactly what the map does, using exactly the same combining theorem, but sets the work out as a sequence of comparisons between bit patterns instead of as a picture. Nothing has to be seen; everything has to be written down. That makes it slower by hand for four variables and possible for twenty, and it makes it the method a computer uses. This chapter works one function through every table of the procedure, then deals with the case where the chart gives no starting point at all.
1 Where the Map Runs Out
The Karnaugh map of Chapter 8 is an excellent instrument for four variables and a workable one for five. At six it needs four maps and three kinds of between-map adjacency; at seven nobody attempts it. The reason is not that the mathematics changes but that the map's whole advantage — that a human eye can spot the largest rectangle at a glance — disappears once the drawing is too big to take in.
The numbers make the point. A map has \(2^n\) cells: 16 at four variables, 64 at six, 1024 at ten. Worse, the quantity that actually has to be searched is the number of prime implicants, and the largest number an \(n\)-variable function can have grows roughly as \(3^n/n\) — about 122 for six variables, some 5900 for ten, and 2.7 million for sixteen. No amount of care with coloured pencils survives that.
What is needed is a procedure: a finite sequence of mechanical steps that produces the minimal expression without asking the person carrying it out to see anything. Willard Quine set out such a method in 1952 and Edward McCluskey completed it in 1956, and the Quine–McCluskey or tabular method is what results. It has three properties the map does not.
- It is exact. It finds every prime implicant, so the cover it chooses really is a minimum and not merely a good one.
- It is independent of \(n\). The same steps apply to four variables and to forty; only the amount of writing changes.
- It is programmable. Every step is a comparison of bit patterns or a search of a table, which is why it is the method behind logic minimisation software and why understanding it tells you what a synthesis tool is doing to your VHDL in Chapter 30.
It is worth being clear about what "exact" buys. An algebraic reduction of the kind attempted in Chapter 6 gives an expression that is correct and usually shorter than the canonical form, with no guarantee that it is the shortest. A map gives the minimum provided the person reading it found every maximal group, which is an assumption rather than a proof. The tabular method generates the prime implicants by construction, so the set it chooses from is complete, and the result is minimal in a sense that can be defended in a design review.
The price is effort. What the map does in one glance, the table does in several passes of systematic comparison, and by hand that is slower for four variables than drawing the map. The method is not a replacement for the map at small \(n\); it is what you use when the map has stopped being available.
2 Setting Up: Grouping Minterms by Weight
The method rests on the same combining theorem as the map, \(XY + XY' = X\), so the first job is to find every pair of terms that differ in exactly one bit. Done naively that means comparing every term with every other, which for \(k\) terms is \(k(k-1)/2\) comparisons. A single observation removes most of them.
Define the weight of a minterm as the number of 1s in its binary code. If two codes differ in exactly one bit position, one of them has a 0 where the other has a 1, so their weights differ by exactly one. Terms of the same weight can never combine, and terms whose weights differ by two or more can never combine. Sorting the minterms into groups by weight therefore means that only adjacent groups need to be compared at all.
So the setup is: write every minterm of the function — and every don't-care, for reasons taken up in the last section — as an \(n\)-bit binary code, and list them in groups, group \(i\) holding the codes with \(i\) ones. For \(F(A,B,C,D) = \Sigma m(0,1,2,5,6,7,8,9,10,14)\), which is the function carried through the whole of this chapter, that gives:
| Group | Minterm | ABCD | Group | Minterm | ABCD |
|---|---|---|---|---|---|
| 0 | 0 | 0000 | 2 | 5 | 0101 |
| 1 | 1 | 0001 | 6 | 0110 | |
| 2 | 0010 | 9 | 1001 | ||
| 8 | 1000 | 10 | 1010 | ||
| 3 | 7 | 0111 | |||
| 14 | 1110 |
Ten minterms would need 45 comparisons if every pair were tried. Comparing only across group boundaries — one term against three, three against four, four against two — needs 23, and every comparison that has been skipped was guaranteed to fail. The saving looks small here and becomes the difference between a feasible and an infeasible computation at twelve or sixteen variables.
3 The Combining Step and the Tick Notation
Take each term in group \(i\) and compare it with each term in group \(i+1\). If the two codes differ in exactly one position, write a new term in the next column with a dash in that position, and place a tick against both parent terms. The dash records the variable that the combination has eliminated: 0001 and 0101 combine to 0-01, which is \(A'C'D\).
The tick means only one thing: this term is contained in a larger one. A ticked term is still an implicant of the function and it is still correct, but it cannot be prime, because the term it helped to form covers everything it covers and more. An unticked term, in any column, has no larger term containing it, and that is precisely the definition of a prime implicant.
Comparing the groups of the previous section in pairs gives thirteen combinations. The bracketed numbers are the minterms each new term covers.
| From groups | Minterms | ABCD | Ticked? | From groups | Minterms | ABCD | Ticked? |
|---|---|---|---|---|---|---|---|
| 0–1 | 0, 1 | 000- | ✓ | 1–2 | 8, 9 | 100- | ✓ |
| 0, 2 | 00-0 | ✓ | 8, 10 | 10-0 | ✓ | ||
| 0, 8 | -000 | ✓ | 2–3 | 5, 7 | 01-1 | — | |
| 1–2 | 1, 5 | 0-01 | — | 6, 7 | 011- | — | |
| 1, 9 | -001 | ✓ | 6, 14 | -110 | ✓ | ||
| 2, 6 | 0-10 | ✓ | 10, 14 | 1-10 | ✓ | ||
| 2, 10 | -010 | ✓ |
Every minterm of column I has been ticked, so no single minterm is prime. Three entries of column II are not ticked and are therefore prime implicants already: 0-01 = \(A'C'D\), 01-1 = \(A'BD\) and 011- = \(A'BC\).
The second pass works on column II exactly as the first worked on column I, with one extra condition: two terms may be combined only if their dashes are in the same positions, since a term of \(n-1\) literals can only merge with another term of \(n-1\) literals over the same variables. Weight is now counted as the number of 1s, dashes not counting.
Only three distinct combinations survive:
| Parents | Minterms covered | ABCD | Term | Ticked? |
|---|---|---|---|---|
| (0,1) + (8,9) | 0, 1, 8, 9 | -00- | \(B'C'\) | — |
| (0,2) + (8,10) | 0, 2, 8, 10 | -0-0 | \(B'D'\) | — |
| (2,6) + (10,14) | 2, 6, 10, 14 | --10 | \(CD'\) | — |
Each of these arises twice — \((0,8)+(1,9)\) produces -00- as well — and the duplicate is simply struck out. No term of column III can be combined with any other, because no two of them have dashes in matching positions, so the process stops. Collecting every unticked entry from both columns gives the six prime implicants of the function:
Drawing the map of Chapter 8 for the same minterm list produces the same six maximal groups, which is worth doing once as a check that the two methods are the same method.
It is tempting to stop as soon as the terms in a column look big enough. The unticked entries of an early column are prime and must be kept, but a column that has not been fully compared may leave a large implicant undiscovered, and a prime implicant that is never generated can never be chosen. The method is exact only because the combining step is carried on until no pair of terms anywhere can be merged.
4 The Prime Implicant Chart
Finding the prime implicants is half the problem. A function usually has more of them than a minimal expression needs — this one has six and needs three — so the second half is choosing the cheapest subset that still covers every minterm. That is a covering problem, and the prime implicant chart is the way it is set out.
Rule the chart with one row per prime implicant and one column per minterm of the function. Put a cross where a prime implicant covers a minterm. Then:
- Find every column containing exactly one cross. The prime implicant in that row is essential: nothing else covers that minterm, so it must appear in the answer. Mark it.
- Delete the row of each essential prime implicant and every column it covers, since those minterms are now dealt with.
- If any columns remain, choose from the rows left the smallest set that covers them, preferring implicants with fewer literals when there is a choice.
The chart of Figure 9.3 has ten columns. Column 9 holds a single cross, in the row of \(B'C'\); column 14 holds a single cross, in the row of \(CD'\). Both are essential. Selecting them and deleting their columns removes 0, 1, 2, 6, 8, 9, 10 and 14, leaving only 5 and 7 uncovered.
Three prime implicants can still contribute: \(A'C'D\) covers 5, \(A'BC\) covers 7, and \(A'BD\) covers both. One term is cheaper than two, so \(A'BD\) is chosen and
seven literals, three AND gates and one OR gate. Substituting all sixteen input combinations confirms that this expression is 1 exactly on \(\{0,1,2,5,6,7,8,9,10,14\}\) and 0 elsewhere. Note what happened to \(B'D'\): it is a genuine prime implicant covering four minterms, and it is not in the answer, because every minterm it covers is covered by the two essential terms. Being large is not the same as being needed.
Two bookkeeping devices shrink a chart before any guessing is required. A row dominates another when it covers every minterm the other covers and costs no more; the dominated row can be deleted. A column dominates another when it contains a cross in every row the other does; the dominating column can be deleted, because covering the harder minterm automatically covers the easier one.
Both appear in the chart above. Column 0 has crosses in the rows of \(B'C'\) and \(B'D'\); column 9 has a cross in the row of \(B'C'\) only. Every row that covers 9 also covers 0, so column 0 dominates column 9 and may be struck out — whatever is eventually chosen to cover the more awkward minterm 9 will cover 0 as well. Row dominance settles the end of the same problem. Once the two essential implicants have gone, the rows left are \(A'C'D\) covering 5, \(A'BD\) covering 5 and 7, and \(A'BC\) covering 7. \(A'BD\) covers everything either of the other two covers and has the same three literals, so it dominates both; deleting them leaves a chart with one row, which is then essential by inspection. Applying the two rules alternately often unravels a chart completely without a single guess.
5 Cyclic Charts and Petrick's Method
Sometimes no column has a single cross, no row dominates another and no column dominates another. Such a chart is cyclic, and it has no obvious place to start: every minterm is covered twice, so every prime implicant looks optional and none is. The smallest example is a function of three variables,
whose six prime implicants each cover exactly two minterms, and every minterm lies in exactly two of them:
| \(P_1 = A'C'\) | \(P_2 = A'B'\) | \(P_3 = B'C\) | \(P_4 = BC'\) | \(P_5 = AC\) | \(P_6 = AB\) | |
|---|---|---|---|---|---|---|
| covers | 0, 2 | 0, 1 | 1, 5 | 2, 6 | 5, 7 | 6, 7 |
Petrick's method solves such a chart algebraically instead of by trial. Write down, for each minterm, the sum of the prime implicants that cover it; the cover is valid only if every one of those sums is true, so form their product:
One bracket per minterm, in the order 0, 1, 2, 5, 6, 7. The variables here are not the inputs of the circuit — \(P_i\) is true when prime implicant \(i\) is selected — so this is a Boolean expression about the design, not about the signals.
Multiply the product out with the ordinary theorems of Chapter 6, using \(X + XY = X\) to absorb any product that contains another, and \(XX = X\) to collapse repeats. Pairing the brackets that share a variable first keeps the work short:
Expanding and absorbing leaves five products, each of which is a valid irredundant cover:
Every product in \(P\) is a set of prime implicants that covers the function; the minimal solutions are the products with the fewest terms. Two of the five have three terms and the rest have four, so there are two minimal expressions:
Both have six literals and both were checked against all eight input combinations of the original minterm list. When a tie like this occurs the choice is made on other grounds — which literals are already available in complemented form, or which sharing opportunities exist with a neighbouring function on the same chip. Nothing in the algebra prefers one over the other.
The expansion is where the cost lies. A chart with \(m\) uncovered minterms and two candidate rows per column produces up to \(2^m\) products before absorption, so a cyclic core of twenty minterms is already a million products to generate and simplify. That is tolerable when dominance has cut the chart down to a handful of columns, which is the usual case, and intolerable when it has not.
Petrick's method is exact and it is also the step that makes exact minimisation expensive: the multiplied-out product can have an enormous number of terms before absorption removes most of them. In practice a program applies dominance first, uses Petrick only on the cyclic core that remains, and for large problems abandons exactness altogether — the Espresso minimiser used by every synthesis tool since the 1980s finds a near-minimal cover without ever enumerating all the prime implicants.
6 Don't-Cares, Cost and What a Computer Actually Does
Don't-care conditions enter the tabular method at one point and leave at another, and getting that the wrong way round is the commonest error in the whole procedure. A don't-care is included when the columns are generated, because it may allow a prime implicant to grow larger; it is excluded from the prime implicant chart, because no cover is obliged to include it.
Minimise the greater-than-four detector of Chapter 8: \(F(A,B,C,D) = \Sigma m(5,6,7,8,9) + \sum d(10,11,12,13,14,15)\).
Eleven terms enter the table — the five minterms and all six don't-cares. The combining passes run to four columns, because 8, 9, 10, 11, 12, 13, 14 and 15 merge into the single term 1---. The unticked entries are:
| Prime implicant | Code | Covers | 1s among them |
|---|---|---|---|
| \(A\) | 1--- | 8, 9, 10, 11, 12, 13, 14, 15 | 8, 9 |
| \(BD\) | -1-1 | 5, 7, 13, 15 | 5, 7 |
| \(BC\) | -11- | 6, 7, 14, 15 | 6, 7 |
The chart is now drawn with columns for 5, 6, 7, 8 and 9 only. Column 8 and column 9 hold crosses in the row of \(A\) alone; column 5 only in \(BD\); column 6 only in \(BC\). All three prime implicants are essential and
five literals, which is the answer the K-map gave in Chapter 8 — as it must, since both methods search the same set of prime implicants. Had the six don't-cares been excluded from the table, the largest implicants available would have been \(A'BD\), \(A'BC\) and \(AB'C'\), and the result would have carried nine literals instead of five.
What does the method cost? Each pass compares terms only across neighbouring weight groups, but the number of terms itself grows: an \(n\)-variable function has up to \(2^n\) minterms and up to \(3^n - 1\) possible product terms, and the worst-case number of prime implicants is of order \(3^n/n\). The covering step is worse than that. Choosing the fewest rows of a chart that cover all its columns is the minimum set-cover problem, which is NP-hard, so no known algorithm solves the general case in polynomial time.
| Variables \(n\) | Map cells \(2^n\) | Possible product terms \(3^n-1\) | Worst-case prime implicants \(\approx 3^n/n\) |
|---|---|---|---|
| 4 | 16 | 80 | 20 |
| 6 | 64 | 728 | 122 |
| 10 | 1 024 | 59 048 | 5 905 |
| 16 | 65 536 | 43 046 720 | 2 690 420 |
Those figures explain both halves of the chapter title. They are why the method is worth learning — nothing done by eye will handle the third row of that table — and why an exact minimiser is not what a synthesis tool runs on a real design. The tool takes the structure of Quine–McCluskey and replaces exhaustive prime implicant generation with heuristics that expand, reduce and reshape a cover in place. The vocabulary, though, is exactly the vocabulary of this chapter, and a report that says a design was reduced to a given number of product terms is quoting the size of a cover chosen from a chart of this kind.
7 Summary and Key Results
| Step | What is done | What it produces |
|---|---|---|
| Set up | List minterms and don't-cares in binary, grouped by number of 1s | Only adjacent groups can ever combine |
| Combining pass | Compare adjacent groups; one-bit difference → new term with a dash, tick both parents | The next column, one literal shorter |
| Repeat | Run further passes; dashes must align before two terms may combine | Stops when no pair anywhere can be merged |
| Collect | Every unticked entry in every column | The complete set of prime implicants |
| Chart | Rows = prime implicants, columns = minterms only (no don't-cares) | A covering problem set out for solution |
| Essential PIs | Any column with exactly one cross forces that row | Terms that appear in every minimal answer |
| Cyclic chart | No single cross, no dominance — apply Petrick's method | All minimal covers; pick the one with fewest literals |
8 Common Mistakes
A tick records that the term has been absorbed into a larger one, not that it was wrong. What matters is the opposite case: an unticked entry is a prime implicant wherever it appears, and the three prime implicants of the worked example that come from column II are exactly as important as the three from column III. Collecting only the last column's terms loses half the answer.
0-01 and -001 differ in one visible position, but they are terms over different variables — the first has lost \(B\), the second has lost \(A\) — and merging them is meaningless. Two terms combine only when their dashes occupy identical positions and their bits differ in exactly one place.
A don't-care belongs in the combining passes, where it can enlarge a prime implicant for free, and nowhere else. Giving it a column obliges the cover to include a minterm nobody asked for, and can force in an extra product term — the opposite of what don't-cares are for. The reverse error, leaving them out of the passes as well, simply throws the saving away.
9 Chapter Review
1. Why is it enough to compare each group of minterms only with the group immediately above it in weight?
Two codes that differ in exactly one bit position have one 1 where the other has a 0, so their weights differ by exactly one. Terms in the same group, or in groups two or more apart, cannot differ in a single bit and so can never combine. Restricting the comparisons to adjacent groups discards only pairs that were certain to fail: for the ten-minterm example of this chapter it cuts 45 comparisons to 23.
2. A column of a tabular minimisation contains the entries
0-01,-001,100-and10-0, of which only the first is unticked. What can be said about each?The unticked entry
0-01is a prime implicant, \(A'C'D\); no larger term contains it. The other three are implicants of the function but have each been absorbed into a term in the next column — for instance100-and10-0both lie inside larger terms formed with partners from the group above. They are correct terms, but they cannot appear in a minimal expression, so they play no further part.3. Apply the tabular method to \(F(A,B,C,D) = \Sigma m(1,3,4,5,10,11,12,13)\) and state the minimal sum.
The passes give five prime implicants: \(A'C'D\) (1, 5), \(A'B'D\) (1, 3), \(B'CD\) (3, 11), \(BC'\) (4, 5, 12, 13) and \(AB'C\) (10, 11). In the chart, columns 4 and 12 hold a single cross in the row of \(BC'\), and column 10 a single cross in the row of \(AB'C\), so both are essential; together they cover 4, 5, 12, 13, 10 and 11. Minterms 1 and 3 are left, and only \(A'B'D\) covers both, so \(F = BC' + AB'C + A'B'D\) — eight literals, verified against all sixteen input combinations.
4. A chart has four minterms \(w, x, y, z\) and four prime implicants, with \(w\) covered by \(P_1\) and \(P_2\), \(x\) by \(P_2\) and \(P_3\), \(y\) by \(P_3\) and \(P_4\), and \(z\) by \(P_4\) and \(P_1\). Solve it.
No column has a single cross, so the chart is cyclic and Petrick's method is needed. \(P = (P_1+P_2)(P_2+P_3)(P_3+P_4)(P_4+P_1)\). Pairing the first two and the last two gives \((P_2 + P_1P_3)(P_4 + P_1P_3)\), which multiplies out to \(P_2P_4 + P_1P_3(P_2 + P_4 + P_1P_3)\) and absorbs to \(P_1P_3 + P_2P_4\). There are therefore two minimal covers of two terms each, \(\{P_1, P_3\}\) and \(\{P_2, P_4\}\), and the cheaper is whichever has the fewer literals.
5. Roughly how many prime implicants can a six-variable function have, and what does that imply about minimising it on a Karnaugh map?
The worst case is of order \(3^n/n\), which for \(n = 6\) is \(729/6 \approx 122\). A six-variable map is drawn as four four-variable maps with adjacency between horizontal, vertical and diagonal pairs, and finding all 122 possible maximal groups across them by eye — then choosing a minimum cover from them — is not something a person does reliably. That is the point at which the tabular method, or a program built on it, has to take over.