Logic Minimization & Karnaugh Maps

A canonical SOP expression, from the previous page, is correct by construction but rarely efficient — it uses one AND term per truth-table row where the output is 1, even when many of those terms overlap and could combine into something far smaller. Logic minimization is the process of turning that correct-but-bloated expression into one with fewer terms and fewer literals, which translates directly into fewer gates, less silicon area, and less propagation delay in the final circuit.

Why minimization matters physically

Every literal (a variable, complemented or not) in a minimized SOP expression corresponds to a transistor pair in the eventual CMOS gate-level implementation. A four-term, three-literal-per-term SOP expression synthesizes to a real, physical AND-OR gate network; halving the term count roughly halves that portion of the circuit's area and power. This is why minimization isn't an academic exercise — it's the first, cheapest optimization available, done before a design ever reaches a synthesis tool (which performs a far more sophisticated version of the same idea automatically, but starting from whatever expression you gave it).

The Karnaugh map (K-map)

A Karnaugh map is a truth table rearranged into a grid, where adjacent cells differ in exactly one variable — the K-map's rows and columns are labeled using Gray code (from Digital Codes) specifically to guarantee that adjacency property. That single design choice is what makes the whole technique work: because adjacent cells differ by one bit, any group of adjacent 1-cells can be combined into a single, smaller product term where the differing variable simply drops out.

A 3-variable example

Truth table for F(A,B,C):
A B C | F
0 0 0 | 0
0 0 1 | 1
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1

K-map (rows = A, columns = BC in Gray order 00,01,11,10):

          BC=00  BC=01  BC=11  BC=10
  A=0       0      1      1      0
  A=1       0      1      1      0

Every cell where C=1 is a 1 regardless of A or B — the entire BC=01 and BC=11 columns are 1, forming one large group of four adjacent cells. Reading that group: A varies (drop it), B varies (drop it), C stays 1 throughout (keep it). The whole function minimizes to F = C — a truth table that looked like it needed four minterms turns out to be a single wire.

Grouping rules

• Groups must have a size that's a power of 2: 1, 2, 4, 8 cells.
• Larger groups are always better — an 8-cell group eliminates 3 variables from that term, a 2-cell group eliminates only 1.
• Groups can wrap around the edges of the map (the leftmost and rightmost columns are adjacent, same for top and bottom rows) — this is a direct consequence of the Gray-code labeling, where the first and last codes in the sequence also differ by only one bit.
• Every 1 cell must be covered by at least one group, but cells can belong to more than one group if that produces a better overall minimization.
• The final expression is the OR of all the minimal terms represented by the chosen groups.

Wraparound adjacency, explicitly

The "groups can wrap around the edges" rule is easy to state and easy to miss in practice, because a 2D grid on paper doesn't visually connect its own edges. Consider this 4-variable K-map (rows = AB, columns = CD, both in Gray order 00, 01, 11, 10):

          CD=00  CD=01  CD=11  CD=10
  AB=00     1      0      0      1
  AB=01     0      0      0      0
  AB=11     0      0      0      0
  AB=10     1      0      0      1

Nothing here looks adjacent on the page — the four 1s sit in the four corners, as far apart as a 4x4 grid can place them. But because the leftmost and rightmost columns (CD=00 and CD=10) are Gray-code neighbors, and the top and bottom rows (AB=00 and AB=10) are Gray-code neighbors too, all four corner cells are mutually adjacent — they form one valid 4-cell group. Reading it: CD stays fixed at 00 throughout the group (C=0, D=0) while AB varies across all four combinations, so the group reduces to F = C'D'. A solver who only checks orthogonally-touching cells on the drawn grid — and never checks the map's own edges against each other — will miss this group entirely and land on a needlessly larger expression built from four separate single-cell groups instead.

Prime implicants and essential prime implicants

Two K-maps can group the same set of 1-cells in more than one valid way, so "a" minimal expression isn't always unique — this is where the vocabulary of implicants matters:

• An implicant is any valid group of adjacent 1-cells (size 1, 2, 4, 8, ...) — a candidate term, not necessarily part of the final answer.
• A prime implicant (PI) is an implicant that cannot be enlarged any further by merging with a neighboring group of the same or larger size — it's already maximal.
• An essential prime implicant (EPI) is a prime implicant that is the only prime implicant covering at least one particular 1-cell. Since that cell has no other way to get covered, every valid minimal expression must include that PI.

The minimization procedure is: find every prime implicant on the map, identify which ones are essential (must be included), include all of them, then cover any remaining 1-cells not yet covered by an essential PI using the smallest additional set of (non-essential) prime implicants needed. Skipping the "essential" check and just picking whichever large groups look convenient can produce a correct but non-minimal expression — technically covering every 1-cell, but with more terms than necessary because a redundant non-essential PI was included alongside ones that already covered its cells.

Minimizing for POS instead of SOP

Every example so far groups the 1-cells to build a minimal sum-of-products (SOP) expression. The mirror-image technique groups the 0-cells instead, using the exact same adjacency and grouping rules, to build a minimal product-of-sums (POS) expression: each group of 0s yields one sum term (OR of literals, complemented relative to the SOP reading), and the final expression is the AND of all those sum terms. The two techniques solve the same function from opposite ends of the same map — POS is preferred when the 0-cells are far fewer/more compactly groupable than the 1-cells, since a smaller set of groups either way means a smaller final circuit.

Don't-care conditions

Some truth-table rows correspond to input combinations that can never actually occur in the real circuit — an encoder that only ever receives one-hot inputs, for instance, has defined behavior for exactly one such input pattern per output, and no obligation to define what happens for the others. Those rows are marked X (don't-care) rather than 0 or 1, and — this is the useful part — a don't-care can be treated as either 0 or 1, whichever helps form a larger group, since the specification places no constraint on that row at all.

          BC=00  BC=01  BC=11  BC=10
  A=0       0      1      X      0
  A=1       0      1      1      0

Treating the X as a 1 here extends the BC=01/BC=11 group into a full 4-cell group spanning both A rows, exactly as in the first example — a smaller expression than would be reachable if that cell were forced to 0. Don't-cares cost nothing to exploit and can only help, which is why real minimization always accounts for them when they exist.

Limits of the K-map method

K-maps stay visually manageable up to about 4–5 variables; beyond that, the 2D-grid layout stops being humanly readable, and the systematic alternative is the Quine–McCluskey method — a tabular algorithm that finds the same guaranteed-minimal groupings by exhaustively comparing minterms for single-bit differences, rather than relying on spatial adjacency a person can see. It's more mechanical and more tedious by hand, but unlike a K-map, it scales cleanly to any number of variables — which is exactly why it's the algorithm (or a refinement of it) that logic synthesis tools actually run internally, on functions with far more inputs than a human would ever attempt by hand.

Where minimization stops paying off

Manual K-map minimization is a foundational skill for building correct intuition about logic — but on any function with more than a handful of inputs, hand minimization is both slower and less reliable than letting a synthesis tool do it. The value of learning this by hand isn't that you'll do it professionally at scale; it's that understanding why a synthesis tool's output looks the way it does — and being able to sanity-check it — depends on having actually done the minimization yourself at least once.

What's next

With minimization covered, the next section moves from single Boolean expressions to complete combinational circuits — the standard building blocks (adders, multiplexers, decoders) that every larger digital design is assembled from, and the general methodology for designing any of them from a specification.