Karnaugh Maps

A truth table lists $2^n$ rows for $n$ variables, but it encodes no notion of "closeness" between rows — row 3 and row 4 look no more related than row 3 and row 12. Boolean simplification, however, is entirely about closeness: the identity $AB\bar{C} + AB C = AB$ works precisely because the two terms differ in only one literal ($C$ vs. $\bar C$), so they merge via $\bar C + C = 1$. A Karnaugh map makes this closeness visible by arranging the $2^n$ minterms into a grid where physical adjacency equals logical adjacency (differing in exactly one variable). The trick is Gray code: a sequence of binary strings in which consecutive entries differ in exactly one bit. Row and column headers of a K-map are labeled with Gray-code sequences (e.g., `00, 01, 11, 10` rather than the natural binary order `00, 01, 10, 11`). Because of this labeling, any two cells that are horizontally or vertically neighbors — including cells that "wrap around" from the last column to the first, or last row to first — differ in exactly one variable's value. A group of $2^k$ adjacent cells that are all 1 (or don't-care) corresponds to a single product term in which $k$ of the $n$ variables have been eliminated, because those $k$ variables take on both values (0 and 1) somewhere inside the group while the term's output stays 1 regardless. The goal of K-map minimization is to find a minimal sum-of-products (SOP) expression: cover every 1-cell in the map using the fewest possible groups, each as large as possible, so that the resulting sum of product terms is logically equivalent to the original function but uses fewer literals and fewer terms. A group of size $2^k$ eliminates $k$ variables from its term; larger groups are exponentially more valuable, so the central heuristic is always "grow every group as large as legality allows, then choose the smallest set of groups that covers all 1s." A group whose 1s are covered by no other group is called an essential prime implicant, and it must appear in any minimal cover — this fact underlies both the manual method and its algorithmic generalization, the Quine–McCluskey method.

Step 1 — Build the map. For $n$ variables, arrange $2^n$ cells in a 2D (or, for $\ge 5$ variables, layered) grid. Split the variables between rows and columns as evenly as possible (e.g., for 4 variables $AB$ label rows, $CD$ label columns), and label both axes in Gray-code order.

