# Quine-McCluskey minimization

*The algorithm that minimizes when a K-map cannot*

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.

Group: Gates
URL: https://digiwleea.wleeaf.dev/learn/quine-mccluskey/

A [Karnaugh map](https://digiwleea.wleeaf.dev/learn/karnaugh/) minimizes logic by letting you *see* which [minterms](https://digiwleea.wleeaf.dev/learn/canonical-forms/) 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 `1`s.

> **TIP:** 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 `1`s**. 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 `1`s 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 `1`s gives five starting groups (`0` ones, `1` one, `2` ones, `3` ones, `4` ones):

| 1s | Minterm | A | B | C | D |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 2 | 0 | 0 | 1 | 0 |
| 1 | 8 | 1 | 0 | 0 | 0 |
| 2 | 10 | 1 | 0 | 1 | 0 |
| 3 | 11 | 1 | 0 | 1 | 1 |
| 3 | 14 | 1 | 1 | 1 | 0 |
| 4 | 15 | 1 | 1 | 1 | 1 |

_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 implicant | m0 | m1 | m2 | m8 | m10 | m11 | m14 | m15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| P1 = B'D' | X |  | X | X | X |  |  |  |
| P2 = A·C |  |  |  |  | X | X | X | X |
| P3 = A'B'C' | X | X |  |  |  |  |  |  |

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

> **KEY:** 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.

> **WARN:** **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 `1`s:

| 1s | Minterm | A | B | C | D |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 8 | 1 | 0 | 0 | 0 |
| 2 | 3 | 0 | 0 | 1 | 1 |
| 2 | 9 | 1 | 0 | 0 | 1 |
| 2 | 10 | 1 | 0 | 1 | 0 |
| 3 | 7 | 0 | 1 | 1 | 1 |
| 3 | 11 | 1 | 0 | 1 | 1 |
| 4 | 15 | 1 | 1 | 1 | 1 |

_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 implicant | Covers | A | B | C | D |
| --- | --- | --- | --- | --- | --- |
| P1 = B'·C' | 0,1,8,9 | - | 0 | 0 | - |
| P2 = B'·D | 1,3,9,11 | - | 0 | - | 1 |
| P3 = A·B' | 8,9,10,11 | 1 | 0 | - | - |
| P4 = C·D | 3,7,11,15 | - | - | 1 | 1 |

_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 implicant | m0 | m1 | m3 | m7 | m8 | m9 | m10 | m11 | m15 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| P1 = B'C' | X | X |  |  | X | X |  |  |  |
| P2 = B'D |  | X | X |  |  | X |  | X |  |
| P3 = A·B' |  |  |  |  | X | X | X | X |  |
| P4 = C·D |  |  | X | X |  |  |  | X | X |

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

> **KEY:** 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 `1`s 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.

**Q (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?

**A:** `0101` and `0111` differ only in the `C` bit (`0` versus `1`), so they merge to `01-1`. The dash sits in the `C` position, meaning `C` dropped out (it was the variable that cancelled). The surviving fixed bits are `A=0, B=1, D=1`, so the implicant is the product term `A'·B·D`. That is one size-2 implicant; whether it is *prime* depends on whether it can merge again with another `01-1`-compatible term.

### FAQ

**Q:** What is the Quine-McCluskey method?

**A:** 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.

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

**A:** 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.

**Q:** What is a prime implicant?

**A:** A prime implicant is a product term (a group of `1`s 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.

**Q:** What is an essential prime implicant?

**A:** 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.

**Q:** What is Petrick's method?

**A:** 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](https://digiwleea.wleeaf.dev/learn/halfadder/).