Logic Minimization: Karnaugh Maps
A circuit straight from SOP works on the first try, but it contains more gates than necessary. The three-judge voting from the previous article took 8: three NOTs, four three-input ANDs, and one four-input OR. The same signal can be described by 4 gates: three two-input ANDs and one three-input OR. Maurice Karnaugh published the map method in 1953 while working as an engineer at Bell Labs, and it has been the first tool of hand minimization taught to engineers ever since.
Merging adjacent rows
The method rests on one identity: if two minterms differ in a single variable, that variable disappears. Take the last two rows of the voting table, A = 1, B = 1:
(A AND B AND C) OR (A AND B AND NOT C) = A AND B AND (C OR NOT C) = A AND BThe bracket "C OR NOT C" always equals 1, so instead of two three-input ANDs one two-input AND remains. Such pairs of rows are called adjacent: they differ in exactly one bit.
The map: same rows, Gray code order
To make neighbors visible at a glance, Karnaugh rearranged the rows of the table. The map for three variables looks like this: rows correspond to A, and columns correspond to the BC combination in the order 00, 01, 11, 10 (Gray code, where neighboring combinations differ in one bit):
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
The order 00, 01, 11, 10 is not accidental: in plain binary order the step from 01 to 10 flips two bits at once, and adjacency is lost. In Gray code any neighboring cells, including the wraparound across the map edge, differ in exactly one bit.
Loops
The ones on the map are wrapped in loops. Three rules: a loop's size is a power of two (1, 2, 4, 8 cells); the map edges are closed, so the leftmost column neighbors the rightmost one and the top row neighbors the bottom one; loops may overlap, but every one must land in at least one loop. A variable that takes both 0 and 1 inside a loop is dropped from the result.
Three loops of two cells each cover the voting ones: the whole BC = 11 column (only A changes, leaving B AND C), the bottom pair in the second and third columns (A = 1 at BC = 01 or 11, only B changes, leaving A AND C), and the bottom pair in the third and fourth columns (A = 1 at BC = 11 or 10, only C changes, leaving A AND B):
F = (B AND C) OR (A AND C) OR (A AND B)assign f = (b & c) | (a & c) | (a & b);The result: 8 gates shrink to 4. The depth drops too: an SOP circuit passes NOT, then AND, then OR — three gates in a row; the minimized one passes only AND and OR, two in total. The shorter the chain, the sooner the circuit settles after an input switches; how delays add up along a chain is covered in the article on propagation delay.
Don't care combinations
Sometimes a portion of the input combinations never arrives. The classic example is binary-coded decimal: four bits offer 16 values while digits stop at 10, so the combinations from 1010 to 1111 never occur. On the map such cells are marked X. You may treat each X as convenient: include it in a loop, count it as a one; leave it outside, count it as a zero. Picking the right X values often shrinks both the loops and the final circuit.
The limits of the method
Up to five variables the map stays convenient. At six it becomes an 8×8 table where adjacency between quadrants is impossible to see by eye, and the manual method loses to automation: the Quine — McCluskey algorithm formalizes the merging, and synthesis tools apply its heuristics to thousands of variables. When you write assign f = (a & b) | (a & c) | (b & c); in Verilog, the synthesizer performs the minimization for the specific chip; the maps are there to help you understand where its result comes from.
Why it matters in the game
The carry of a full adder (level 1.7) is precisely the three-judge voting: the carry appears when at least two of A, B, and the incoming carry equal 1. In SOP form the carry takes eight gates; after minimization, four: (A AND B) OR (A AND P) OR (B AND P), where P is the incoming carry.
The savings compound: the 8-bit adder of level 1.8 assembles eight full adders, and the carry path through all the places determines whether the circuit settles within one clock tick. Every gate saved along that path shortens the delay.
Test yourself
Why do the columns go in the order 00, 01, 11, 10 rather than 00, 01, 10, 11?
Gray code: neighboring columns differ in one bit, so any two adjacent cells can merge into a loop. In binary order the step 01 → 10 flips two bits at once.
What loop sizes are allowed?
1, 2, 4, 8, 16 cells — always a power of two. A three-cell loop matches no minterm.
Write the minimal form of the full adder carry.
(A AND B) OR (A AND P) OR (B AND P), where P is the incoming carry. It is the same voting function as in the previous article.
Summary
1. Adjacent minterms that differ in one variable merge, and the variable leaves the formula.
2. A Karnaugh map lays out combinations in Gray code so that cell adjacency shows the merge; the map edges are closed.
3. Loops take sizes that are powers of two; variables changing inside a loop are dropped.
4. Don't care cells (X) may be included in loops for extra savings.
5. The manual map works up to 5–6 variables; beyond that, automation does the minimization.
On levels 1.6–1.8 build the full adder and compare both versions of the carry: SOP and minimized. Both pass the tests, but the second contains half the gates. Next up is the Zhegalkin Polynomial, and minimal forms find their use in the multiplexer and the instruction decoder.