The Quine-McCluskey Method
In the previous articles we minimised functions by drawing them. In this one we look at what to do when drawing is not an option. A synthesis tool working on a design with a 32-bit comparator and a 16-state state machine has to minimise dozens of functions of ten or twenty variables. Nobody can draw a 20-variable map, and no one could see all the adjacencies in a million cells if they did. What is needed is a procedure that does what the map does without needing eyes, and that is the Quine-McCluskey method, developed by Willard Quine in 1952 and Edward McCluskey in 1956.
Where maps run out
Maps work well up to four variables. At five you need two 4×4 planes and have to track adjacencies between them, which is possible but tiring. At six you have four planes. Beyond that the answer to “can I see all the adjacencies?” is no. And even at four variables, a person doing the tenth problem of the evening misses the corner group. An algorithm does not get tired.
The method in outline
Quine-McCluskey has two phases, which correspond exactly to the two steps of the map method.
Phase 1 finds all the prime implicants. It repeatedly merges pairs of terms that differ in exactly one variable, until nothing more will merge. The terms left over that were never absorbed into a larger merge are the prime implicants.
Phase 2 chooses a minimum cover. A chart shows which prime implicant covers which minterm, and from it you pick the smallest set that covers everything.
The idea behind phase 1 is the same one behind the map: two minterms that differ in one bit combine into a term with that bit removed. The map finds such pairs by adjacency; Quine-McCluskey finds them by comparing bit patterns.
Phase 1: finding the prime implicants
Group the minterms by the number of 1s in their binary form. Two patterns can differ in exactly one bit only if their counts of 1s differ by exactly one, so you only ever compare a group with the next one up. This cuts the number of comparisons a great deal.
Merge across adjacent groups. Compare every term in one group with every term in the next. Where two differ in exactly one bit, write the merged term with a dash in that position, and tick both source terms to say they have been absorbed. For example 0101 and 0111 differ in the second bit from the right and merge to 01-1.
Repeat on the merged terms. Two merged terms combine if their dashes are in the same positions and they differ in exactly one other bit. Keep going until a pass produces no new merges.
Collect the unticked terms. Anything that was never absorbed is a prime implicant.
A worked example
$$F = \sum m(0, 1, 2, 5, 6, 7, 8, 9, 10, 13, 14, 15)$$
Twelve of the sixteen minterms of a 4-variable function of A, B, C, D, with A the most significant bit.
Group by number of 1s
| Ones | Minterms |
|---|---|
| 0 | 0 (0000) |
| 1 | 1 (0001), 2 (0010), 8 (1000) |
| 2 | 5 (0101), 6 (0110), 9 (1001), 10 (1010) |
| 3 | 7 (0111), 13 (1101), 14 (1110) |
| 4 | 15 (1111) |
First merge
Compare each group with the next. Every pair that differs in one bit produces a merged term:
| From | Merged term |
|---|---|
| 0, 1 | 000- |
| 0, 2 | 00-0 |
| 0, 8 | -000 |
| 1, 5 | 0-01 |
| 1, 9 | -001 |
| 2, 6 | 0-10 |
| 2, 10 | -010 |
| 8, 9 | 100- |
| 8, 10 | 10-0 |
| 5, 7 | 01-1 |
| 5, 13 | -101 |
| 6, 7 | 011- |
| 6, 14 | -110 |
| 9, 13 | 1-01 |
| 10, 14 | 1-10 |
| 7, 15 | -111 |
| 13, 15 | 11-1 |
| 14, 15 | 111- |
Every one of the twelve minterms took part in at least one merge, so none of them is a prime implicant on its own.
Second merge
Now merge the two-cell terms. Two combine if their dashes match and one other bit differs:
| From | Merged term | Covers |
|---|---|---|
| 000- and 100- | -00- | 0, 1, 8, 9 |
| 00-0 and 10-0 | -0-0 | 0, 2, 8, 10 |
| 0-01 and 1-01 | –01 | 1, 5, 9, 13 |
| 0-10 and 1-10 | –10 | 2, 6, 10, 14 |
| 01-1 and 11-1 | -1-1 | 5, 7, 13, 15 |
| 011- and 111- | -11- | 6, 7, 14, 15 |
Several other pairs produce the same terms again (for example -000 and -001 also give -00-), which is normal; duplicates are simply discarded. When you check, every two-cell term has been absorbed into one of these six. No further merges are possible among the four-cell terms, since no two of them have their dashes in the same positions.
The prime implicants
| Term | Cells | Expression | |
|---|---|---|---|
| P1 | -00- | 0, 1, 8, 9 | $B’C'$ |
| P2 | -0-0 | 0, 2, 8, 10 | $B’D'$ |
| P3 | –01 | 1, 5, 9, 13 | $C’D$ |
| P4 | –10 | 2, 6, 10, 14 | $CD'$ |
| P5 | -1-1 | 5, 7, 13, 15 | $BD$ |
| P6 | -11- | 6, 7, 14, 15 | $BC$ |
Phase 2: the prime implicant chart
One row per prime implicant, one column per minterm:
| 0 | 1 | 2 | 5 | 6 | 7 | 8 | 9 | 10 | 13 | 14 | 15 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| P1 $B’C'$ | X | X | X | X | ||||||||
| P2 $B’D'$ | X | X | X | X | ||||||||
| P3 $C’D$ | X | X | X | X | ||||||||
| P4 $CD'$ | X | X | X | X | ||||||||
| P5 $BD$ | X | X | X | X | ||||||||
| P6 $BC$ | X | X | X | X |
Look for columns with a single X. There are none: every minterm is covered by exactly two prime implicants. This function has no essential prime implicants, so we cannot take the easy route and have to choose a cover deliberately.
Petrick’s method
When essential implicants do not finish the job, Petrick’s method finds an exact minimum cover. For each minterm, write the sum of the implicants that cover it; then AND all the sums together and expand. Each product term in the expansion is a valid cover.
For our chart:
$$(P_1 + P_2)(P_1 + P_3)(P_2 + P_4)(P_3 + P_5)(P_4 + P_6)(P_5 + P_6)(P_1 + P_2)(P_1 + P_3)(P_2 + P_4)(P_3 + P_5)(P_4 + P_6)(P_5 + P_6)$$
The second half repeats the first, so it reduces to
$$(P_1 + P_2)(P_1 + P_3)(P_2 + P_4)(P_3 + P_5)(P_4 + P_6)(P_5 + P_6)$$
Expanding, the smallest products have three implicants: $P_1 P_4 P_5$ and $P_2 P_3 P_6$. So there are two minimal covers, each with three 2-literal terms:
$$F = B’C’ + CD’ + BD \qquad \text{or} \qquad F = B’D’ + C’D + BC$$
Figures 1 and 2 show both on the map. Each is a cyclic pattern of three groups of four, and neither is better than the other.
You would probably have found one of these on the map without much trouble. The point of working it through by hand is that the algorithm found both, mechanically, without anyone having to notice anything, and it would have done the same with twelve variables.
Petrick’s method is exhaustive and exponential in the worst case. For homework it is rarely needed, because essential implicants usually cover everything or leave one obvious choice. Inside tools it is replaced by heuristics.
Espresso and what synthesis tools do
You will probably never run Quine-McCluskey by hand again after this article. The reason to know it is that it is a model of what your synthesis tool does when it turns RTL into gates.
The Espresso algorithm, from Berkeley in 1984, is the minimiser inside most synthesis tools. It works on the same prime implicant idea with several improvements. It represents terms as cubes rather than strings with dashes. It minimises several outputs at once and shares implicants between them. It searches heuristically, expanding and reducing cubes iteratively, rather than generating every prime implicant, because the number of prime implicants can itself be exponential in the number of variables. And it handles don’t-cares natively during the expansion step. The result is not always the true minimum, but it is close, and it runs on functions with hundreds of inputs.
When Vivado or Yosys tells you that a block of RTL became some number of LUTs or cells, that number is partly a measure of how well the minimiser did. Knowing what prime implicants and covers are lets you read that report with some understanding rather than as a black box.
| Method | Good for | Limit |
|---|---|---|
| Map, 2 to 4 variables | Quick work by hand | None worth mentioning |
| Map, 5 to 6 variables | Careful work by hand | Error-prone |
| Quine-McCluskey | Any size, exact, mechanical | Exponential in the worst case |
| Espresso and successors | Real designs, hundreds of inputs | Heuristic, not always minimal |
Practice Exercise
Apply Quine-McCluskey to $F = \sum m(1, 3, 5, 7, 9, 11)$ and check the answer on a map.
Solution
Group by number of 1s: one 1: {1 (0001)}; two 1s: {3 (0011), 5 (0101), 9 (1001)}; three 1s: {7 (0111), 11 (1011)}.
First merge: 1,3 → 00-1; 1,5 → 0-01; 1,9 → -001; 3,7 → 0-11; 5,7 → 01-1; 3,11 → -011; 9,11 → 10-1. All six minterms absorbed.
Second merge: 00-1 and 10-1 → -0-1 (1, 3, 9, 11); 0-01 and 0-11 → 0–1 (1, 3, 5, 7); -001 and -011 → -0-1 again; 00-1 and 01-1 → 0–1 again. Every two-cell term is absorbed into one of these two.
Prime implicants: $B’D$ (1, 3, 9, 11) and $A’D$ (1, 3, 5, 7).
Chart: 5 and 7 are covered only by $A’D$, and 9 and 11 only by $B’D$, so both are essential. $F = A’D + B’D = D(A’ + B’)$.
On the map, the left group of four (rows 00 and 01, columns 01 and 11) is $A’D$, and the wrap-around group (rows 00 and 10, same columns) is $B’D$. Same answer.
That completes the section on minimisation. In section 1.5 we put the gates to work and build the standard combinational blocks: multiplexers, decoders, encoders and comparators.