Quine-McCluskey Method | Digital Electronics

Motivation

Karnaugh maps are excellent for functions of up to about 5 variables. Beyond that, the map becomes unwieldy and visual grouping is error-prone. The Quine-McCluskey (Q-M) method is a systematic, tabular algorithm that finds the minimal SOP (or POS) expression for any Boolean function, regardless of the number of variables. It is the algorithm underlying most computer-based logic minimisation tools.

The Q-M method has two distinct phases:

Find all prime implicants using the Q-M implication table.
Find the minimum cover using the prime implicant chart.

Phase 1: The Implication Table (Finding Prime Implicants)

The process systematically combines minterms that differ in exactly one bit position, iteratively reducing the number of literals until no further combinations are possible.

Step 1: List Minterms in Binary, Grouped by Number of 1s

List all minterms (and don’t-cares, if any) by their binary representation. Group them according to the number of 1s in the binary representation. Arrange groups in ascending order of the count of 1s, with a blank line between groups.

Step 2: The Uniting Theorem

Compare every term in group $i$ with every term in group $i+1$ . If two terms differ in exactly one bit position, they can be combined: write the combined term in a new column, replacing the differing bit with a dash ( $-$ ). Mark (tick, ✓) the two original terms to indicate they are NOT prime implicants (since they were combined into a larger term).

Step 3: Repeat

Repeat Step 2 on the newly formed column. Terms in the new column can combine only if they have dashes in exactly the same positions AND differ in exactly one remaining bit position.

Step 4: Identify Prime Implicants

When no further combinations are possible, the unticked terms in all columns are the prime implicants.

Full Worked Example

Consider a 4-variable function with minterms: 4, 5, 6, 8, 9, 10, 13. Don’t-cares: 0, 7, 15.

Step 1: Binary Representation, Grouped by Number of 1s

