Karnaugh Map

A Karnaugh map (K-map) is a grid layout of a truth table, arranged so that adjacent cells differ in only one variable. That adjacency makes minimization visual: groups of $1$ s in adjacent cells correspond to product terms with one fewer variable.

Each cell is a minterm. Cells are ordered in Gray code (one bit change between neighbors) along both axes. The grid is toroidally connected — the leftmost column is adjacent to the rightmost, and the top row is adjacent to the bottom. So a $1$ in the corner can group with a $1$ in the opposite corner.

Why grouping works

Two minterms that differ in exactly one variable can combine: the variable that flips drops out. Algebraically, $\overline{x_{1}} x_{2} + x_{1} x_{2} = (\overline{x_{1}} + x_{1}) x_{2} = x_{2}$ . On a K-map, those two minterms are in adjacent cells, and circling them as a group of two replaces both with the single product term $x_{2}$ .

Doubling the group size drops one more variable. Four adjacent cells (a $2 \times 2$ block, or a $1 \times 4$ row) eliminate two variables. Eight cells eliminate three. Always group in powers of two — that’s the only shape where the algebraic cancellation works out cleanly.

Building one

Pick the K-map shape based on the number of variables:

2 variables: $2 \times 2$ grid.
3 variables: $2 \times 4$ grid (one variable along rows, two along columns in Gray order).
4 variables: $4 \times 4$ grid.

For SOP solutions, fill in $1$ s where the function is true (and $0$ s elsewhere). Then identify groups.

Solving

Strategy: cover every $1$ with as few groups as possible, and make each group as large as possible.

The product term for a group is read off by listing the variables that don’t change across the group’s cells. Variables that take both values in the group drop out. If a variable is constantly $1$ in the group, it appears uncomplemented; if constantly $0$ , it appears complemented.

Worked example for a 3-variable K-map with $1$ s at minterms 1, 4, 5, 6:

Two groups: ${1, 5}$ gives $\overline{x_{2}} x_{3}$ (because $x_{2} = 0$ and $x_{3} = 1$ throughout, $x_{1}$ varies). ${4, 6}$ gives $x_{1} \overline{x_{3}}$ . Result: $f = x_{1} \overline{x_{3}} + \overline{x_{2}} x_{3}$ , a 4-literal SOP from a 4-minterm function.

POS solutions

Same procedure but group the $0$ s instead. Each group becomes a maxterm. To read it off, take the complement of the literals: a group where $C = 0, D = 1, B = 1$ throughout becomes $C + \overline{D} + \overline{B}$ .

Key terms

Literal: an appearance of a variable in a product term, complemented or not.
Implicant: a product term that makes the function true wherever it’s true. Visually, a rectangular group of $1$ s.
Prime implicant: an implicant that can’t be combined into a larger group. The maximal rectangle.
Essential prime implicant (EPI): a prime implicant covering at least one $1$ that no other prime implicant covers. EPIs are mandatory in any minimum cover.
Cover: a set of implicants whose union accounts for every $1$ in the K-map.

The minimum-cost cover is found by:

Identifying all prime implicants.
Finding all EPIs and including them automatically.
Picking additional prime implicants to cover any $1$ s left, choosing the largest available groups.

For example, given the function below with minterms grouped:

The expression $f_{3} = \overline{x_{2}} x_{4} + \overline{x_{1}} x_{3} + x_{2} x_{3} x_{4}$ comes out of three groups — two pairs and a single — each read by the variables that stay constant.

Don’t-cares

If some input combinations can’t occur (or you don’t care about the output for them), mark the cells with a $d$ instead of $0$ or $1$ . Don’t-cares are flexible: include them in a group when it makes the group bigger (they count as $1$ for SOP grouping); leave them out when they don’t help. See Don’t Care Condition.

Limits

K-maps are practical up to 4 variables and stretch to 5 or 6 with mirror-image conventions (treating two halves of the map as overlapping planes for the extra variable). Past 6 variables they become impractical and you switch to algorithmic methods (Quine-McCluskey, Espresso). For LUT-based FPGA design, the synthesis tool handles minimization automatically.

The expression that comes out of a K-map isn’t always fully minimum — sometimes a further algebraic step can shrink it more.

Idriss Rami — Notes

Explorer