Module 34 min

Karnaugh Maps (K-Maps)

Why Adjacent Cells Differ by Only One Variable (Gray Code)

Pro Tip

What Is a K-Map? — A Karnaugh Map is a visual method for simplifying Boolean expressions. Instead of applying algebra laws step-by-step, you lay the truth table out in a 2D grid where adjacent cells differ by only one variable - then group 1s to extract minimal terms. Invented by Maurice Karnaugh in 1953, still used in logic design and VLSI synthesis today.

Why Adjacent Cells Differ by Only One Variable (Gray Code)

K-maps use Gray Code ordering (00, 01, 11, 10) - NOT binary order - so that adjacent cells differ by exactly one variable. When two adjacent cells are both 1, they can be combined to eliminate one variable.

The Simplification Rule

If AB + AB' appear together (same for all other variables) → factor out A → A(B+B') = A·1 = A

Grouping Rules

Group Size	Variables Eliminated	Example
1 cell	0 variables eliminated	Minterm stays as is - 3-variable product term
2 cells (pair)	1 variable eliminated	4 minterms → 2-variable product term
4 cells (quad)	2 variables eliminated	1-variable product term
8 cells (octet)	3 variables eliminated	Single literal or constant 1
16 cells	All eliminated	Output is always 1 (tautology)

Pro Tip

K-Map Rules - Never Violate These — 1. Groups must be rectangular and sizes must be powers of 2 (1, 2, 4, 8, 16). 2. Groups wrap around edges - the top row is adjacent to the bottom row, left column to right column. 3. Always make groups as large as possible. 4. Use the minimum number of groups to cover all 1s. 5. Cells with X (don't care) can be included in groups if it makes them larger, but need not be covered.

3-Variable K-Map - Step by Step Example

Minimize: F(A,B,C) = Σm(0,1,2,4,5)

3-Variable K-Map Layout

code


        BC →   00    01    11    10
        A=0  [ 1 ]  [ 1 ]  [ 0 ]  [ 1 ]   ← minterms 0,1,3,2
        A=1  [ 1 ]  [ 1 ]  [ 0 ]  [ 0 ]   ← minterms 4,5,7,6

        Group 1 (quad): m(0,1,4,5) → A can be 0 or 1, B=0, C can be 0 or 1 → B'
        Group 2 (pair): m(0,2) → A=0, B can vary, C=0 → A'C'

        F = B' + A'C'  (minimized from 5 minterms)

4-Variable K-Map Layout

4-Variable K-Map (AB vs CD)

code


      CD →   00    01    11    10
 AB=00  [  0  ]  [  1  ]  [  1  ]  [  0  ]
 AB=01  [  0  ]  [  1  ]  [  1  ]  [  0  ]
 AB=11  [  1  ]  [  1  ]  [  1  ]  [  1  ]
 AB=10  [  1  ]  [  1  ]  [  0  ]  [  0  ]

 Remember: wrap-around applies on all 4 edges.

Don't Care Conditions (X)

Some input combinations may never occur in practice (e.g., BCD codes 1010–1111 are invalid). These are marked as don't cares (X) in the truth table. In K-maps, you can treat X as 1 or 0 - choose whichever makes your groups larger, giving a simpler expression.

Pro Tip

Don't Cares - Key Rule — Include a don't care in a group only if it allows you to form a larger group. Never form a group consisting only of don't cares - you must always have at least one true 1 in each group.