Minterm	Binary ( $a\,b\,c\,d$ )	Group (# of 1s)
0	0 0 0 0	0

4	0 1 0 0	1
8	1 0 0 0	1

5	0 1 0 1	2
6	0 1 1 0	2
9	1 0 0 1	2
10	1 0 1 0	2

7	0 1 1 1	3
13	1 1 0 1	3

15	1 1 1 1	4

Step 2: First Pass of Comparison (Column 1 → Column 2)

Compare group 0 with group 1:

0000 vs 0100: differ in bit $b$ (position 2). Combined: 0 - 0 0. Tick both originals.
0000 vs 1000: differ in bit $a$ (position 1). Combined: - 0 0 0. Tick both originals.

Compare group 1 with group 2:

0100 vs 0101: differ in $d$ . Combined: 0 1 0 -. Tick both.
0100 vs 0110: differ in $c$ . Combined: 0 1 - 0. Tick both.
1000 vs 1001: differ in $d$ . Combined: 1 0 0 -. Tick both.
1000 vs 1010: differ in $c$ . Combined: 1 0 - 0. Tick both.

Compare group 2 with group 3:

0101 vs 0111: differ in $c$ . Combined: 0 1 - 1. Tick both.
0110 vs 0111: differ in $d$ . Combined: 0 1 1 -. Tick both.
1001 vs 1101: differ in $b$ . Combined: 1 - 0 1. Tick both.
0110 vs… nothing else in group 3. 1010 vs 1101? Differ in 2 positions ( $a$ and $c$ ), not combinable.

Compare group 3 with group 4:

0111 vs 1111: differ in $a$ . Combined: - 1 1 1. Tick both.
1101 vs 1111: differ in $c$ . Combined: 1 1 - 1. Tick both.

After first pass, Column 1 status:

Minterm	Binary	Status
0	0 0 0 0	✓
4	0 1 0 0	✓
8	1 0 0 0	✓
5	0 1 0 1	✓
6	0 1 1 0	✓
9	1 0 0 1	✓
10	1 0 1 0	✓
7	0 1 1 1	✓
13	1 1 0 1	✓
15	1 1 1 1	✓

All original minterms are ticked (none are prime implicants yet).

Column 2 (all combinations from pass 1):

Group by number of 1s in the non-dash bits:

Combined Term	# of 1s (non-dash)	Source Minterms
0 - 0 0	0	0, 4
- 0 0 0	0	0, 8

0 1 0 -	1	4, 5
0 1 - 0	1	4, 6
1 0 0 -	1	8, 9
1 0 - 0	1	8, 10

0 1 - 1	2	5, 7
0 1 1 -	2	6, 7
1 - 0 1	2	9, 13

- 1 1 1	3	7, 15
1 1 - 1	3	13, 15

Step 3: Second Pass (Column 2 → Column 3)

Compare adjacent groups in Column 2. Two terms can combine only if they have dashes in exactly the same positions AND differ in exactly one remaining bit.

Compare Group 1 with Group 2:

0 1 0 - (dash at pos 4) and 0 1 1 - (dash at pos 4): same dash position. Remaining bits differ only in bit 3. ✓ COMBINE → 0 1 - -. Tick both.
0 1 - 0 (dash at pos 3) and 0 1 - 1 (dash at pos 3): same dash position. Remaining bits differ only in bit 4. ✓ COMBINE → 0 1 - -. Tick both.
All other Group 1–Group 2 pairs have dashes at different positions or differ in more than one remaining bit.

Compare Group 2 with Group 3:

0 1 - 1 (dash at pos 3) and 1 1 - 1 (dash at pos 3): same dash position. Remaining bits differ only in bit 1. ✓ COMBINE → - 1 - 1. Tick both.
All other Group 2–Group 3 pairs have dashes at different positions.

Column 2 status after second pass:

Group 0 (unticked — prime implicants): 0 - 0 0, - 0 0 0. Group 1: 0 1 0 - ✓, 0 1 - 0 ✓, 1 0 0 - (unticked), 1 0 - 0 (unticked). Group 2: 0 1 - 1 ✓, 0 1 1 - ✓, 1 - 0 1 (unticked). Group 3: - 1 1 1 ✓, 1 1 - 1 ✓.

The final prime implicants (unticked terms across all columns):

Prime implicants from Column 2: 0 - 0 0 (covers $m_0, m_4$ ), - 0 0 0 (covers $m_0, m_8$ ), 1 0 0 - (covers $m_8, m_9$ ), 1 0 - 0 (covers $m_8, m_{10}$ ), 1 - 0 1 (covers $m_9, m_{13}$ ).

Prime implicants from Column 3: 0 1 - - (covers $m_4, m_5, m_6, m_7$ ), - 1 - 1 (covers $m_5, m_7, m_{13}, m_{15}$ ).

K-Map Verification

To visualise these prime implicants on a 4-variable K-map:

\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & X & & & \\ 01 & 1 & 1 & X & 1 \\ 11 & & 1 & X & \\ 10 & 1 & 1 & & 1 \end{array}

The prime implicants map as:

0 - 0 0: row $a=0$ , column $c=0,d=0$ → $m_0$ (X) and $m_4$ (1). Two cells.
- 0 0 0: column $b=0,c=0,d=0$ → $m_0$ (X) and $m_8$ (1). Two cells.
1 0 0 -: row $a=1, b=0$ , columns $c=0$ → $m_8$ (1) and $m_9$ (1). Two cells.
1 0 - 0: $a=1, b=0, d=0$ , columns 00 and 10 → $m_8$ (1) and $m_{10}$ (1). Two cells.
1 - 0 1: $a=1, c=0, d=1$ , both $b=0$ and $b=1$ → $m_9$ (1) and $m_{13}$ (1). Two cells.
0 1 - -: row 01 ( $a=0, b=1$ ) → $m_4, m_5, m_6, m_7$ . Four cells.
- 1 - 1: $b=1, d=1$ , all $a$ and $c$ → $m_5, m_7, m_{13}, m_{15}$ . Four cells.

All prime implicants shown. The K-map confirms the Q-M result.

Phase 2: The Prime Implicant Chart (Finding Minimum Cover)

Now we need to select the minimum set of prime implicants that covers all the required minterms (the 1s, not the don’t-cares).

Step 1: Construct the Chart

Columns: each required minterm (4, 5, 6, 8, 9, 10, 13). Do NOT include don’t-cares (0, 7, 15) as columns.

Rows: each prime implicant. Place an X where the prime implicant covers the minterm.

Prime implicants expressed by their covered minterms (required ones only):

Prime Implicant	Binary	Covers (req. minterms)	4	5	6	8	9	10	13
PI1: 0,4	0 - 0 0	4	X
PI2: 0,8	- 0 0 0	8				X
PI3: 8,9	1 0 0 -	8, 9				X	X
PI4: 8,10	1 0 - 0	8, 10				X		X
PI5: 9,13	1 - 0 1	9, 13					X		X
PI6: 4,5,6,7	0 1 - -	4, 5, 6	X	X	X
PI7: 5,7,13,15	- 1 - 1	5, 13		X					X

Step 2: Find Essential Prime Implicants

Look at each column. If a column has exactly one X, the corresponding row is an essential prime implicant.

Column 4: Xs in PI1 and PI6 → not essential (yet).
Column 5: Xs in PI6 and PI7 → not essential.
Column 6: X only in PI6 → PI6 is essential!
Column 8: Xs in PI2, PI3, PI4 → not essential.
Column 9: Xs in PI3 and PI5 → not essential.
Column 10: X only in PI4 → PI4 is essential!
Column 13: Xs in PI5 and PI7 → not essential.

Essential prime implicants: PI6 and PI4.

Step 3: Cross Out Covered Minterms

PI6 covers minterms 4, 5, 6. Cross out columns 4, 5, 6. PI4 covers minterms 8, 10. Cross out columns 8, 10.

Remaining uncovered minterms: 9, 13.

Step 4: Cover Remaining Minterms

Looking at columns 9 and 13:

Column 9: Xs in PI3 and PI5.
Column 13: Xs in PI5 and PI7.

PI5 covers BOTH 9 and 13. So we select PI5. This completes the cover.

Final Covering Set

Selected prime implicants: PI4 (8,10), PI5 (9,13), PI6 (4,5,6).

Converting to Boolean expressions:

PI4: 1 0 - 0 → $a \cdot \bar{b} \cdot \bar{d}$
PI5: 1 - 0 1 → $a \cdot \bar{c} \cdot d$
PI6: 0 1 - - → $\bar{a} \cdot b$

$f = \bar{a} \cdot b + a \cdot \bar{b} \cdot \bar{d} + a \cdot \bar{c} \cdot d$

This is the minimal SOP expression.

Summary of the Q-M Method

List all minterms and don’t-cares in binary, grouped by number of 1s.
Iteratively combine adjacent groups: terms that differ in exactly one bit are merged (bit replaced by dash), originals ticked. Repeat on successive columns until no more combinations.
Unticked terms across all columns are the prime implicants.
Build the prime implicant chart: columns = required minterms (no don’t-cares), rows = prime implicants, X = coverage.
Identify essential prime implicants: columns with a single X.
Select additional prime implicants as needed to cover remaining minterms (using row/column dominance or Petrick’s method for complex cases).

The Q-M method is guaranteed to find the true minimal expression (unlike K-maps, which rely on visual inspection and can miss optimal groupings in complex cases). For functions with more than about 10 variables, even Q-M becomes computationally expensive, and heuristic minimisers (e.g., Espresso) are used in practice.