digiwleeaLearn
Open the lab →

Quine-McCluskey minimization

The algorithm that minimizes when a K-map cannot

10 min read

Quine-McCluskey is a tabular, exhaustive algorithm for minimizing a boolean function: it systematically combines minterms that differ in one bit to find every prime implicant, then uses a prime-implicant chart to select a minimum-cost cover, succeeding where Karnaugh maps become unreadable past five or six variables.

Builds onKarnaugh mapsCanonical forms: minterms and maxterms
A Karnaugh map minimizes logic by letting you *see* which minterms combine. That works beautifully for three or four variables, but vision fails fast: nobody can eyeball adjacency in a six-dimensional grid. Quine-McCluskey (Q-M) is the same merging idea turned into a mechanical table, so it stays correct at any number of variables and a computer can run it. It is the rigorous backbone of the logic-minimization tools inside every chip-design (CAD) flow.

Why Karnaugh maps run out

A K-map relies on physical adjacency on paper. Four variables is 16 cells (fine), five is 32 (two maps stacked), six is 64 (four maps, error-prone), and beyond that the picture is hopeless because a single cell now has too many neighbors to draw flat. Q-M throws away the picture and keeps only the rule that made it work: two terms combine when they differ in exactly one bit. It runs in two phases: first find *every* prime implicant, then choose a smallest set of them that covers all the 1s.
Think of it as a knockout tournament for terms. Round one pairs up minterms that differ in one bit, merging each pair into a shorter term with a dash (-) marking the bit that cancelled. Round two pairs up *those* merged terms the same way, and so on. A term that never finds a partner to merge with has gone as far as it can: it is a prime implicant, a survivor of the bracket.

Phase 1: find the prime implicants

  1. Write every minterm of the function in binary, and include any don't-care terms (they may help things combine). Drop the rows where the output is 0.
  2. Group the terms by their **number of 1s**. Two terms can differ in one bit only if their 1-counts differ by one, so only neighboring groups ever combine.
  3. Compare each term in a group with each term in the next group up. If they differ in exactly one bit, write a new term with a dash (-) in that position and check off both source terms (they are now covered by the merged term).
  4. Repeat the whole process on the list of merged terms: two size-2 implicants combine if their dashes are in the same place and they differ in one of the remaining bits, giving a size-4 implicant. Keep going until nothing more combines.
  5. Every term that was never checked off at any stage is a prime implicant: a group of 1s that cannot be made any larger. Collect them all.

Worked example: a 4-variable run

Minimize F(A,B,C,D) = Sigma m(0,1,2,8,10,11,14,15). Writing each minterm as ABCD and grouping by the count of 1s gives five starting groups (0 ones, 1 one, 2 ones, 3 ones, 4 ones):
1sMintermABCD
000000
110001
120010
181000
2101010
3111011
3141110
4151111
The eight minterms, grouped by their number of 1s. Combining only ever happens between adjacent groups (a 1-count difference of exactly one), which keeps the comparisons few.
Comparing adjacent groups, every pair that differs in one bit merges (the cancelled bit becomes a dash). Each merged term is then compared again to build size-4 groups. The terms that survive with no further merge are the prime implicants:
  1. Round one merges, for example, 0 (0000) with 2 (0010) into 00-0, and 2 (0010) with 10 (1010) into -010. Both 0 and 2 get checked off; a minterm can take part in several merges.
  2. -010 and -000 share their dash position and differ in one bit, merging into -0-0 (covering 0,2,8,10). Independently 101- and 111- merge into 1-1- (covering 10,11,14,15). These size-4 terms cannot grow further.
  3. One pair never finds a same-position partner: 0 with 1 gives 000- (covering 0,1) and stays put. It is a prime implicant on its own.
  4. Reading off the surviving terms: P1 = -0-0 = B'D', P2 = 1-1- = A·C, and P3 = 000- = A'·B'·C'. Those three are the complete set of prime implicants.

Phase 2: the prime-implicant chart

