Tabular (Quine-McCluskey) Method: short notes (Digital Logic)

Introduction

The Quine-McCluskey (QM) method finds all prime implicants of a Boolean function by systematically combining minterms, then selects a minimum cover with a prime-implicant chart. It is the syllabus's tabular minimization technique: the same mathematics as K-maps, but mechanical, so it works for more variables and can be programmed.

The method has two stages. Stage A builds every prime implicant by repeated merging of bit strings. Stage B chooses a cheapest set of primes that covers every 1 of the function. The method yields the number of prime implicants, the number of essential ones, the entries of a combination table, and the final minimal SOP.

Prerequisites

Karnaugh Maps: prime implicants, essential primes, don't-cares, covering.

Core concepts

Cubes as strings

A product term over $n$ ordered variables is written as an $n$ -character string over $\{0, 1, -\}$ : 1 for an uncomplemented literal, 0 for a complemented literal and $-$ for an absent variable. With variables $abcd$ , the string $0{-}11$ is $a'cd$ and covers minterms 3 and 7. A string with $k$ dashes covers $2^k$ minterms.

Stage A: find prime implicants

List all minterms and don't-cares as $n$ -bit strings, grouped by the number of 1 bits (the index).
Compare every string with every string in the next group only. Two strings combine when they have dashes in the same positions and differ in exactly one of the other positions. Write the merged string with a new dash there and check off both parents.
Repeat step 2 on the list of merged strings, column by column, until no merge is possible. Record each merged string once, even if several pairs produce it.
Strings never checked off are the prime implicants.

Why only adjacent groups. Two strings that differ in exactly one fixed bit have indices that differ by exactly 1, so comparing a group only with the next group finds every merge.

Stage B: prime-implicant chart

