BitFlow
← Academy·The Quine-McCluskey Method
QMGATE~30 min

The Quine-McCluskey Method

K-maps stop working at about five variables. This is the same idea as a step-by-step procedure a computer can follow.

Why another method

K-maps depend on your eye spotting rectangles. That's fine up to four variables and awkward at five, and past six you can't draw it at all. It's also no use to a computer. The Quine-McCluskey method, or tabular method, does the same job by a fixed procedure, so it works for any number of variables and it's guaranteed to find every prime implicant.

It has two stages. Find all the prime implicants by merging terms repeatedly, then choose the fewest primes that cover every minterm.

Stage 1: merge until nothing merges

The merging rule is the one behind every K-map group: two terms that differ in exactly one bit combine, and that bit disappears. xy + xy' = x. We write the vanished bit as a dash, so 0010 and 0110 merge into 0-10.

  1. Write each minterm in binary and sort them into groups by how many 1s they have.
  2. Compare each term with those in the next group. Two terms whose bits differ in just one place merge, so write the merged term in the next column and tick both.
  3. Repeat on the new column. Dashes must line up: 0-10 can merge with 0-11 but not with 01-0.
  4. Any term that never got ticked is a prime implicant.
TipSorting by the count of 1s saves work. Two terms that differ in one bit must have counts that differ by exactly one, so you only ever compare neighbouring groups.

Loading the animation…

Worked example: Is this a valid merge?

Can 01-1 and 11-1 merge? Can 01-1 and 0-11?

  1. 01-1 and 11-1 have their dash in the same place and differ only in the first bit. They merge into -1-1.
  2. 01-1 and 0-11 have their dashes in different places, so they can't merge.

Answer:Yes for the first, and no for the second.

Practice

What do 1001 and 1011 merge into?

Practice

A term with 2 dashes in a 4-variable function covers how many minterms?

Stage 2: the prime implicant chart

Now you have every prime, but you may not need them all. Draw a chart with the primes as rows and the minterms as columns, and mark which prime covers which minterm.

  1. Find columns with only one mark. That row is an essential prime, so take it.
  2. Cross off every minterm those primes cover.
  3. Choose from the remaining primes to cover what's left, as cheaply as you can.
Quine-McCluskey working

Terms that differ in one bit merge; the bit becomes a dash. A term that merges (crossed out) isn't prime. Rows are grouped by how many 1s they have, because only neighbouring groups can merge.

Minterms
0000
0001
0010
1000
0101
0110
1001
1010
0111
1110
Pass 1
000-
00-0
-000
0-01
-001
0-10
-010
100-
10-0
01-1
011-
-110
1-10
Pass 2
-00-
-0-0
--10
Prime implicant chart: the essential primes cover a column alone; the rest is the cheapest cover of what remains.
primeterm012567891014
0-01a'c'd××
01-1a'bd××
011-a'bc××
-00- *b'c'××××
-0-0b'd'××××
--10 *cd'××××
* essential. Green rows are the minimal answer.
abcd000111100001111001113021405171611201301501418191110101b'c'b'c'cd'a'bd
Grouping

F = b'c' + cd' + a'bd

The same function on a K-map, to compare. Six primes reduce to three terms: b'c' and cd' are essential, and a'bd picks up the last two cells, 5 and 7, in one term.

Don't-cares

Don't-cares are handled in one simple way, and it matches the K-map rule. Include them in stage 1, so they can make groups bigger. Leave them out of stage 2, since they don't need to be covered.

Watch outA common exam slip is to keep don't-care columns in the chart. That can make a prime look essential when it isn't.
Practice

Why are don't-cares left out of the chart's columns?

Cyclic charts and Petrick's methodGATE: fine to skip at first

Sometimes no column has a single mark, so there are no essential primes. The function Σm(0, 1, 2, 5, 6, 7) from the last chapter is like this. You can pick a prime and continue, but that doesn't guarantee the best answer.

Petrick's method does. Write the requirement as logic, with one variable per prime. Each column says "at least one of the primes that cover me", so it's an OR, and all columns must hold, so they're ANDed. Multiply it out, and each product term is one valid cover. Pick the cheapest.

Worked example: Petrick on a small chart

Prime P covers minterms 1 and 2. Q covers 2 and 3. R covers 1 and 3. Find the smallest covers.

  1. Minterm 1 needs (P + R). Minterm 2 needs (P + Q). Minterm 3 needs (Q + R).
  2. Multiply: (P + R)(P + Q)(Q + R).
  3. (P + R)(P + Q) = P + QR, by the distributive law.
  4. (P + QR)(Q + R) = PQ + PR + QR.

Answer:Any two of the three primes will do: PQ, PR or QR.

The algebra behind that example
  1. (P + R)(P + Q)(Q + R)every minterm must be covered
Step 1 of 3

The method's cost is its limit. A function of n variables can have roughly 3ⁿ/n primes, so the chart can grow enormous. Finding the true minimum is NP-hard, which is why synthesis tools use heuristics such as Espresso, which find very good answers without promising the best one.

Practice · GATE-style

A 4-variable function's prime implicant is written -1-0. What term is it?

Practice · GATE-style

Which stage of Quine-McCluskey includes the don't-care terms?

See the working for your own function →The truth table tool shows every Quine-McCluskey pass and the chart for any function up to 6 variables.
Was this chapter helpful?