10.1 Why K-maps run out of steam
A 3- or 4-variable K-map is easy to draw and minimise by inspection. But once you have 5 or more variables, the K-map either becomes 3-D (5 variables) or several stacked maps (6+ variables), and visual grouping becomes error-prone. The Quine–McCluskey method gives a purely tabular procedure that handles any number of variables and is straightforward to mechanise (or program).
10.2 Q-M algorithm at a glance
10.3 Phase 1 — generating prime implicants
Step 1: List minterms
Write each minterm of the function (and the don't-cares) in binary, with one row per minterm. Group them by the number of 1s they contain — Group 0 has zero 1s, Group 1 has one 1, etc.
Step 2: Combine adjacent groups
Two minterms can be combined when they differ in exactly one bit. Replace that bit with a dash ("−"). The dash is permanent — it tells you that variable is not needed.
Step 3: Keep combining until no new combinations are possible
A term in the new column can combine with another term in the same column only if they have a dash in the same position and differ in exactly one of the remaining bits.
Step 4: Prime implicants
Any term that is never combined further is a prime implicant. Mark every such "untouched" entry with ✱.
10.4 Worked example — F(A,B,C,D) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14)
Initial table, grouped by 1-count
| Group | Minterm | Binary |
|---|---|---|
| 0 | 0 | 0000 |
| 1 | 1 | 0001 |
| 1 | 2 | 0010 |
| 1 | 8 | 1000 |
| 2 | 5 | 0101 |
| 2 | 6 | 0110 |
| 2 | 9 | 1001 |
| 2 | 10 | 1010 |
| 3 | 7 | 0111 |
| 3 | 14 | 1110 |
First combination
| Combined pair | Result | From |
|---|---|---|
| 0–1 | 000− | 0,1 |
| 0–2 | 00−0 | 0,2 |
| 0–8 | −000 | 0,8 |
| 1–5 | 0−01 | 1,5 |
| 1–9 | −001 | 1,9 |
| 2–6 | 0−10 | 2,6 |
| 2–10 | −010 | 2,10 |
| 8–9 | 100− | 8,9 |
| 8–10 | 10−0 | 8,10 |
| 5–7 | 01−1 | 5,7 |
| 6–7 | 011− | 6,7 |
| 6–14 | −110 | 6,14 |
| 10–14 | 1−10 | 10,14 |
Second combination
| Combined pair | Result | From |
|---|---|---|
| (0,2) – (8,10) | −0−0 | 0,2,8,10 |
| (2,6) – (10,14) | −−10 | 2,6,10,14 |
No further combinations are possible. The prime implicants are:
- ✱
000−(covers 0,1) - ✱
0−01(covers 1,5) - ✱
−001(covers 1,9) - ✱
100−(covers 8,9) - ✱
01−1(covers 5,7) - ✱
011−(covers 6,7) - ✱
−0−0(covers 0,2,8,10) - ✱
−−10(covers 2,6,10,14)
10.5 Phase 2 — the prime implicant chart
Lay out a table with minterms on top and prime implicants down the side. Tick each cell where the PI covers that minterm.
| PI | 0 | 1 | 2 | 5 | 6 | 7 | 8 | 9 | 10 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|
| 000− | × | × | ||||||||
| 0−01 | × | × | ||||||||
| −001 | × | × | ||||||||
| 100− | × | × | ||||||||
| 01−1 | × | × | ||||||||
| 011− | × | × | ||||||||
| −0−0 | × | × | × | × | ||||||
| −−10 | × | × | × | × |
Essential prime implicants
A column with exactly one tick means only one PI covers that minterm, so it must be in the final solution.
- Minterm 14 → only
−−10→ essential. - With
−−10chosen, minterm 6 is covered. - Remaining columns: scan again, pick PIs that cover the rest with fewest gates.
10.6 Final minimised expression
For this example, one optimal cover is:
F = (−0−0) + (−−10) + (000−) + (01−1) + (−001)
= B'D' + CD' + A'B'C' + A'BD + B'C'D(There can be several equally optimal covers — Q-M finds one of them.)
10.7 Strengths and limits
| Q-M | K-map | |
|---|---|---|
| Number of variables | Any | ≤ 5 in practice |
| Mechanisable | Yes — easy to program | No |
| Speed for large N | Slow (NP-hard in worst case) | Impossible |
| Always finds minimum cover? | Yes | Only if you spot the right groupings |
Q-M is the theoretical minimum-cost algorithm. For real circuits with 20+ variables, CAD tools use heuristic minimisers like Espresso, which trade exactness for speed but still build on the same generate-and-cover idea.