CE2704 · Digital Logic Design
Theme 3 · Making logic smaller

Karnaugh maps

A visual puzzle that turns a long truth table into the shortest possible equation — no algebra, just fill the grid and circle the groups.

Built from first principles. (Maurice Karnaugh, 1953.)

Before you start

What you need first

  • Canonical forms — minterms and the SOP form from a truth table.
  • Truth tables — \(2^n\) rows in order.

What you'll be able to do

  • Lay out a 3- and 4-variable K-map in Gray-code order.
  • Group the 1s by the rules and read off each term.
  • Use wrap-around to find the biggest groups.

Long equation → short equation

A K-map is a grid that gives you the shortest SOP from a truth table. Same function, two ways:

Straight from the table: F = A′B′C′ + A′B′C + A′BC′ + A′BC + AB′C′ + AB′C — 6 terms, many gates.
After the K-map: F = A′ + B′ — 2 terms, one gate. Same circuit, a fraction of the cost.

The 3-variable grid (8 cells)

A \ BC00011110
0m₀m₁m₃m₂
1m₄m₅m₇m₆
  • 8 cells = 8 truth-table rows.
  • Column order is 00 → 01 → 11 → 10 (Gray code), not plain counting.
  • So every neighbouring cell differs by exactly one variable — that's what lets a group cancel a variable.
  • Left and right edges are neighbours too: the map wraps.
📐 Worked example

Simplify F = Σm(0,1,2,3,4,5)

Fill the grid (1 in every listed cell), then make the largest power-of-two groups covering all the 1s:

A \ BC00011110
01111
11100

Blue = top row (A = 0)  ·  Green = left two columns (B = 0)

Blue group — A = 0 in all cells (kept), B and C vary (dropped) → term A′.
Green group — B = 0 in both columns (kept), A and C vary (dropped) → term B′.
$$ F = A' + B' $$
Read each group by asking: which variable stays the same across all its cells? Keep that; drop the ones that change.

The grouping rules — every K-map

  1. Groups are rectangular (horizontal/vertical, no diagonals).
  2. Group size is a power of 2: 1, 2, 4, 8, 16.
  3. Bigger is better — a larger group means fewer literals. Find the largest first.
  4. Every 1 must be in at least one group; groups may overlap.
  5. The map wraps — left↔right and top↔bottom edges are adjacent.
  6. Use the fewest groups that cover all the 1s.
A group of \(2^k\) cells in an n-variable map leaves n − k literals. Group of 8 in a 4-var map → 1 literal; a full map → F = 1.

The 4-variable grid (16 cells)

Both axes use Gray code, and both pairs of edges wrap (top↔bottom and left↔right) — so even the four corners are one group.

📐 Worked example

Simplify F = Σm(0,1,2,3,8,9,10,11)

AB \ CD00011110
001111
010000
110000
101111

Blue = top row (AB = 00) + bottom row (AB = 10), adjacent by wrap-around → one group of 8

Across all 8 cells: A varies, C varies, D varies, but B = 0 throughout.

$$ F = B' $$
Eight minterms — 32 literals in canonical SOP — collapse to a single literal. Wrap-around found the group pure algebra would struggle to see.

✏️ Try it yourself

(a) Why is the column order 00,01,11,10 and not 00,01,10,11? (b) A group of 4 in a 3-variable map → how many literals? (c) In a 4-var map the four corners are all 1, rest 0 — what is F?

(a) Gray code → neighbouring cells differ by exactly one variable; plain counting (01→10) changes two bits at once. (b) 3 − 2 = 1 literal. (c) the corners wrap into one group of 4 sharing B = 0 and D = 0 → F = B′·D′.

Recap — the whole topic on one screen

StepDo this
Lay outGray-code axes (00,01,11,10); 8 or 16 cells
Fillcopy each F value into its cell
Grouplargest power-of-2 rectangles of 1s; use wrap-around
Readper group, keep the variable that stays, drop the rest; OR the terms

Next topic

Don't-care conditions

Some input combinations can never happen. Marking them as "don't-care" lets your K-map groups grow even bigger — often shrinking the circuit dramatically.

→ Don't-care conditions