Logic minimization

The formula

Every minimization trick reduces to one identity, the adjacency theorem:

A·B + A·B' = A·(B + B') = A

If two product terms differ in exactly one variable, that variable is doing nothing — delete it and merge the terms. The Karnaugh map is a plot arranged so this identity becomes visible: rows and columns are ordered in Gray code (00, 01, 11, 10), so physically adjacent cells differ in one variable, including wraparound at the edges.

The payoff rule for grouping cells on an n-variable map:

a block of 2^k adjacent 1-cells → one product term with n − k literals

Double the group, drop a literal. A concrete four-variable case, the four corners of the map:

f(A,B,C,D) = Σm(0, 2, 8, 10) = B'·D'

Four minterms, sixteen literals as written; two literals after grouping — the corners are one block on the map's torus.

The Quine–McCluskey algorithm is the same adjacency theorem run as bookkeeping. Pair minterms whose binary codes differ in one bit and replace the differing bit with a dash:

101 (m5) + 111 (m7) → 1-1 = A·C

Repeat until nothing combines; the survivors are the prime implicants. Then pick the cheapest set of primes that covers every minterm — a set-cover problem.

One more identity earns its keep at review time, the consensus theorem:

A·B + A'·C + B·C = A·B + A'·C

B·C is logically redundant. Hold that thought — "redundant" and "removable" are not the same word in hardware.

Where you meet it

Glue logic on a board. An address decoder, a power-sequencing interlock, a fault-summary line OR-ing eight status bits with exceptions — you write the truth table from the ICD, and the K-map tells you whether that is two gates or ten. On safety-critical test-stand interlocks where the review board wants discrete gates instead of firmware, this is still done by hand, on paper, with initials on it.
FPGA synthesis reports. You rarely draw the map, but the synthesizer runs descendants of these algorithms on every always block you write. When utilization or timing goes sideways, reading the report means knowing what a prime implicant and a two-level cover are — otherwise the tool's decisions look like weather.
Reverse-engineering a legacy box. A 1980s relay chassis or a dead PAL with no source: you walk every input combination on the bench, log the outputs, and now own a raw truth table that has to become something buildable. Quine–McCluskey, or Espresso for anything wide, turns the log into equations.
The design review question. Somebody minimized a control signal that feeds an asynchronous input, and a reviewer asks whether it glitches when inputs change. That question is about hazards, and the answer lives in the consensus theorem below.

How it works

Start from the truth table in sum-of-products form: one AND term per row that outputs 1, all OR-ed together. That version works and is maximally expensive. Minimization is the search for an equivalent expression with fewer terms and fewer literals.

The adjacency theorem is the only move in the game. The K-map's Gray-code layout makes every legal move a visual rectangle: any power-of-two block of 1s — 1, 2, 4, 8 cells — collapses to a single term. The discipline is mechanical: blocks must be power-of-two sized, the map wraps top-to-bottom and left-to-right, and you want the fewest blocks, each as large as possible. Largest-possible blocks are the prime implicants; a block that is the only cover for some 1-cell is essential and goes in regardless.

The things that bite:

Don't-cares are free money. Output rows that can never occur, or whose value nobody downstream reads, get marked X and included in a group whenever they enlarge it, ignored when they don't. A BCD decoder has six don't-care codes out of sixteen; using them is routinely the difference between three literals and one. Verified small case: f = Σm(1,3,7) with d(5) minimizes to just C.
Minimal is not glitch-free. Take f = A·B + A'·C with B = C = 1. The output should sit at 1 while A transitions — but the A·B gate can drop before the A'·C gate picks up, and the output spikes low for a few nanoseconds. That is a static-1 hazard, and the fix is to add back the consensus term B·C that minimization removed. If the output clocks a flip-flop, gates a latch, or leaves the board, the "redundant" term is load-bearing. This is the classic field mistake: hand-minimizing to the theoretical floor and shipping the glitch.
The map runs out at about five variables. Four variables is comfortable, five and six need stacked maps and more care than they're worth. Past that it's Quine–McCluskey — exact, mechanical, and exponential. The number of prime implicants of an n-variable function can grow roughly as 3^n/√n; past 10^14 for 32 inputs, and the cover-selection step is NP-complete ^[5]. Exact minimization does not scale. Petrick's method handles the cover step systematically on small problems ^[5]; real tools gave up on exactness and went heuristic — Espresso finds near-minimal covers on functions with dozens of inputs and is what synthesis flows descend from ^[9].
On an FPGA, the cost function moved. A modern 6-input LUT implements any function of six inputs at identical cost — one truth table in RAM. Minimizing literals inside one LUT buys nothing. What matters now is input count and logic depth: whether the function fits in one LUT or cascades through three. Two-level minimization still runs under the hood, but hand-optimizing HDL for gate count is solving 1975's problem. Write it clear, read the synthesis report, and intervene only where the tool provably did badly.
Minimization assumes the truth table is right. The method preserves the function you gave it, including the wrong rows. A minimized implementation of a bad spec fails smaller and cheaper, but just as hard.

History

The tabular half came from a logician. W. V. Quine published "The Problem of Simplifying Truth Functions" in the American Mathematical Monthly in October 1952, laying out the reduction to prime implicants, and tightened the procedure in a 1955 follow-up ^[5]^[6]. Edward McCluskey, then finishing his doctorate at MIT, turned Quine's approach into the systematic bit-by-bit tabulation engineers could actually run, publishing "Minimization of Boolean Functions" in the Bell System Technical Journal in November 1956, drawn from his thesis ^[7]^[8]. The hyphenated name stuck.

The graphical half is a two-step. Edward Veitch presented "A Chart Method for Simplifying Truth Functions" at the ACM national meeting in Pittsburgh in May 1952, plotting a function's outputs on a grid so simplifications could be spotted rather than derived — but his chart kept the rows in truth-table order ^[3]^[4]. The next year Maurice Karnaugh at Bell Telephone Laboratories in Murray Hill made the one change that mattered: reorder the rows and columns into Gray code, so every adjacency on paper is an adjacency in logic. His "The Map Method for Synthesis of Combinational Logic Circuits" was presented at the AIEE Summer General Meeting in June 1953 and published that November ^[1]^[2]. Veitch had the idea; Karnaugh had the coordinate system. Engineers vote with their pencils, and the pencils chose Karnaugh.

By the late 1970s chips had outgrown both men's methods. Starting in 1982 at the IBM T. J. Watson Research Center, Robert Brayton and colleagues — with Alberto Sangiovanni-Vincentelli of UC Berkeley — built Espresso, a heuristic minimizer that traded guaranteed minimality for the ability to chew through functions no exact method could touch; the 1984 book Logic Minimization Algorithms for VLSI Synthesis documented it and seeded the synthesis tools every FPGA flow uses today ^[9]^[10].

Related tools

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →