Karnaugh Maps (K-Maps)

Why simplify at all

The previous lesson's canonical sum-of-products form is always correct and always mechanical to write down, but it is almost never cheap to build: a function read straight off an 8-row truth table can need as many AND gates as there are 1s in the output column, each one as wide as the function has variables. Fewer literals in the final expression means fewer gate inputs, which in turn means less area, less capacitance to drive, and less delay. A Karnaugh map (K-map) is a way of finding that smaller expression by eye, for functions small enough to draw – in practice, up to about five or six variables, beyond which the grid becomes too large to read reliably and the job moves to algorithms such as Quine–McCluskey or, in any real design today, to a synthesis tool.

The idea: adjacency means "differs in one variable"

A K-map is a grid of cells, one per truth-table row, arranged so that any two cells touching edge-to-edge represent minterms differing in exactly one variable. That single property is the entire mechanism: if two adjacent cells are both 1, the variable that differs between them does not matter for that part of the function, and algebra confirms it – AB'C + ABC = AC(B'+B) = AC. The map lets a designer spot that cancellation visually, as two neighbouring filled cells, instead of working through the algebra by hand each time.

Getting that adjacency property requires the row and column headers to be ordered so that only one bit changes between consecutive headers, which is exactly the Gray code sequence from the first lesson (00, 01, 11, 10, not the binary-counting order 00, 01, 10, 11). This is the payoff promised back then: a K-map is laid out in Gray-code order specifically so that physical adjacency in the drawing always matches "one variable apart" in the logic.

2- and 3-variable maps

A 2-variable map is a 2×2 grid, one cell per row of a 2-input truth table; a 3-variable map is a 2×4 grid, with one variable controlling the 2 rows and the other two controlling the 4 Gray-coded columns. The grouping rule is the same at every size: a rectangular block of 1s whose side lengths are powers of 2 – 1, 2, 4, 8 and so on – can be circled as one term, and the term's expression is whatever variables stay constant across every cell in the block. The variables that change across the block get dropped.

Every 1 sits in the C=1 column. A and B both vary freely across all four rows while staying grouped with C=1, so A and B drop out entirely and the whole function reduces to F = C. Thus, a group covering an entire half of the map always eliminates exactly the one variable that distinguishes the two halves.

A full 4-variable worked example

Let us work through a larger case. Take F(A,B,C,D) = Σm(0,1,3,4,5,8,9,11,12,13) – ten minterms, which as canonical SOP would need ten 4-literal AND terms. Laid out as a 4×4 map with rows AB and columns CD, both in Gray-code order, the picture looks like this:

Grouping rules

• Group size must be a power of 2 – 1, 2, 4, 8, or (for a 4-variable map) all 16 cells. A group of 3, 5 or 6 is never legal; it has to be re-drawn as two separate legal groups, or as one legal group plus a smaller leftover group.
• The group must be rectangular, including wrap-around, which still counts as rectangular on the map's cylindrical topology. An L-shape or a diagonal pair is never a single valid group.
• Bigger is better. Always prefer the largest legal rectangle covering a given 1, since doubling a group's size always removes exactly one more literal from its term.
• Groups may overlap. The same 1 can belong to more than one group if that is what minimizes the total literal count – a cell counts as "used" once it is covered by at least one chosen group, not by exactly one.
• Every 1 must be covered by at least one group, and the map is considered minimized once every 1 is covered by the fewest, largest groups available. A 1 that cannot join any adjacent 1 becomes its own single-cell group and keeps every one of its variables in the term.

Don't-care conditions

Some input combinations in a real design never occur. A BCD-to-something decoder's inputs 1010–1111 are not valid BCD digits and will never actually be driven, so the designer does not care what the circuit outputs for them. These rows are marked X (don't-care) in the truth table and the K-map, and the rule for using them is simple: treat an X as a 1 if including it allows a bigger group to be drawn, and ignore it – treat it as a 0 – otherwise. A don't-care is never required to be covered; it is only ever a convenience for enlarging a real group.

POS instead of SOP: group the zeros

Every rule above applies unchanged when grouping a map's 0s instead of its 1s. The result is a product-of-sums expression for the function's complement, and inverting that – one more application of De Morgan's law – gives a POS expression for the original function. Whether SOP or POS ends up the cheaper circuit depends entirely on which value, 1 or 0, is rarer in that particular truth table. For a function with mostly 1s and few 0s, grouping the 0s and converting to POS is usually the shorter path.

Where K-maps stop working

A 5-variable map needs two 4-variable grids side by side, or stacked depending on the convention used, with adjacency rules spanning between them; a 6-variable map needs four. Both are drawable but genuinely hard to read reliably by eye, and in practice nobody does a 7-variable map by hand. The algorithm a K-map is really a visual shortcut for – systematically combining adjacent terms, repeatedly, until no further combination is possible – has a tabular, scalable version called the Quine–McCluskey method. In any real design today, this entire step is simply delegated to a logic synthesis tool, which minimizes million-gate netlists using the same underlying adjacency idea at a scale no K-map drawn by hand could ever touch.