Two-Level Minimization with Prime Implicants and the Quine-McCluskey Method

A canonical sum of products is correct and enormous. Reducing it means finding larger implicants, terms that cover more assignments with fewer literals, and then choosing a subset of them that covers every one-row of the truth table. The first part is mechanical and tractable. The second part is a set-cover problem, and that is where the trouble starts.

Merging adjacent minterms

The merge rule is the whole engine of two-level minimization. Two product terms that are identical except for one variable, which appears complemented in one and uncomplemented in the other, combine into a single term with that variable removed:

$$x, \bar y, z + x, y, z = x, z$$

Each merge doubles the number of assignments the term covers while removing one literal, so the ratio of covered assignments to literals improves by more than a factor of two. Repeat until no more merges are possible and every term is a prime implicant.

An implicant of $f$ is any product term that implies $f$: it is true only on assignments where $f$ is true. It is prime if removing any literal makes it no longer an implicant. The set of prime implicants is unique for a given function — there is exactly one such set, though there are many covers built from it.

Two facts make prime implicants the right search space. First, every minimal sum of products consists only of prime implicants, because any non-prime term could be enlarged to cover more assignments at no extra cost. Second, the problem therefore reduces to selecting prime implicants that cover all the ones.

The Karnaugh map as a reordered truth table

The Karnaugh map is a truth table drawn so that physically adjacent cells differ in exactly one variable. For four variables the map is a 4-by-4 grid with rows and columns labelled in the order 00, 01, 11, 10 — Gray code — so that moving one cell horizontally or vertically flips one bit. Wrap-around adjacency applies at the edges: the leftmost and rightmost columns are adjacent, as are the top and bottom rows, because the map is topologically a torus.

A group of $2^k$ adjacent ones in the map corresponds to a product term with $n-k$ literals. A group of two cells removes one variable, four cells remove two, eight cells remove three. The rule for reading the term off the map: any variable that is constant across all cells of the group appears in the term, with the polarity of that constant; variables that change are dropped.

The map’s value is that it makes adjacency visual, which is why it remains the standard teaching device and a useful check for functions of up to four or five variables. Its limitation is equally clear: a five-variable map needs two four-variable planes that must be mentally joined, and a six-variable map needs four. Beyond that the visual method fails, and a tabular algorithm is needed.

The map also exposes the covering choice. Some cells are covered by exactly one prime implicant — these are essential prime implicants and must be in every cover. After selecting all essentials and removing the rows they cover, what remains is a smaller covering problem, and sometimes a choice between equally small alternatives with different gate-level consequences.

Don’t-care conditions and the expanded cover

Real designs rarely specify all $2^n$ output values. A circuit that decodes only the bit patterns a counter can actually produce does not care what it outputs for the patterns that never occur, and a circuit whose output is ignored during a particular mode does not care what it produces then.

These unspecified rows are don’t-cares, and they change the minimization problem from “cover the ones without covering any zero” to “cover the ones without covering any zero, using don’t-cares freely as part of implicants”. A don’t-care may be included in a group if that makes the group larger, but it need not be covered.

The effect can be dramatic. A function whose ones form a sparse pattern that becomes a large block when the don’t-cares are admitted may collapse to a handful of literals. It is also the mechanism by which a designer encodes intent into a specification: declaring an input combination impossible licenses the minimizer to exploit it, and if the assumption later breaks — a mode is added, a counter reaches an unexpected state — the circuit’s output for that combination is whatever the minimized logic happens to produce, which is usually not what the new requirement wants. Don’t-care sets are contracts about the environment, not free optimization opportunities.

The Quine-McCluskey tabulation

Quine–McCluskey performs the merge systematically, without a map. The procedure for $n$ variables:

