Karnaugh Maps and Boolean Simplification

The gates lesson ended on a big claim: a truth table is a complete specification, and any circuit with the same table is interchangeable. That cuts both ways: many different gate networks satisfy one table, and they are not equal in cost. Every gate you describe becomes physical silicon: area, power, delay. This lesson gives you the mechanical route from any truth table to gates, and then the tool, the Karnaugh map, that finds a near-minimal version by hand.

From Table to Gates, the Brute-Force Way

A PC cooling controller has three temperature flags (cpu, chassis, psu), and the thermal team hands you the fan requirement as a table:

The brute-force recipe, called sum of products, works for any table. For each row where the output is 1, write an AND term that matches exactly that row (inverting the inputs that are 0). Then OR all the terms together:

fan <= ((not cpu) and chassis and psu)
      or (cpu and chassis and (not psu))
      or (cpu and chassis and psu);

Correct by construction, and wasteful: three 3-input ANDs, two inverters, a 3-input OR, for what turns out to be a two-gate function.

The Karnaugh Map

A Karnaugh map is the same truth table folded into a grid, with one deliberate trick. The row and column labels follow Gray order (00, 01, 11, 10), so any two neighboring cells differ in exactly one bit. Note the order: 11 before 10, not the counting order from the binary lesson. For three variables, one variable picks the row and the other two pick the column. Plotting the fan table:

Adjacency is the whole point. If two neighboring cells are both 1, the one bit that differs between them cannot matter there, so it can vanish from the expression.

Drawing Groups

Circle rectangles of 1s whose width and height are powers of two (1, 2, 4 cells...). Groups may overlap, and the map wraps: the left and right columns are neighbors, as are top and bottom rows. Bigger groups are better: each doubling removes one variable from the term.

The fan map has two groups of two:

• The 11 column pair: both cells of column chassis·psu = 11. Between them only cpu changes (0 → 1), so cpu drops out. The term is what stays fixed: chassis and psu.
• The bottom-row pair, columns 11 and 10: here cpu = 1 and chassis = 1 stay fixed while psu changes, so psu drops out: cpu and chassis.

Every 1 is covered (the 11-column overlap is fine), so the minimal expression ORs the two terms:

fan <= (cpu and chassis) or (chassis and psu);

Two 2-input ANDs and one OR, down from six gates, and it even reads sensibly: the chassis sensor must corroborate either hot neighbor.

Four Variables

With four inputs the map is a 4×4 grid: two bits pick the row, two pick the column, both axes in Gray order. Plotting a 4-bit value v (bits v3 v2 v1 v0), here is where each decimal value lands; note the scrambled-looking order on both axes:

Grouping works exactly as before, with more room. One worked grouping: suppose the output is 1 exactly in the four center cells (values 5, 7, 13, 15). Those cells span rows 01 and 11 (where v2 = 1 and v3 changes) and columns 01 and 11 (where v0 = 1 and v1 changes). Both changing variables drop out, leaving a single two-literal term: v2 and v0. A group of four collapsed sixteen rows of table into one AND gate.

In the Example

The example panel on the right (Raw vs. Minimized) contains both fan controllers from this lesson: fan_raw, the three-term sum of products, and fan_min, the two-group K-map result. One testbench drives both through all eight input rows. The waveform shows raw_fan and min_fan as identical traces on every step: same truth table, interchangeable circuits. Then open the Netlist tab and flip between the fan_raw and fan_min file tabs: the raw version's gate network is visibly larger. The simulator can't tell them apart; the silicon can.

Key Takeaways

• Sum of products turns any truth table into gates mechanically: one AND term per 1-row, ORed together.
• A K-map's Gray-ordered axes make adjacent cells differ by one bit, so power-of-two groups of 1s drop variables. Each group reads off as one term of what stays fixed.
• Minimization changes the gate count, never the behavior; the truth table stays identical.