Step 2 — Populate. Fill in each cell with the truth-table output (0, 1, or `X` for don't-care) for the minterm at that row/column intersection.

Step 3 — Group. Circle rectangular groups of 1s and don't-cares. A group is legal only if:

• its size is a power of two: 1, 2, 4, 8, …
• it forms a rectangle (including wraparound across map edges, and toroidal wraparound for 4-variable maps in both directions)
• every cell inside is 1 or `X` (never a bare 0)

Step 4 — Maximize each group. Every group should be as large as possible — a group of 4 is always preferred over two separate groups of 2 covering the same 1s, since it produces one term with one fewer literal.

Step 5 — Find essential prime implicants. A prime implicant is a group that cannot be enlarged further. It is essential if it is the only group covering at least one particular 1-cell. All essential prime implicants must be included in the final expression.

Step 6 — Minimal cover. After including all essential groups, if some 1s remain uncovered, select additional (non-essential) prime implicants to cover them, preferring the largest groups and the fewest additional groups (a small instance of set cover).

Step 7 — Write the expression. For each chosen group, write the product term consisting only of the variables that stay constant across the group (drop any variable that takes both 0 and 1 within the group). Sum these terms with OR. ``` function KMAP-MINIMIZE(truth_table, variables): map = build_kmap(truth_table, variables) # Gray-code axes groups = enumerate_all_legal_groups(map) # all rectangles of size 2^k

# containing only 1/X prime_implicants = [] for g in groups: if not exists g' in groups such that g is a strict subset of g': prime_implicants.append(g) # g cannot be enlarged essential = [] uncovered_ones = all_cells_with_value(map, 1) for one_cell in uncovered_ones: covering = [pi for pi in prime_implicants if one_cell in pi] if length(covering) == 1: essential.append(covering[0]) # only one PI covers it essential = deduplicate(essential) covered = union of cells in essential remaining = uncovered_ones - covered chosen = essential while remaining is not empty:

# pick the prime implicant covering the most

# still-uncovered 1-cells (greedy set cover) best = argmax_{pi in prime_implicants} |cells(pi) ∩ remaining| chosen.append(best) remaining = remaining - cells(best) expression = OR of [term_for_group(g, variables) for g in chosen] return expression

function term_for_group(g, variables): term = [] for v in variables: if v is constant (always 0 or always 1) across all cells in g: term.append(v if constant==1 else NOT v)

# else v is eliminated — varies within the group return AND(term) # empty AND-list means constant "1" ``` The greedy step for non-essential coverage is a heuristic — exact minimum set cover is NP-hard in general — but for the small maps (2–4 variables, occasionally 5–6) that K-maps are used for by hand, this greedy pass combined with essential-PI extraction reliably finds a truly minimal or near-minimal cover, and a human doing it visually can simply check by inspection.

Time complexity of the hand method. For $n$ variables there are $2^n$ cells. The number of possible rectangular groups is bounded by $O(3^n)$ (each variable is either fixed to 0, fixed to 1, or eliminated in a candidate group, giving $3^n$ candidate product terms total, each of which is a candidate group). Enumerating all prime implicants and checking essentiality against $2^n$ minterms takes $O(3^n \cdot 2^n)$ in the worst case using the naive algorithm above — this is exactly why K-maps are a hand/visual tool for $n \le 4$ (occasionally 5–6 with layered maps) and not a scalable algorithm: it is the same exponential blowup that afflicts the algebraically equivalent Quine–McCluskey procedure, and both are eventually superseded in industrial tools by heuristic algorithms such as Espresso, which never enumerate all implicants explicitly.

Space complexity. The map itself is $O(2^n)$ cells; storing all candidate groups is $O(3^n)$ in the worst case, since each of the $n$ variables independently contributes a factor of "fixed-0 / fixed-1 / don't-care" to the space of possible product terms.

Correctness — why grouping produces valid simplification. The core algebraic fact is the identity

for any product term $X$ over the remaining variables and any single variable $V$. A size-2 group merges two minterms differing in exactly one variable $V$; the Gray-code layout guarantees such minterms are adjacent, so a legal group of size 2 is precisely an instance of this identity, and $V$ is correctly dropped from the term. Induction extends this to groups of size $2^k$: a size-4 group is a union of two adjacent size-2 groups whose merged terms differ in one further variable, which then also cancels, and so on. Hence every legal group corresponds to a valid simplification, and conversely, every simplification obtainable through repeated application of $X + XV + X\bar V = X$ has a representation as a rectangular group on the Gray-coded map — the geometric adjacency structure is a faithful encoding of the algebra, not merely a mnemonic.

Correctness of the essential-prime-implicant argument. If a 1-cell is covered by only one prime implicant, that implicant must be present in any correct sum-of-products cover of the function (otherwise that minterm is not produced by the expression), which proves essential prime implicants are mandatory. After forcing all essential implicants in, the remaining uncovered 1s must be covered by some selection of the remaining (non-essential) prime implicants; because we only need any valid cover (not necessarily the provably-optimal one for large $n$), greedy largest-first selection is used in practice and is exact for the small cases K-maps are designed for.

Tradeoffs, honestly stated. K-maps guarantee a minimal two-level (SOP) form given a correct, exhaustive grouping, but:

• Beyond 4–6 variables, visual grouping becomes error-prone and the $O(3^n)$ blowup makes exhaustive enumeration impractical — real EDA tools use Quine–McCluskey (exact, exponential) or Espresso (heuristic, scalable but not always provably minimal).
• K-maps minimize a two-level (SOP or POS) realization; they do not directly minimize multi-level logic (circuits with several layers of gates), which is what modern synthesis tools ultimately optimize for area/delay/power.
• The greedy non-essential selection can, in rare configurations with multiple ties, require backtracking to find a truly minimal cover — a subtlety usually elided in introductory treatments but real in the underlying set-cover problem.

Consider a 4-variable majority-like function $F(A,B,C,D)$ specified by this truth table (minterm numbers in standard order $ABCD$):

Binary breakdown: $m_3=0011$, $m_7=0111$, $m_{11}=1011$, $m_{12}=1100$, $m_{13}=1101$, $m_{14}=1110$, $m_{15}=1111$; don't-cares $m_8=1000$, $m_9=1001$. Lay this into the same Gray-code K-map as the figure above (rows $AB \in \{00,01,11,10\}$, columns $CD \in \{00,01,11,10\}$):

Grouping, step by step: 1. The entire bottom-plus-adjacent row `AB=11` is all 1s (4 cells): m₁₂, m₁₃, m₁₅, m₁₄. That's a size-4 group where $A=1, B=1$ constant, $C,D$ vary — term $AB$. 2. Column `CD=11` has 1s at rows `AB=00,01,11,10` — all four rows. Cells: m₃, m₇, m₁₅, m₁₁. This is a legal size-4 group (an entire column), giving term $CD$ (since $C=1,D=1$ constant, $A,B$ vary across all rows). 3. The don't-cares at m₈ (`AB=10, CD=00`) and m₉ (`AB=10, CD=01`) sit adjacent to the solid 1s in row `AB=11`. Treating them as 1 lets us merge the entire `AB∈{11,10}` block for column `CD=00` and `CD=01` too — check: cells m₁₂(1), m₈(X→1), m₁₃(1), m₉(X→1) form a 2×2 block (rows AB=11,10 and columns CD=00,01) that is entirely 1/X. This gives a size-4 group where $A=1$ constant (both rows have $A=1$), and $B$ varies (11 vs 10 differ in second bit)... checking carefully: `AB=11` and `AB=10` share $A=1$ but differ in $B$; `CD=00` and `CD=01` share $C=0$ but differ in $D$. So the constant literals are $A=1, C=0$, giving term $A\bar C$. Now check coverage: does group 1 ($AB$) plus group 3 ($A\bar C$) already cover everything group 2 ($CD$) was covering?

• $m_3$ (0011): covered only by $CD$ (since $A=0,B=0$, not in $AB$ or $A\bar C$ groups). Essential — $CD$ must stay.
• $m_7$ (0111): covered only by $CD$. Confirms $CD$ essential.
• $m_{11}$ (1011): covered only by $CD$ (here $A=1,B=0$, so not in $AB$-group which needs $B=1$; not in $A\bar C$ which needs $C=0$, but here $C=1$). Confirms $CD$ essential again.
• $m_{12}, m_{13}, m_{14}, m_{15}$: all covered by $AB$ group.
• $m_8, m_9$: don't-cares, covered by $A\bar C$ group, need not be forced but including the group is "free" since it also helps simplify — check if $A\bar{C}$ is actually needed: without it, are $m_8, m_9$ (don't cares) covered? They don't need to be covered at all (don't-cares can be left as 0), so $A\bar C$ is optional. But does dropping it lose anything? $m_{12}, m_{13}$ are already covered by the $AB$ group. So group 3 is not essential — every real 1 it covers is already covered elsewhere.