Now decide which prime implicants to keep. Draw a chart with one row per prime implicant and one column per minterm of the function (don't-cares get no column, you never need to cover them). Mark X where a prime implicant covers a minterm:
Prime implicantm0m1m2m8m10m11m14m15
P1 = B'D'XXXX
P2 = A·CXXXX
P3 = A'B'C'XX
The prime-implicant chart. A column with a single X pins down an essential prime implicant: m1 is covered only by P3, m2 only by P1, and m11 (also m14, m15) only by P2.
  1. Find the essential prime implicants: any minterm covered by exactly one prime implicant forces that implicant into the answer. Column m1 has its only X in P3, m2 only in P1, and m11 only in P2, so all three are essential.
  2. Mark the minterms those essentials cover. Here P1, P2, P3 together cover {0,1,2,8,10,11,14,15}, which is every minterm, so the cover is complete.
  3. Read the minimal sum of products straight off the chosen rows: F = B'D' + A·C + A'·B'·C'. Three terms, seven literals, down from the eight 4-literal minterms you started with.
Here every prime implicant turned out essential, the easy case. Often the essentials leave a few minterms still uncovered, and several prime implicants could finish the job at different costs. That residual choice is a minimum set-cover problem, and Petrick's method solves it exactly: write a product-of-sums saying 'each leftover minterm must be covered by one of these implicants', multiply it out to a sum of products, and the cheapest product term names the cheapest cover. Q-M plus Petrick is guaranteed to find a true minimum two-level form, which is why it, not a hand-drawn map, is the reference algorithm.
Common mistakes. Only compare **adjacent 1-count groups**; terms whose counts differ by two can never combine. When two terms merge you must check off *both*, and a single term may legally combine into several different merges, so do not stop at its first partner. Two implicants can only merge if their dashes are in the same positions. Include don't-cares while *finding* prime implicants (they enlarge groups for free) but give them no column in the chart, since you are not required to cover them. And keep iterating until a full pass produces no new merge, or you will miss a larger prime implicant.

Full walkthrough: watch a prime implicant get dropped

Time to run the whole machine end to end on a fresh function, and this time not every prime implicant will survive the chart. Minimize F(A,B,C,D) = Sigma m(0,1,3,7,8,9,10,11,15), nine minterms. Write each as ABCD and sort into groups by the number of 1s:
1sMintermABCD
000000
110001
181000
230011
291001
2101010
370111
3111011
4151111
The nine minterms grouped by 1-count: one term with zero 1s, two with one, three with two, two with three, and 15 alone with four.
Round one compares each term with the group above it and keeps the pairs that differ in a single bit (the cancelled bit becomes a dash). Every one of the nine minterms finds at least one partner, so none survives as a prime implicant yet. The twelve size-2 implicants are 000- (0,1), -000 (0,8), 00-1 (1,3), -001 (1,9), 100- (8,9), 10-0 (8,10), 0-11 (3,7), -011 (3,11), 10-1 (9,11), 101- (10,11), -111 (7,15), and 1-11 (11,15).
Round two merges those size-2 terms whenever their dashes line up and exactly one remaining bit differs. Four size-4 implicants come out, each reachable two different ways (which just confirms the merge): -00- from 000-+100-, -0-1 from 00-1+10-1, 10-- from 100-+101-, and --11 from 0-11+1-11. Every size-2 term gets checked off, so none of them is prime. A third round finds no two size-4 terms sharing dash positions, so merging stops and those four are the complete prime-implicant set:
Prime implicantCoversABCD
P1 = B'·C'0,1,8,9-00-
P2 = B'·D1,3,9,11-0-1
P3 = A·B'8,9,10,1110--
P4 = C·D3,7,11,15--11
The four prime implicants in dash notation. A dash marks a variable that cancelled, so -00- fixes only B=0, C=0, giving the product term B'·C'.
Now the chart. One row per prime implicant, one column per minterm of F, and an X wherever the implicant covers that minterm:
Prime implicantm0m1m3m7m8m9m10m11m15
P1 = B'C'XXXX
P2 = B'DXXXX
P3 = A·B'XXXX
P4 = C·DXXXX
The prime-implicant chart. Columns m0, m7, m10, and m15 each hold a single X, which pins down the essential prime implicants.
  1. Scan for single-X columns. m0 is covered only by P1, m10 only by P3, and both m7 and m15 only by P4. So P1, P3, and P4 are essential and must go in the answer.
  2. Mark what those three essentials cover: P1 gives {0,1,8,9}, P3 gives {8,9,10,11}, and P4 gives {3,7,11,15}. Their union is {0,1,3,7,8,9,10,11,15}, which is every minterm of F.
  3. Because the essentials already cover everything, P2 = B'·D is never needed: each of its minterms (1,3,9,11) is already claimed by an essential. Drop it.
  4. Read the minimal sum of products off the chosen rows: F = B'·C' + A·B' + C·D. Three two-literal terms (six literals), down from nine four-literal minterms.
This run is exactly why the chart deserves to be a separate phase. P2 = B'·D is a perfectly valid prime implicant, a maximal group of 1s that cannot grow any larger, yet the final expression does not use it, because every 1 it would cover is already spoken for by an essential. Finding all the prime implicants is not the same as needing them all. The chart is what tells the two apart: lock in the essentials, then drop (or choose among) whatever is left over.
Try it
In a 4-variable function (ABCD), combine minterm 5 (0101) with minterm 7 (0111). What is the resulting implicant in dash notation, which variable dropped out, and what product term does it represent?

Frequently asked

What is the Quine-McCluskey method?

Quine-McCluskey is a tabular algorithm for minimizing a boolean function. It lists the minterms (and don't-cares) in binary, repeatedly combines terms that differ in exactly one bit to find all prime implicants, then uses a prime-implicant chart to choose a minimum-cost cover. Unlike a Karnaugh map it is exhaustive and works for any number of variables.

When should you use Quine-McCluskey instead of a Karnaugh map?

Use a Karnaugh map for up to about four variables, where its visual grouping is fast. Switch to Quine-McCluskey when a function has five or six or more variables: a K-map's adjacency becomes impossible to see, while Q-M's mechanical table stays correct and can be automated. Q-M is also the method behind logic-synthesis CAD tools.

What is a prime implicant?

A prime implicant is a product term (a group of 1s in the truth table) that cannot be made any larger by combining it with another term, that is, no further bit can be cancelled. In Quine-McCluskey, prime implicants are exactly the merged terms that never get checked off because nothing remains to combine them with.

What is an essential prime implicant?

An essential prime implicant is one that is the only prime implicant covering some minterm. Because that minterm has no other cover, the essential prime implicant must appear in the final expression. In the prime-implicant chart it shows up as a column with a single X; selecting all essentials first is the start of choosing a minimum cover.

What is Petrick's method?

Petrick's method finds the minimum cover when essential prime implicants alone do not cover every minterm. You write a product of sums stating that each still-uncovered minterm must be handled by one of the prime implicants that covers it, multiply it out into a sum of products, and pick the term with the fewest (or cheapest) implicants. It guarantees an exact minimum two-level solution.
Quine-McCluskey gives you the smallest two-level AND-OR circuit a function can have, the rigorous end of logic minimization. With the gate-level toolkit complete (design, simplify, and now provably minimize), the course turns those minimized gates toward real computation, starting with adding two bits in the half adder.

Every lesson here builds toward one thing: a working CPU, from the transistor up.

Open the free lab →
Found this useful? Share itShare on X