Quine-McCluskey and Prime Implicants
Find every prime implicant by merging terms in a table. Then pick the cover from a chart, with no picture at all.
You Will Be Able To
- Sort minterms into groups by their number of 1s.
- Merge terms that differ in one bit until nothing merges.
- Build the prime implicant chart and find the essential primes.
- Shrink the chart with column dominance and row dominance.
- Lesson
- G3.5
- Time
- 35 min
- Runs on
- Your browser
- Check
- 5 questions
A map works when you can see the groups. A program cannot see. It needs rules that always give the same answer. The Quine-McCluskey method is such a set of rules.
| Stage of the method | What it holds for the pump function |
|---|---|
| Column 1: minterms | 11 terms |
| Column 2: pairs | 15 terms |
| Column 3: groups of four | 5 terms |
| Prime implicants | 6 terms |
| Minimum cover | 4 terms, 9 literals |
Generated by the merging code of this lesson and checked against the exact minimizer.
Sort the Minterms by Their 1s
- Neutral
- Step
- Structure
- Find the candidates
Merging finds every prime implicant. No choice is made yet.
- Choose among them
The chart takes the essential primes, then dominance removes rows and columns.
- Finish
The chart ends empty with a cover, or stuck as a cyclic chart.
Read the diagram as text
- Minterms: sorted by their 1s
- Merge: differ in one bit
- Prime implicants: never checked off
- Chart: primes against 1s
- Essential primes: a column with one X
- Dominance: drop lines that cannot help
- Minimum cover: or a cyclic chart
- Minterms → Merge: compare
- Merge → Prime implicants: repeat
- Prime implicants → Chart: rows
- Chart → Essential primes: take
- Essential primes → Dominance: shrink
- Dominance → Minimum cover: done
The method needs no picture, so it works for any number of variables.
The pump function is f = Σm(2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15). Write each minterm in binary and sort the list by its number of 1s.
| Number of 1s | Minterm | abcd |
|---|---|---|
| 1 | 2 | 0010 |
| 1 | 4 | 0100 |
| 1 | 8 | 1000 |
| 2 | 3 | 0011 |
| 2 | 5 | 0101 |
| 2 | 9 | 1001 |
| 2 | 12 | 1100 |
| 3 | 7 | 0111 |
| 3 | 11 | 1011 |
| 3 | 13 | 1101 |
| 4 | 15 | 1111 |
Column 1 of the method. Two terms can differ in one bit only if their 1-counts differ by one.
So you only compare each term with the group just below it. That saves most of the comparisons.
Merge Terms That Differ in One Bit
Two terms merge when they differ in exactly one bit. Put a dash in that bit. Check off both terms: each now sits inside a larger one.
Column 1 to column 2
Compare neighbouring groups. 15 pairs appear. Every minterm merges at least once.
Column 2 to column 3
Merge pairs with dashes in the same place. 5 groups of four appear. One pair,
001-, merges with nothing.Column 3
No two groups of four have their dashes in the same places and differ in one bit. The merging stops.
Read the primes
Every term without a check mark is a prime implicant. There are 6.
| Column | Term (abcd) | Rows it holds | Merged? | Product |
|---|---|---|---|---|
| 2 | 001- | 2, 3 | no: prime | a'b'c |
| 3 | -10- | 4, 5, 12, 13 | no: prime | bc' |
| 3 | 1-0- | 8, 9, 12, 13 | no: prime | ac' |
| 3 | --11 | 3, 7, 11, 15 | no: prime | cd |
| 3 | -1-1 | 5, 7, 13, 15 | no: prime | bd |
| 3 | 1--1 | 9, 11, 13, 15 | no: prime | ad |
The unmerged pair and column 3. A dash means the variable leaves the term.
Open the full column 2 (15 pairs)
| Number of 1s | Term (abcd) | Rows it holds | Merged? |
|---|---|---|---|
| 1 | 001- | 2, 3 | no |
| 1 | -100 | 4, 12 | yes |
| 1 | 010- | 4, 5 | yes |
| 1 | 1-00 | 8, 12 | yes |
| 1 | 100- | 8, 9 | yes |
| 2 | -011 | 3, 11 | yes |
| 2 | 0-11 | 3, 7 | yes |
| 2 | -101 | 5, 13 | yes |
| 2 | 01-1 | 5, 7 | yes |
| 2 | 1-01 | 9, 13 | yes |
| 2 | 10-1 | 9, 11 | yes |
| 2 | 110- | 12, 13 | yes |
| 3 | -111 | 7, 15 | yes |
| 3 | 1-11 | 11, 15 | yes |
| 3 | 11-1 | 13, 15 | yes |
A pair that merges is checked off. Only 001- survives as a prime.
The Prime Implicant Chart
The primes are the candidates. Now choose the fewest that cover every 1. Draw a chart: one row per prime, one column per 1 of f.
| Prime | 2 | 3 | 4 | 5 | 7 | 8 | 9 | 11 | 12 | 13 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|
a'b'c | X | X | |||||||||
bc' | X | X | X | X | |||||||
ac' | X | X | X | X | |||||||
cd | X | X | X | X | |||||||
bd | X | X | X | X | |||||||
ad | X | X | X | X |
An X means the prime holds that row. Columns 2, 4, 8 each have one X.
A column with one X has only one way to be covered. That prime is essential. Here the essential primes are a'b'c, bc', ac'.
Take them, and cross out every column they hold. Only the columns 7, 11 and 15 are left.
| Prime | 7 | 11 | 15 |
|---|---|---|---|
cd | X | X | X |
bd | X | X | |
ad | X | X |
The chart after the essential primes. No column has one X now.
Dominance Finishes the Chart
Two rules shrink a chart that has no single X. Each removes a line that can never help.
Column dominance
Column 15 has an X in every row where column 7 has one. Covering 7 covers 15 too, so cross out column 15.
Row dominance
Row
cdholds every column that rowbdholds, at no more literals. So dropbd.A secondary essential prime
Now column 7 has one X, in row
cd. Take it. It also covers column 11.The cover
The chart is empty: f = a'b'c + bc' + ac' + cd. That is 4 terms and 9 literals, the minimum.
| Rule | Keep | Remove | Why it is safe |
|---|---|---|---|
| Column dominance | the column whose X rows are all in the other column | the column that holds every X row of another | any row that covers the kept column also covers the other |
| Row dominance | the row whose X columns include the other row's | a row whose X columns all sit in a cheaper or equal row | the kept row does the same job, or more, for no more literals |
Dominance is containment, not a count: compare which rows or columns hold the X, not how many.
Sometimes no rule applies and the chart still has columns. That chart is cyclic. Lesson G3.6 solves it with Petrick's method.
Asked in interviews
What does the Quine-McCluskey method do?
It finds all prime implicants by merging terms that differ in one bit. Then a chart picks the fewest primes that cover every 1.
What is an essential prime implicant?
It is the only prime that holds some 1 of the function. On the chart, it is the X alone in a column. Every minimum cover uses it.
Why do tools not run this method on big designs?
The number of primes can grow very fast with the number of inputs. Tools use faster heuristic minimizers and accept a cover that may not be minimal.
Try It
The table holds terms, as in earlier labs. This bench does not check a cover. It says whether each term is a prime implicant, and counts how many of the six you listed.
The starter lists the three essential primes and a'cd. The bench calls a'cd an implicant that is not prime: it sits inside cd.
List all six primes: N = 6, CARE = {4'b1001, 4'b0101, 4'b0011, 4'b1010, 4'b0110, 4'b1110} and VALUE = {4'b1001, 4'b0101, 4'b0011, 4'b1000, 4'b0100, 4'b0010}. The bench prints 6 of 6 prime implicants listed.
Then drop one more literal from cd, to make it d. The bench prints d: holds a 0 of f.
a'b'c: prime implicant bc': prime implicant ac': prime implicant a'cd: implicant, not prime 3 of 6 prime implicants listedRead included file: tb.sv
// tb.sv: the bench (read-only). For each term of the table in module answer it prints whether the term
// holds a 0 of f, is an implicant that is not prime, or is a prime implicant. Then it counts the primes.
module tb;
// Bit m is f on row m, where m is the binary value of abcd. DC marks the don't-care rows.
localparam logic [15:0] F = 16'b1011101110111100;
localparam logic [15:0] DC = 16'b0000000000000000;
wire [7:0] n;
wire [31:0] care, value;
answer ans (.n(n), .care(care), .value(value));
// An implicant holds no row where f is 0.
function automatic logic implicant(input logic [3:0] c, input logic [3:0] v);
for (int m = 0; m < 16; m++)
if (((m[3:0] ^ v) & c) == '0 && !F[m] && !DC[m]) return 1'b0;
return 1'b1;
endfunction
// A prime implicant stops being an implicant when any one of its literals is dropped.
function automatic logic prime(input logic [3:0] c, input logic [3:0] v);
logic [3:0] one;
if (!implicant(c, v)) return 1'b0;
for (int i = 0; i < 4; i++) begin
one = '0;
one[i] = 1'b1;
if (c[i] && implicant(c & ~one, v & ~one)) return 1'b0;
end
return 1'b1;
endfunction
function automatic string tname(input logic [3:0] c, input logic [3:0] v);
string s;
s = "";
for (int i = 3; i >= 0; i--) if (c[i]) begin
case (i)
3: s = {s, "a"};
2: s = {s, "b"};
1: s = {s, "c"};
0: s = {s, "d"};
endcase
if (!v[i]) s = {s, "'"};
end
if (s == "") s = "1";
return s;
endfunction
initial begin
int found;
logic [3:0] c, v;
logic again;
#1; // let the table reach the wires
found = 0;
for (int t = 0; t < 8; t++) if (t < n) begin
c = care[4*t +: 4];
v = value[4*t +: 4] & c;
again = 1'b0;
for (int u = 0; u < t; u++)
if (care[4*u +: 4] == c && (value[4*u +: 4] & c) == v) again = 1'b1;
if (!implicant(c, v)) $display("%s: holds a 0 of f", tname(c, v));
else if (!prime(c, v)) $display("%s: implicant, not prime", tname(c, v));
else begin
$display("%s: prime implicant", tname(c, v));
if (!again) found++;
end
end
$display("%0d of 6 prime implicants listed", found);
end
endmodule
Check Yourself
Common Mistakes
Wrong Merge two terms whose dashes sit in different places.
0-01 and -101 differ in more than one place, so no single cube holds both.
Fix Merge only terms with dashes in the same places that differ in one more bit.
Wrong Call a prime essential because it holds many 1s.
Size does not matter. A prime is essential when some 1 has no other prime.
Fix Look for a chart column with exactly one X.
Wrong Stop after the essential primes.
They may leave some 1s uncovered, as they leave rows 7, 11 and 15 here.
Fix Remove the covered columns, then apply dominance until the chart is empty.
Wrong Put the don't-care rows into the chart as columns.
A don't-care never needs covering, so it must not force a choice.
Fix Use don't-cares in the merging columns only. The chart has one column per 1 of f.
Remember
- Sort the minterms by their number of 1s; only neighbouring groups can merge.
- Merge terms that differ in one bit, with dashes in the same places; the terms never checked off are the primes.
- On the chart, a column with one X makes its prime essential.
- Dominance is containment. Drop a column that holds another column's X rows, and a row covered by a cheaper or equal row.