Quine–McCluskey, by hand

Why a table instead of a map

A Karnaugh map depends on your eye. It is easy to miss a wrap-around group, and it stops being practical beyond four or five variables. The Quine–McCluskey (Q-M) method replaces looking with a mechanical procedure on bit patterns. It is slower by hand, but it cannot miss a prime implicant, and it works for any number of variables.

Q-M has two phases:

1. Find all prime implicants by merging terms repeatedly — this lesson.
2. Choose a minimal set of them with a cover chart — lesson 6.

The idea

Two terms combine by XY + XY = X when their bit patterns differ in exactly one position. That position becomes a dash: 0010 + 1010 → -010.

If two patterns differ in exactly one position, their counts of 1s differ by exactly one. So sort the minterms into groups by number of 1s, and you only ever need to compare a group with the next one.

Worked example

F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 13)

Step 1 — group the minterms by number of 1s

The ✓ marks are added during step 2: a term gets a check the moment it merges with anything.

Step 2 — merge neighbouring groups

Compare every term in one group with every term in the next. Where they differ in exactly one position, write the merged pattern in a new column and check off both parents.

Pairs that do not merge are just as important to check. For example 8 (1000) and 3 (0011) differ in three positions; 10 (1010) and 7 (0111) differ in three.

Step 3 — merge again

Repeat on the new column. Two patterns can merge only if their dashes are in the same positions and they differ in exactly one remaining bit.

Every group of four is found twice, by two different routes. Write it once. Nothing else merges: 001-, 0-11, 01-1 and -101 all have their dashes in different positions from each other, or differ in more than one bit.

There is only one term in the last column, so the merging stops.

Step 4 — collect the unchecked terms

Any term that never received a check could not be made larger. Those are the prime implicants. Read each pattern back as a product: 1 is the plain variable, 0 is the complemented variable, and a dash means the variable is gone.

Five prime implicants. ORing all five gives a correct expression for F, but not a minimal one — some of them are not needed. Here is the same function on a K-map, with all five drawn:

Choosing which to keep is the job of the cover chart, next.

The Quine–McCluskey tool builds these tables for any function you enter, so you can check your own columns line by line.

Don’t-cares in Q-M

Include the don’t-cares in step 1 as if they were minterms, so that they can help build larger terms. Then leave them out of the cover chart: they are allowed to be covered, but nothing has to cover them. A prime implicant that covers only don’t-cares is simply discarded.

Common mistakes

• Merging two patterns whose dashes are in different positions. 00-0 and -000 differ in two positions, not one — a dash is not a wildcard that matches a bit.
• Forgetting to check off both parents, which leaves a non-prime term looking prime.
• Stopping at the first merge a term takes part in. A term can merge with several partners; find all of them.
• Treating a term as prime because it appears in the last column. What makes a term prime is only that it has no check.

Check yourself

1. Which of these pairs merge, and into what? (a) 0110, 0111   (b) 0-01, 1-01   (c) 0-01, 01-1   (d) 0011, 0101
   Show answer

   (a) Yes: 011-. (b) Yes: --01. (c) No: the dashes are in different positions. (d) No: they differ in two positions, even though both have two 1s — which is why you compare a group with the next group, never with itself.
2. Find all prime implicants of F(A, B, C) = Σm(0, 1, 2, 3, 7) with Q-M.
   Show answer

   Groups: {0}, {1, 2}, {3}, {7}. First merge: 0,1 00-; 0,2 0-0; 1,3 0-1; 2,3 01-; 3,7 -11. Second merge: 00- + 01- = 0-- (and again from 0-0 + 0-1). Unchecked: 0-- = A and -11 = BC. Both are needed: F = A + BC.
3. In the worked example, why does -101 (5, 13) not merge with 01-1 (5, 7), even though both contain minterm 5?
   Show answer

   Sharing a minterm is not the test. To merge, the dashes must line up and exactly one other bit must differ. Here the dashes are in positions A and C respectively. On the K-map: cells 5, 7 and 13 form an L shape, not a rectangle.
4. A pattern with two dashes covers how many minterms? How many times will the procedure generate it?
   Show answer

   It covers 2² = 4 minterms, and it is generated twice — once for each way of pairing up its four minterms into two mergeable halves. (A pattern with three dashes is generated three times.)