Tabular method (Quine-McCluskey)

Why it exists

A Karnaugh map is a picture: a person looks for the largest groups of ones. It is quick for three or four variables, awkward for five, and unusable beyond. The tabular method (Quine-McCluskey) finds the same groups by pure bookkeeping on binary numbers, so it works for any number of variables and is the form in which a program does two-level minimisation. The official syllabus names it next to the Karnaugh map, and the exam asks for its by-products: how many prime implicants, which are essential, which minterms combine in the first round.

Prerequisites

You need minterms, the sum of products form and the idea of an implicant from Boolean functions and their forms, and the groups, prime implicants and essential prime implicants of the Karnaugh map.

Precise definitions

Cube. A product term written as a string over 0, 1 and -, one position per variable (leftmost = most significant variable). 1 means the variable appears uncomplemented, 0 complemented, - absent. For $A, B, C, D$: 10-0 is $AB'D'$. A cube with $k$ dashes covers $2^k$ minterms.

Implicant. A cube all of whose minterms are in the ON-set or are don't cares. Prime implicant. An implicant that is not contained in a larger implicant (removing any literal would make it cover an OFF minterm). Essential prime implicant. A prime implicant that is the only one covering some ON minterm; it is in every cover.

Group. The number of ones in a cube. Adjacent cubes differ in exactly one position, and in that position neither has a dash; the dashes of the two cubes must be in the same places. Their combination has a dash in the differing position.

Cost of a cover. The number of product terms first, then the number of literals. A minimum cover is a cover of the ON-set by prime implicants of least cost.

The procedure.

1. List the minterms and the don't cares in binary and sort them by group.
2. Round 1: compare every cube of group $g$ with every cube of group $g+1$. For each adjacent pair write the combined cube (once) in the next table and tick both cubes. Round 2, 3, ... repeat with the combined cubes, until a round produces nothing.
3. Every cube that was never ticked is a prime implicant (in whichever round it stands).
4. Build the prime implicant chart: rows are the prime implicants, columns the ON-set minterms only.
5. Choose the essential prime implicants (a column with one X), delete the columns they cover. Delete dominated rows and columns. Repeat.
6. If columns are left and several choices remain, use Petrick's method: for every column write the sum of the rows that cover it, multiply the sums out with $X + XY = X$ and $XX = X$, and take the cheapest product.

How it works

Step 1 and 2: the combining rounds

The function is $F(A,B,C,D) = \sum m(0,1,2,5,6,7,8,9,10,14)$. The first ten rows are the minterms by group. Look at 0000 in group 0: it differs in exactly one bit from 0001, 0010 and 1000, so it produces 000-, 00-0 and -000 and is ticked. Round 2 combines the cubes of size 2: only cubes with the dash in the same place can merge, -000 with -001 gives -00-. The same cube can arise from two different pairs (-0-0 comes from -000 with -010 and from 00-0 with 10-0); it is written once. Round 2 produces three cubes of size 4, and round 3 finds no neighbours among them, so the process stops. The cubes without a tick are the prime implicants: $A'C'D$ (0-01), $A'BD$ (01-1), $A'BC$ (011-), $B'D'$ (-0-0), $B'C'$ (-00-), $CD'$ (--10).

Step 3 and 4: the chart

Each row marks the minterms the prime implicant covers. A column with a single X names an essential prime implicant: $m_9$ is covered only by $B'C'$, $m_{14}$ only by $CD'$. Columns are only the ON-set: a don't care is allowed to be covered but never has to be.

Step 5: essential primes and dominance

$B'C'$ and $CD'$ are chosen, which removes $m_0, m_1, m_8, m_9$ and $m_2, m_6, m_{10}, m_{14}$. Left are $m_5$ and $m_7$. Row $A'C'D$ covers only $m_5$, row $A'BD$ covers both, at the same literal cost, so $A'C'D$ is dominated and deleted. Now $m_5$ has a single X: $A'BD$ is chosen, and the chart is empty. The answer is $F = CD' + B'C' + A'BD$ (3 terms, 7 literals). The prime implicant $B'D'$ is never needed: all its minterms are covered by the others. A prime implicant can be essential, optional or useless.

Row dominance: row $a$ dominates row $b$ if $a$ covers every remaining column that $b$ covers, and costs no more. Delete $b$. Column dominance: column $x$ is dominated by column $y$ if every row that covers $y$ also covers $x$. Delete $x$ (covering $y$ covers $x$ for free).

When no prime implicant is essential

$F(A,B,C) = \sum m(0,1,2,5,6,7)$ has six prime implicants and every column has two X's. Nothing is essential, nothing dominates anything. Guessing a row does work (and many students do it), but nothing in the chart says which choices are cheapest, so we need a method that looks at all of them.

Petrick's method

For each column write "one of the rows covering it must be chosen": $(P_3 + P_4)$ for $m_0$, $(P_1 + P_4)$ for $m_1$, and so on. A cover is a choice that satisfies all the factors, which is the product of the sums. Multiply them out step by step; after each multiplication delete every product that contains another product ($X + XY = X$), because it is a more expensive cover of the same thing. What is left are the irredundant covers. The cheapest are $P_1 P_3 P_6$ and $P_2 P_4 P_5$: $B'C + A'C' + AB$ and $BC' + A'B' + AC$, both 3 terms and 6 literals. The minimum cover is not unique; both are correct answers, and the exam may offer both among the options.

Don't cares

Don't cares take part in the combining step (they let the cubes grow, so the terms get shorter) but they have no column in the chart (nobody has to cover them). Throwing them away gives a more expensive answer (more literals); making them columns is also wrong (a cover would have to cover things it need not). The second row is the method.

Product of sums

To get a minimum product of sums, run the same procedure on the OFF-set (the maxterms) to get a minimum sum of products for $F'$, then complement it with De Morgan: every product term becomes a sum term with the literals complemented. For $F$ above, the OFF-set is $\{3,4,11,12,13,15\}$; the method gives $F' = B'CD + BC'D' + ABD$ (3 terms, 9 literals), so $F = (B + C' + D')(B' + C + D)(A' + B' + D')$.

What the method costs

The number of cubes in the tables and of products in Petrick's method can grow very fast with the number of variables. The largest number of prime implicants over all functions is 2, 6 and 13 for 2, 3 and 4 variables:

Charts without any essential prime implicant are rare (584 of the 65536 four-variable functions), but a choice left after the essential primes and the dominance steps is common (21656), so Petrick's method or a tie-break is a normal part of the work. The covering step is the hard part; the combining step only enumerates.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The Karnaugh map and the tabular method find the same prime implicants: a group on the map is a cube of the table. The result feeds the design of combinational circuits, where the cost of the cover is the number of gates and gate inputs.

PYQs

Consider a Boolean function F with the following
min-term expression:
F(P, Q, R, S) = Σm(1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Which of the following options is/are the minimal
sum-of-products expression(s) of F?

Self-check

Revision card

References