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 methodWhat it holds for the pump function
Column 1: minterms11 terms
Column 2: pairs15 terms
Column 3: groups of four5 terms
Prime implicants6 terms
Minimum cover4 terms, 9 literals

Generated by the merging code of this lesson and checked against the exact minimizer.

Sort the Minterms by Their 1s

The Two Halves of the MethodArrows show the order of the work. The left column finds the candidates; the right column chooses among them.
  • Neutral
  • Step
  • Structure
The two halves of the methodArrows show the order of the work. The left column finds the candidates; the right column chooses among them. neutral Minterms sorted by their 1s step Merge differ in one bit neutral Prime implicants never checked off neutral Chart primes against 1s neutral Essential primes a column with one X step Dominance drop lines thatcannot help neutral Minimum cover or a cyclic chart comparerepeatrowstakeshrinkdone
  1. neutral Mintermssorted by their 1s
    • compare → Merge
  2. step Mergediffer in one bit
    • repeat → Prime implicants
  3. neutral Prime implicantsnever checked off
    • rows → Chart
  4. neutral Chartprimes against 1s
    • take → Essential primes
  5. neutral Essential primesa column with one X
    • shrink → Dominance
  6. step Dominancedrop lines that cannot help
    • done → Minimum cover
  7. neutral Minimum coveror a cyclic chart
  1. Find the candidates

    Merging finds every prime implicant. No choice is made yet.

  2. Choose among them

    The chart takes the essential primes, then dominance removes rows and columns.

  3. 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 1sMintermabcd
120010
140100
181000
230011
250101
291001
2121100
370111
3111011
3131101
4151111

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.

  1. Column 1 to column 2

    Compare neighbouring groups. 15 pairs appear. Every minterm merges at least once.

  2. Column 2 to column 3

    Merge pairs with dashes in the same place. 5 groups of four appear. One pair, 001-, merges with nothing.

  3. Column 3

    No two groups of four have their dashes in the same places and differ in one bit. The merging stops.

  4. Read the primes

    Every term without a check mark is a prime implicant. There are 6.

ColumnTerm (abcd)Rows it holdsMerged?Product
2001-2, 3no: primea'b'c
3-10-4, 5, 12, 13no: primebc'
31-0-8, 9, 12, 13no: primeac'
3--113, 7, 11, 15no: primecd
3-1-15, 7, 13, 15no: primebd
31--19, 11, 13, 15no: primead

The unmerged pair and column 3. A dash means the variable leaves the term.

Open the full column 2 (15 pairs)
Number of 1sTerm (abcd)Rows it holdsMerged?
1001-2, 3no
1-1004, 12yes
1010-4, 5yes
11-008, 12yes
1100-8, 9yes
2-0113, 11yes
20-113, 7yes
2-1015, 13yes
201-15, 7yes
21-019, 13yes
210-19, 11yes
2110-12, 13yes
3-1117, 15yes
31-1111, 15yes
311-113, 15yes

A pair that merges is checked off. Only 001- survives as a prime.

The six prime implicants on the map
ab / cd00011110
00
01
11
10

~a & ~b & c | b & ~c | a & ~c | c & d

Minimum SOP: 4 terms · 9 literals.

The table found the same groups that the map shows. It did so without looking.

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.

Prime234578911121315
a'b'cXX
bc'XXXX
ac'XXXX
cdXXXX
bdXXXX
adXXXX

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.

Prime71115
cdXXX
bdXX
adXX

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.

  1. 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.

  2. Row dominance

    Row cd holds every column that row bd holds, at no more literals. So drop bd.

  3. A secondary essential prime

    Now column 7 has one X, in row cd. Take it. It also covers column 11.

  4. The cover

    The chart is empty: f = a'b'c + bc' + ac' + cd. That is 4 terms and 9 literals, the minimum.

RuleKeepRemoveWhy it is safe
Column dominancethe column whose X rows are all in the other columnthe column that holds every X row of anotherany row that covers the kept column also covers the other
Row dominancethe row whose X columns include the other row'sa row whose X columns all sit in a cheaper or equal rowthe 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.

The cover the chart chose
ab / cd00011110
00
01
11
10

~a & ~b & c | b & ~c | a & ~c | c & d

Minimum SOP: 4 terms · 9 literals.

f = a'b'c + bc' + ac' + cd. The primes `bd` and `ad` are left out.

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
  1. 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.

  2. 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.

  3. 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.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: a'b'c: prime implicant bc': prime implicant ac': prime implicant a'cd: implicant, not prime 3 of 6 prime implicants listed
Read 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

Predict the outputThe program XORs minterms 9 and 11 of the pump function. Predict the exact line it prints.
module tb;
  logic [3:0] x, y;
  initial begin
    x = 4'b1001;                 // minterm 9
    y = 4'b1011;                 // minterm 11
    $display("%b", x ^ y);
  end
endmodule
Spot the bugEach option is an expression for the pump function. The bench compares it with f on all 16 rows. Which one fails?
ConceptA chart column has an X in rows P and Q. Another column has an X in rows P, Q and R. Which column can you cross out?
ConceptRow bd holds only column 7. Row cd holds columns 7 and 11. Both have two literals. What does row dominance do?
ConceptIn the merging columns, a term never gets a check mark. What is it?

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.

Practice

Report a problem with this page