Rows: prime implicants. Columns: onset minterms only (don't-cares need not be covered).
Star a cell when the prime covers that minterm.
A column with a single star marks an essential prime; select it, delete its row and all columns it covers.
Row dominance. If row $P$ covers every remaining column of row $Q$ and costs no more, delete $Q$ .
Column dominance. If every row that covers column $u$ also covers column $v$ , delete $v$ (covering $u$ will cover $v$ automatically).
Repeat until every column is covered or the chart is cyclic (no essential row, no dominance left); then use Petrick's method or branching.

Petrick's method

Name the remaining primes $P_1, P_2, \ldots$ . For each uncovered column write the OR of the names of the rows that cover it, and AND these clauses together. Multiply out into a sum of products (using $X + XY = X$ to drop supersets). Each product is an irredundant cover; choose one with the fewest primes, then the fewest literals.

Quine-McCluskey grouping table and prime-implicant chart — Figure 1. Top: combination table for $f=\sum m(0,1,2,5,6,7)$ showing checked-off minterms and primes. Bottom: prime-implicant chart with no essential prime and one minimum cover marked.

How it works

Don't-cares in QM

Include don't-care minterms in Stage A so they can enlarge implicants. Omit their columns in Stage B so they are not required in the cover. A prime that covers only don't-cares (and no onset minterm) can be discarded at once.

Completeness

Stage A enumerates every prime implicant of the onset plus don't-care set: every implicant is a cube, every cube of size $2^k$ arises by merging two cubes of size $2^{k-1}$ , and only cubes contained in no larger implicant survive unchecked. Stage B then solves the covering problem exactly when Petrick's method is used.

Algorithms and pseudocode

Pseudocode uses strings over $\{0, 1, -\}$ and <- for assignment.

Text

QM-PRIMES(onset, dontcares, n)
1  current <- onset union dontcares, as n-bit strings
2  primes <- empty set
3  while current is not empty
4      next <- empty set; used <- empty set
5      for each pair (a, b) in current with equal dash positions
6          if a and b differ in exactly one non-dash position i then
7              add (a with position i replaced by '-') to next
8              add a and b to used
9      primes <- primes union (current minus used)
10     current <- next
11 return primes minus {p : p covers no onset minterm}

QM-COVER(primes, onset)               // return one minimum cover
1  rows <- primes; remaining <- onset; chosen <- empty set
2  repeat
3      select an essential row p, if one exists, in chart (rows, remaining)
4      if p exists then
5          chosen <- chosen union {p}
6          remaining <- remaining minus columns covered by p; rows <- rows minus {p}
7      apply cost-respecting row and column dominance to (rows, remaining)
8  until no change
9  if remaining is not empty then
10     minimumSets <- PETRICK(rows, remaining)
11     choose one set S from minimumSets
12     chosen <- chosen union S
13 return chosen

PETRICK(rows, columns)
1  S <- { empty set }                     // partial covers
2  for each column u in columns
3      C <- rows that cover u
4      S <- { s union {p} : s in S, p in C }
5      delete from S every set that strictly contains another set in S
6  return the sets in S with fewest rows, ties broken by fewest literals

Cost. Stage A on $m$ strings in a column compares at most $\binom{m}{2}$ pairs, each in $O(n)$ time; there are at most $n + 1$ columns. QM is exact; it is not fast.

Procedure	Best case	Worst case
QM-PRIMES	No two minterms are adjacent, for example odd parity: one column, at most $\binom{m}{2}$ comparisons, and every minterm is its own prime (8 primes for $n = 4$ )	$f = 1$ : column $k$ holds all $\binom{n}{k}2^{n-k}$ cubes with $k$ dashes, so all $3^n$ cubes are built (81 for $n = 4$ ) in $n + 1$ columns, and comparing pairs within columns costs $O(9^n n)$
QM-COVER	The essential primes cover every column, as in the Karnaugh Maps note's Figure 1 function: one pass, $O(\text{rows} \times \text{columns})$ , and PETRICK never runs	A cyclic chart: no essentials, no dominance, everything goes to PETRICK
PETRICK	One column left: one set per covering row	$c$ columns with $k$ stars each give up to $k^c$ selections before absorption, exponential in $c$

For Example 1 below, PETRICK sees $c = 6$ columns with $k = 2$ stars each: $2^6 = 64$ selections, 18 distinct sets, and 5 sets after absorption (the two 3-prime covers and three 4-prime covers). Minimum cover is set cover, which is NP-hard, so no known exact method is polynomial in the worst case. There is no useful average case: the cost depends on how many implicants the onset has, anywhere from $m$ to $3^n$ .

Mathematical explanation

Merging two cubes that differ in one fixed position is the combining rule $Px + Px' = P$ , so every merged string is an implicant. A string is left unchecked exactly when no implicant one dimension larger contains it, which is the definition of prime. Every minimal SOP is a sum of primes (removing a literal from a non-prime term would lower the cost), so searching among primes loses nothing. The chart step is minimum set cover over the onset columns, with each row weighted by its literal count.

Worked examples

Example 1: $f=\sum m(0,1,2,5,6,7)$ with $n=3$ (variables $xyz$ )

Stage A, column 1 (minterms by index):

Index	Minterms
0	000 (0)
1	001 (1), 010 (2)
2	101 (5), 110 (6)
3	111 (7)

Column 2 (merges of adjacent groups): $0,1 \to 00{-}$ ; $0,2 \to 0{-}0$ ; $1,5 \to {-}01$ ; $2,6 \to {-}10$ ; $5,7 \to 1{-}1$ ; $6,7 \to 11{-}$ . Every minterm is checked off. Pairs such as 1 and 2 are in the same group and never combine; 2 and 5 are in adjacent groups but differ in three bits.

Column 3. No two column-2 strings have the same dash position and differ in one bit: $00{-}$ and $11{-}$ differ in two bits, $0{-}0$ and $1{-}1$ in two, ${-}01$ and ${-}10$ in two. So the six pairs are the prime implicants: $x'y'$ , $x'z'$ , $y'z$ , $yz'$ , $xz$ , $xy$ .

Stage B.

PI	0	1	2	5	6	7
$P_1 = x'y'$	*	*
$P_2 = x'z'$	*		*
$P_3 = y'z$		*		*
$P_4 = yz'$			*		*
$P_5 = xz$				*		*
$P_6 = xy$					*	*

Every column has exactly two stars, so no prime is essential and no row or column dominates another: the chart is cyclic. Petrick's method gives

(P_1 + P_2)(P_1 + P_3)(P_2 + P_4)(P_3 + P_5)(P_4 + P_6)(P_5 + P_6),

whose smallest products are $P_1P_4P_5$ and $P_2P_3P_6$ . So the two minimal SOPs are

f = x'y' + yz' + xz \qquad\text{and}\qquad f = x'z' + y'z + xy,

each with 3 terms and 6 literals. Figure 1 shows the chart: no row is marked essential, and the ticked rows $P_1, P_4, P_5$ are one of the two minimum covers.

Example 2: the same function with a don't-care

Add $d(4)$ . Now Stage A also merges 4 ( $100$ ) with 0, 5 and 6, and the column-3 merges $0,1,4,5 \to {-}0{-}$ , $0,2,4,6 \to {-}{-}0$ and $4,5,6,7 \to 1{-}{-}$ appear. The primes are $y'$ , $z'$ and $x$ . Each is essential ( $y'$ alone covers 1, $z'$ alone covers 2, $x$ alone covers 7), and

f = x + y' + z' \quad (3 \text{ literals, against } 6 \text{ without the don't-care}).

Example 3: four variables, $f(a,b,c,d) = \sum m(1, 3, 7, 11, 15) + d(0, 2, 5)$

Column 1. Index 0: 0000 (0). Index 1: 0001 (1), 0010 (2). Index 2: 0011 (3), 0101 (5). Index 3: 0111 (7), 1011 (11). Index 4: 1111 (15).

Column 2 (ten merges, every minterm checked): $0,1 \to 000{-}$ ; $0,2 \to 00{-}0$ ; $1,3 \to 00{-}1$ ; $1,5 \to 0{-}01$ ; $2,3 \to 001{-}$ ; $3,7 \to 0{-}11$ ; $3,11 \to {-}011$ ; $5,7 \to 01{-}1$ ; $7,15 \to {-}111$ ; $11,15 \to 1{-}11$ .

Column 3 (every column-2 string checked):

Quad	Formed by	Term
$0,1,2,3 \to 00{-}{-}$	$000{-}$ with $001{-}$ , and $00{-}0$ with $00{-}1$	$a'b'$
$1,3,5,7 \to 0{-}{-}1$	$00{-}1$ with $01{-}1$ , and $0{-}01$ with $0{-}11$	$a'd$
$3,7,11,15 \to {-}{-}11$	${-}011$ with ${-}111$ , and $0{-}11$ with $1{-}11$	$cd$

Each quad is produced twice; it is recorded once. No two quads merge, so there are three prime implicants.

Stage B (columns 1, 3, 7, 11, 15 only):

PI	1	3	7	11	15
$cd$		*	*	*	*
$a'd$	*	*	*
$a'b'$	*	*

Columns 11 and 15 have a single star: $cd$ is the only essential prime. It leaves column 1, covered by $a'd$ or $a'b'$ at equal cost. So there are two minimal SOPs, $f = cd + a'd$ and $f = cd + a'b'$ , each with 4 literals. They differ only on don't-care inputs: $a'd$ makes $m_5$ a 1, $a'b'$ makes $m_0$ and $m_2$ 1s.

Important properties and observations

Combine only equal dash patterns; mismatched dashes mean different subcube orientations.
A cube of $2^k$ minterms is generated by $k$ different merges in the last column; record it once.
Essential primes are exactly those with a private onset column.
Multiple minimum covers may exist; any minimum literal SOP is a correct answer.
Two minimal SOPs that use don't-cares differently are different functions on the don't-care rows, and both are correct.

Common misconceptions.

"Don't-care columns appear in the chart." They must not.
"All primes are needed." Only a cover; extras inflate the expression.
"QM and K-map can disagree on the minimum." They minimize the same cost; their lists of primes are identical.
"Strings in the same index group can combine." They have the same number of 1s, so they differ in at least two positions.
"No essential prime means no minimum exists." A cyclic chart still has minimum covers; Petrick's method finds them.

GATE examination perspective

COMBINATION TABLE. Show check marks and dashes carefully; questions ask how many entries a column has or which strings stay unchecked.
PRIME AND ESSENTIAL COUNTS. Count primes after Stage A including those formed with don't-cares; count essentials from onset columns only.
CHART. Strike essentials first, then apply dominance; read what remains as a small covering problem.
DON'T-CARES. In Stage A only.
CYCLIC CHARTS. A chart with two stars in every column has no essential prime. Apply dominance and solve the residual covering problem; column star counts alone establish neither cyclicity nor the number of optimum covers. For example, rows A={1,2}, B={1}, C={2} give two stars per column but a unique minimum-row cover {A}.
COMPARE OPTIONS. Evaluate each option's onset against the specified minterms, ignoring don't-care rows.

Summary

Karnaugh Maps: prerequisite. Same covering ideas visually.
Algebraic Minimization: related. Local rewrites without enumeration.
Combinational Circuit Design: related. Implement the cover as gates.

Tabular (Quine-McCluskey) Method

Introduction

Prerequisites

Core concepts

Cubes as strings

Stage A: find prime implicants

Stage B: prime-implicant chart

Petrick's method

How it works

Don't-cares in QM

Completeness

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: $f=\sum m(0,1,2,5,6,7)$ with $n=3$ (variables $xyz$ )

Example 2: the same function with a don't-care

Example 3: four variables, $f(a,b,c,d) = \sum m(1, 3, 7, 11, 15) + d(0, 2, 5)$

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Cubes as strings

Stage A: find prime implicants

Stage B: prime-implicant chart

Petrick's method

How it works

Don't-cares in QM

Completeness

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: f=∑m(0,1,2,5,6,7)f=\sum m(0,1,2,5,6,7)f=∑m(0,1,2,5,6,7) with n=3n=3n=3 (variables xyzxyzxyz)

Example 2: the same function with a don't-care

Example 3: four variables, f(a,b,c,d)=∑m(1,3,7,11,15)+d(0,2,5)f(a,b,c,d) = \sum m(1, 3, 7, 11, 15) + d(0, 2, 5)f(a,b,c,d)=∑m(1,3,7,11,15)+d(0,2,5)

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

Example 1: $f=\sum m(0,1,2,5,6,7)$ with $n=3$ (variables $xyz$ )

Example 3: four variables, $f(a,b,c,d) = \sum m(1, 3, 7, 11, 15) + d(0, 2, 5)$