Quine–McCluskey

Digital Logic 101 · 14 min read

Why a tabular method

K-maps work brilliantly up to 4 variables and tolerably for 5. By 6 variables the planar adjacency picture breaks down and reading groups becomes guesswork. Quine–McCluskey (QM) is the textbook algorithm that does the same minimisation purely on tables, so it scales to any number of inputs and is straightforward to implement on a computer.

QM produces the same minimum SOP a perfect K-map reading would. What it loses in visual intuition it gains in mechanical certainty — every step is bookkeeping.

Three stages

Figure 1. QM pipeline: list minterms in binary, group by ones-count, combine adjacent groups (one-bit difference) into larger implicants with dashes, repeat until no more combinations. The unused rows from every column become prime implicants. Then a chart picks the smallest covering subset.

Stage 1 — iteration columns

Write each minterm as a binary string of length $n$ . Group them by the number of 1-bits (the ones-count). Two patterns can combine when they sit in adjacent groups and differ in exactly one bit. The combined pattern keeps every matched bit and writes a dash in the differing position.

Combine rule: two patterns that differ in exactly one bit collapse into one pattern with a dash at the differing position. A dash means “this variable is don’t-care for this implicant.”

For a concrete walk-through, take the 3-variable function $F(A,B,C) = \Sigma m(0, 1, 2, 5, 7)$ . Write each minterm in binary, count its 1-bits, and bucket them by ones-count:

Ones   Minterms
 0     m0 = 000
 1     m1 = 001
       m2 = 010
 2     m5 = 101
 3     m7 = 111

Four ones-count groups: {m0}, {m1, m2}, {m5}, {m7}. Combining can only happen across adjacent buckets, because two patterns whose ones-counts differ by 0 or ≥ 2 cannot differ by exactly one bit. The figure below shows one such combine step — the adjacent pair (m0, m1) differs only in bit C and collapses to 00– (the prime implicant A'B'):

Figure 2. One-bit difference combines: m0 (000) + m1 (001) → 00–, dropping the C variable. The new implicant covers both source minterms. In the full F(A,B,C) = Σm(0,1,2,5,7) example, three more pairs combine the same way (m0+m2, m1+m5, m5+m7), giving four prime implicants total — those become the rows of the chart in Stage 2.

Tick every row that found a partner; carry the unticked rows forward as prime implicants — they cannot grow any larger. Repeat with the new column. When a column produces no further combinations the procedure halts; every unticked row across all columns is a prime implicant.

Stage 2 — the PI chart

Build a table with prime implicants down the left and theoriginal minterms across the top (don’t-cares are not listed; they were only useful for growing groups). Mark an × wherever a PI covers a minterm.

Figure 3. F(A,B,C) = Σm(0,1,2,5,7). Column m2 has exactly one × (in A'C') and column m7 has exactly one × (in AC) — those two PIs are essential. After taking them, m1 is the only remaining minterm; either A'B' or B'C will cover it.

The Stage-2 procedure, step by step:

Scan every minterm column. If a column has exactly one ×, the PI in that row is essential. Add it to the cover.
Strike out every minterm column that essential covers — those minterms are now satisfied and play no further part. You can also cross out the chosen row.
Repeat step 1 on the reduced chart. New essentials may emerge once columns disappear (a column that previously had two ×s may drop to one).
When no more essentials exist but minterms remain, the chart is cyclic. Pick the smallest extra set of PIs that covers what’s left — by inspection for small charts, or by Petrick’s method below.

Applied to the chart above: m2 is covered only by A’C’ and m7 is covered only by AC, so both are essential. Take them and strike columns m0, m2, m5, m7 (everything they cover). Only m1 is left, covered by A’B’ or B’C — either choice gives a valid 3-PI minimum cover.

Petrick’s method (cyclic charts)

When the chart has no essentials, write a Boolean “cover constraint”: for each minterm column, an OR over the PIs that cover it. AND those clauses together, multiply out using Boolean idempotence ( $P_i \cdot P_i = P_i$ ) and absorption ( $P_i + P_i \cdot X = P_i$ ), then pick the smallest product term. That product names the PIs that form the minimum cover.

Worked example

Take the function $F(A,B,C) = \Sigma m(0,1,2,5,6,7)$ . Stage 1 produces six 2-cell prime implicants, none of which can grow further:

P1 = A'B' (00–)   covers m0, m1
P2 = A'C' (0–0)   covers m0, m2
P3 = B'C  (–01)   covers m1, m5
P4 = BC'  (–10)   covers m2, m6
P5 = AC   (1–1)   covers m5, m7
P6 = AB   (11–)   covers m6, m7

On the PI chart every column has exactly two ×s, so there are no essentials — a fully cyclic chart. Write the cover constraint (one OR per minterm):

P  =  (P1 + P2)    ← m0 covered by P1 or P2
   ·  (P1 + P3)    ← m1
   ·  (P2 + P4)    ← m2
   ·  (P3 + P5)    ← m5
   ·  (P4 + P6)    ← m6
   ·  (P5 + P6)    ← m7

Multiply pairs that share a variable:

(P1 + P2)(P1 + P3) = P1 + P2·P3      ← P1 absorbs P1·P2 and P1·P3
(P4 + P6)(P5 + P6) = P6 + P4·P5      ← same trick on P6

Continue expanding and applying absorption $(X + X \cdot Y = X)$ . After all the dust settles only two product terms of size 3 survive:

P  =  P1·P4·P5  +  P2·P3·P6  +  (longer 4-PI terms, all absorbed)

Each surviving term is a candidate minimum cover. Pick whichever you like — both have three PIs and six literals total:

Cover A:  P1·P4·P5  →  F = A'B' + BC' + AC
Cover B:  P2·P3·P6  →  F = A'C' + B'C + AB

Petrick = OR-AND-multiply-absorb. The smallest product term in the expanded sum-of-products of

P

names the PIs in the minimum cover. Multiple smallest terms means multiple equally-minimum SOPs.

Don’t-cares in QM

Don’t-care minterms join the input list during stage 1 — they help patterns combine into larger groups for free. They do not appear as columns in the PI chart, so the algorithm won’t spend a PI just to cover one. That asymmetry is what makes don’t-cares tighten the cover when they help and cost nothing when they don’t.

Practical limits

The number of prime implicants can grow exponentially in the worst case (Chandra–Markowsky). For everyday digital design the chart stays manageable through 7–8 variables, after which heuristic tools like ESPRESSO take over. The reducer in this topic caps at 6 variables for chart readability.