1. List the minterms of $f$, each written as an $n$-bit string, and group them by the number of ones in the string.
2. Compare each term in group $k$ with each term in group $k+1$. If they differ in exactly one bit, merge them into a term with a dash in that position, and mark both parents as combined.
3. Repeat on the merged terms, grouping by count of ones ignoring dashes.
4. When no further merges are possible, the unmarked terms are the prime implicants.
5. Build a table with prime implicants as rows and minterms as columns, mark the cells where the prime implicant covers the minterm, select essential rows, then solve the remaining cover.

The grouping by ones count is not cosmetic. Two terms differing in exactly one bit necessarily have ones counts differing by exactly one, so only terms in adjacent groups need be compared. That restriction reduces the pairwise comparison count substantially, though it does not change the asymptotic behaviour.

def merge_pass(terms):
    """One round of Quine-McCluskey merging. Terms use '-' for a dropped variable."""
    merged, used = set(), set()
    for a in terms:
        for b in terms:
            if a >= b:
                continue
            diff = [(i, x, y) for i, (x, y) in enumerate(zip(a, b)) if x != y]
            if len(diff) != 1:
                continue
            i, x, y = diff[0]
            if "-" in (x, y):
                continue
            merged.add(a[:i] + "-" + a[i + 1:])
            used.add(a)
            used.add(b)
    return merged, [t for t in terms if t not in used]


def prime_implicants(minterms, n):
    current, primes = sorted(minterms), []
    while current:
        merged, leftovers = merge_pass(current)
        primes.extend(leftovers)
        current = sorted(merged)
    return sorted(set(primes))

The loop terminates because the terms carried into the next pass gain exactly one dash each round, and a term of $n$ variables can carry at most $n$ dashes, so there are at most $n+1$ passes. In the worst case the number of terms grows combinatorially before it shrinks, which is the practical problem with the method: intermediate term counts can exceed the number of minterms by a wide margin.

Why the cover is the hard part

Step 5 is an exact minimum set cover. Given a universe of minterms and a family of prime implicants each covering a subset, find the smallest subfamily whose union is the universe. This problem is NP-hard, and two-level minimization inherits that hardness.

The practical consequence is a threshold. Exact minimizers handle functions with roughly a dozen inputs and a modest number of prime implicants. Above that, the prime implicant set itself can grow exponentially, and the cover search on top of it becomes hopeless. Synthesis tools therefore run a heuristic: generate a good cover greedily, then improve it with local transformations that replace a set of terms with a cheaper set covering the same minterms. The result is not guaranteed minimal and is usually close enough, because literal count in a two-level expression is only a proxy for the cost of the final multi-level network anyway.

There is also a classical result that bounds how bad the heuristic can be in the worst case, but the bound is loose and says little about real functions. The honest statement is that exact minimization is a small-input tool, and the interesting optimization happens later, after technology mapping, where the cost function is actual cell area and delay rather than literal count.

Reading a minimized expression back into gates

A minimized sum of products with $k$ terms and maximum term width $w$ maps to a two-level network: $k$ AND gates of up to $w$ inputs feeding one OR gate of $k$ inputs. In CMOS, De Morgan turns this into $k$ NAND gates feeding one NAND gate, which is the same depth with inverting gates.

The depth is two gate delays regardless of $k$, which is the appeal of two-level logic: predictable, short latency. The cost grows with $k$ and $w$ in ways that are not linear. A wide AND term becomes a tall series stack in the pull-down network, and as the gate structure explains, series stacks are slower than their device count suggests. A term with more than about four literals is usually better factored into a tree.

That factoring is precisely what two-level minimization does not do. It produces a flat expression, and the multi-level restructuring that follows — common subexpression extraction, balancing, and technology mapping — belongs to synthesis rather than to logic minimization proper. A minimized two-level form is a well-defined waypoint, not a finished netlist.

For functions with many inputs, the flat form is not even a reasonable waypoint. A 32-input function would need terms of up to 32 literals, and the prime implicant set is astronomically large. Such functions are built structurally instead: from adders, comparators, and multiplexer trees whose correctness is argued compositionally rather than by covering a truth table.