Minimal cover: essential prime implicants are $AB$ and $CD$; group 3 ($A\bar C$) turns out to be redundant once $AB$ is included, since $AB$ already covers $m_{12}, m_{13}$ and the don't-cares needed no coverage.

This is a 2-term, 4-literal expression — a substantial reduction from the naive 7-term, 28-literal sum-of-minterms expansion the truth table would otherwise dictate.

The map is named for Maurice Karnaugh, an American physicist and mathematician working at Bell Labs, who published the technique in 1953 as a refinement of a similar chart introduced earlier by Edward Veitch — hence the map is sometimes called the Veitch–Karnaugh diagram. Karnaugh's contribution was to reorganize Veitch's layout using reflected binary (Gray) code, which is the exact feature that gives every adjacent pair of cells the one-variable-difference property central to the method. The underlying Gray code itself predates Karnaugh's application by decades, tracing to telegraphy and later formalized by Frank Gray at Bell Labs in the 1940s for use in pulse-code modulation, illustrating how a piece of communications-engineering mathematics found an entirely new life in digital logic design.

K-map-style minimization is the conceptual seed of modern logic synthesis: every EDA toolchain that compiles a hardware description language (Verilog, VHDL) down to gates performs two-level and multi-level logic minimization, using algorithms descended from the same principles — Quine–McCluskey for exactness, Espresso and its successors for scale. Chip designers building decoders, encoders, multiplexers, comparators, and the control logic feeding an ALU all rely on minimized combinational logic to reduce gate count, critical-path delay, and dynamic power. The next-state and output logic of a finite state machine — the control unit of a processor, a traffic-light controller, a vending-machine dispenser — is itself a set of Boolean functions of the current state and inputs, and minimizing that logic (by hand for small FSMs, by tool for large ones) is a direct application of the same grouping principle a K-map teaches. Even outside hardware, the same Gray-code adjacency idea reappears in rotary encoders, error-correcting codes, and combinatorial search algorithms that benefit from single-bit-change traversal orders.

Ask the tutor: Can you walk me through minimizing a 5-variable function using two overlapping 4-variable K-map sheets?