Karnaugh Maps

Motivation

Boolean algebra can simplify expressions, but it is not systematic: you must spot the right factoring opportunities. Karnaugh maps (K-maps) provide a visual method for simplification that is systematic and reliable for up to about 5 variables. Beyond that, tabular methods like Quine-McCluskey are preferred.

A K-map is a two-dimensional array where each cell corresponds to one minterm (one row of the truth table). The layout is carefully arranged so that adjacent cells differ in exactly one variable. This adjacency makes it possible to combine terms visually.

K-Map Layout: Gray Code Ordering

The axes of a K-map use Gray code ordering, not binary counting order. In Gray code, consecutive numbers differ in exactly one bit:

Decimal	Binary	Gray code
0	00	00
1	01	01
2	10	11
3	11	10

This ordering is crucial because it ensures that physically adjacent cells on the map are logically adjacent (differ by one variable). The map also wraps around: the leftmost and rightmost cells in a row are adjacent (differ by one variable), and the topmost and bottommost cells in a column are adjacent.

2-Variable K-Map

For variables $x$ and $y$:

$$\begin{array}{c|cc} x \setminus y & 0 & 1 \\ \hline 0 & m_0 & m_1 \\ 1 & m_2 & m_3 \end{array}$$

Cells: $m_0 = \bar{x}\bar{y}$, $m_1 = \bar{x}y$, $m_2 = x\bar{y}$, $m_3 = xy$.

3-Variable K-Map

For variables $x$, $y$, $z$, with $x$ on the vertical axis and $yz$ on the horizontal:

$$\begin{array}{c|cccc} x \setminus yz & 00 & 01 & 11 & 10 \\ \hline 0 & m_0 & m_1 & m_3 & m_2 \\ 1 & m_4 & m_5 & m_7 & m_6 \end{array}$$

Note the Gray-code ordering of the $yz$ axis: 00, 01, 11, 10 (not 00, 01, 10, 11). This ordering is what makes cells $m_3$ (011) and $m_2$ (010) adjacent to each other in the grid.

4-Variable K-Map

For variables $a$, $b$, $c$, $d$, with $ab$ on the vertical axis and $cd$ on the horizontal:

$$\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & m_0 & m_1 & m_3 & m_2 \\ 01 & m_4 & m_5 & m_7 & m_6 \\ 11 & m_{12} & m_{13} & m_{15} & m_{14} \\ 10 & m_8 & m_9 & m_{11} & m_{10} \end{array}$$

Both axes use Gray code. Adjacent cells always differ in exactly one variable, including edges and corners.

Mapping Onto a K-Map

From Truth Table

Place the output value (0 or 1) into the cell corresponding to each input combination. For the function $f(x,y,z) = x + y \cdot z$:

$$\begin{array}{c|cccc} x \setminus yz & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{array}$$

Row $x=0$, column $yz=11$ (cell $m_3 = \bar{x}yz$) contains 1; row $x=1$, all columns contain 1.

From Boolean Expression

A product term of $k$ literals covers $2^{n-k}$ cells. For example, in a 4-variable map:

• A 1-variable term (e.g., $b$) covers 8 cells (half the map).
• A 2-variable term (e.g., $a \cdot \bar{d}$) covers 4 cells.
• A 3-variable term (e.g., $\bar{a} \cdot b \cdot c$) covers 2 cells.
• A 4-variable term (minterm) covers exactly 1 cell.

Place a 1 in every cell where the term is TRUE. For $f = \bar{a} \cdot b + b \cdot \bar{c} \cdot d$: first mark all cells where $a=0$ AND $b=1$ (rows 01 on K-map: that’s 4 cells), then mark all cells where $b=1$ AND $c=0$ AND $d=1$ (those are cells in row 01 or 11 where $cd=01$, total 2 cells). Overlapping cells are marked 1 only once.

Example: plot $f = \bar{a} \cdot b + b \cdot \bar{c}d$ on a 4-variable K-map.

$$\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & & & & \\ 01 & 1 & 1^+ & 1 & 1 \\ 11 & & 1 & & \\ 10 & & & & \end{array}$$

The cells marked $1^+$ are covered by both terms. Row $ab=01$ (where $a=0$, $b=1$) gets 1s from the first term $\bar{a} \cdot b$ in all four columns. The second term $b \cdot \bar{c}d$ puts a 1 only in cells where $b=1$, $c=0$, $d=1$: this is column $cd=01$ in rows where $b=1$ (rows 01 and 11).

From DNF/Σ Notation

Simply place a 1 in every cell whose index is listed. $f = \Sigma(1, 2, 3, 5, 7, 10, 11)$ on a 4-variable map puts 1s in those cells.

Grouping Rules

To simplify an expression using a K-map, we group adjacent 1s according to these rules:

1. Groups must be rectangular (1×1, 1×2, 2×1, 1×4, 2×2, 2×4, 4×2, 4×4).
2. Group size must be a power of 2: 1, 2, 4, 8, 16.
3. Groups must be as large as possible (to eliminate as many variables as possible).
4. Every 1 must be covered by at least one group (all minterms must be accounted for).
5. Cells can be in multiple groups (to enable larger groups elsewhere).
6. Groups may wrap around edges and corners (the map is topologically a torus).

Why Groups of Powers of 2?

A group of $2^k$ cells eliminates $k$ variables. Consider a group of two adjacent cells; they differ in exactly one variable, say $x$. One cell has $\bar{x}$, the other has $x$; all other variables are identical. The OR of these two minterms is $\bar{x} \cdot (\text{common part}) + x \cdot (\text{common part}) = (\bar{x} + x) \cdot (\text{common part}) = \text{common part}$. The variable $x$ is eliminated. Similarly, a group of 4 eliminates 2 variables, a group of 8 eliminates 3 variables.

Reading the Simplified Expression

For each group, write down the product of the literals that are constant across the entire group:

• If a variable is 0 everywhere in the group, it appears complemented.
• If a variable is 1 everywhere in the group, it appears uncomplemented.
• If a variable changes (both 0 and 1 appear in the group), it is eliminated from that term.

The final simplified SOP expression is the OR of all group terms.

Worked Example: 3-Variable Simplification

Simplify $f = \Sigma(0, 1, 2, 3, 7)$ (function from the truth tables note: 3 variables $x$, $y$, $z$).

K-map:

$$\begin{array}{c|cccc} x \setminus yz & 00 & 01 & 11 & 10 \\ \hline 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{array}$$

Grouping:

• The top row ($x=0$) has four 1s: this is a group of 4 covering $m_0, m_1, m_3, m_2$. In this group, $x = 0$ everywhere (so $\bar{x}$ is included), but $y$ and $z$ both vary (00, 01, 11, 10), so they are eliminated. Term: $\bar{x}$.
• The remaining 1 at $m_7$ (cell $x=1, yz=11$) is isolated. But note: we could instead group $m_7$ with $m_3$ (the cell directly above it). Let us use grouping (a): top row group of 4 gives $\bar{x}$; remaining $m_7$ groups with $m_3$ as a vertical group of 2 (wrap not needed here since they’re adjacent vertically). In this group of 2 ($m_3$ and $m_7$), $x$ varies (0 and 1), $y$ is always 1, $z$ is always 1. Term: $y \cdot z$.

Result: $f = \bar{x} + y \cdot z$. This matches the previous algebraic simplification.

(Note: $m_3$ belongs to both groups; this is allowed and necessary to get the largest possible group for $m_7$.)

Worked Example: 4-Variable Simplification

Simplify $f = \bar{a} \cdot \bar{b} \cdot d + \bar{b} \cdot c \cdot d + \bar{a} \cdot \bar{b} \cdot \bar{c} \cdot \bar{d} + c \cdot \bar{d}$.

First, plot on the 4-variable K-map:

Term $\bar{a} \cdot \bar{b} \cdot d$: cells where $a=0$, $b=0$, $d=1$: these are row $ab=00$, columns where $d=1$ ($cd=01$ and $cd=11$). Cells: $m_1$ (0001) and $m_3$ (0011).

Term $\bar{b} \cdot c \cdot d$: cells where $b=0$, $c=1$, $d=1$: rows where $b=0$ (rows 00 and 10), column $cd=11$. Cells: $m_3$ (0011) and $m_{11}$ (1011).

Term $\bar{a} \cdot \bar{b} \cdot \bar{c} \cdot \bar{d}$: exactly cell $m_0$ (0000).

Term $c \cdot \bar{d}$: cells where $c=1$ and $d=0$: column $cd=10$. All 4 rows: $m_2$, $m_6$, $m_{14}$, $m_{10}$.

K-map:

$$\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & 1 & 1 & 1 & 1 \\ 01 & & & & 1 \\ 11 & & & & 1 \\ 10 & & & 1 & 1 \end{array}$$

Grouping:

• Group 1: all four cells in column $cd=10$ ($m_2, m_6, m_{14}, m_{10}$). In this group, $c=1$, $d=0$ are constant; $a$ and $b$ vary. Term: $c \cdot \bar{d}$.
• Group 2: top row $ab=00$, first two cells ($m_0, m_1$) form a group of 2: $a=0$, $b=0$, $c=0$ constant; $d$ varies. Also $m_1$ and $m_3$ can group vertically. Looking for the largest groups:
  • $m_0$ and $m_1$ (group of 2, horizontal): $a=0, b=0, c=0$ constant; $d$ varies. Term: $\bar{a} \cdot \bar{b} \cdot \bar{c}$.
  • $m_1$ and $m_3$: group of 2 (vertical). Constant: $a=0, b=0, d=1$; $c$ varies. Term: $\bar{a} \cdot \bar{b} \cdot d$.
  • $m_3$ and $m_{11}$: rows 00 and 10 are adjacent by wrap-around in Gray code. Group of 2: constant $b=0, c=1, d=1$; $a$ varies. Term: $\bar{b} \cdot c \cdot d$.

But now we have a 1 at $m_1$ that is covered by two groups (with $m_0$ and with $m_3$). The minimal cover uses the minimal number of prime implicants that collectively cover all 1s.

Looking at the map holistically, the optimal grouping is:

• Group A: $c \cdot \bar{d}$ (covers $m_2, m_6, m_{14}, m_{10}$)
• Group B: $\bar{a} \cdot \bar{b}$ (covers $m_0, m_1, m_2, m_3$: the entire top row $ab=00$). In this group $a=0, b=0$; $c$ and $d$ vary.
• Group C: Remaining 1 at $m_{11}$ is already covered if we use group B… no, $m_{11}$ is in row $ab=10$, not 00. So $m_{11}$ needs a group. It groups with $m_3$ (vertical, rows 00 and 10 wrap): term $\bar{b} \cdot c \cdot d$.

But $m_3$ is covered by both B and C, which is fine.

Final: $f = c \cdot \bar{d} + \bar{a} \cdot \bar{b} + \bar{b} \cdot c \cdot d$.

POS Simplification: Grouping Zeros

To obtain a Product of Sums (POS) simplified expression, we group the zeros on the K-map. Grouping zeros follows the same rules; each group of zeros produces a sum term (OR) for the complement of the function. Then De Morgan’s theorem gives the POS expression.

Procedure

1. Group the zeros on the K-map (treating zeros exactly like ones were treated for SOP).
2. Read off the SOP expression for $\bar{f}$: each group of zeros yields a product term for $\bar{f}$.
3. Apply De Morgan and complement to convert $\bar{f}$ to $f$ in POS form.

POS Example

Simplify $f = \Sigma(0, 1, 2, 5, 8, 9, 10)$ into POS form (4 variables).

K-map for ones:

$$\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & 1 & 1 & 0 & 1 \\ 01 & 0 & 1 & 0 & 0 \\ 11 & 0 & 0 & 0 & 0 \\ 10 & 1 & 1 & 0 & 1 \end{array}$$

Zeros are at: $m_3, m_4, m_6, m_7, m_{11}, m_{12}, m_{13}, m_{14}, m_{15}$.

Grouping zeros (for $\bar{f}$):

• Group Z1: columns $cd=11$ (all four rows: $m_3, m_7, m_{11}, m_{15}$) — a group of 4. Constant: $c=1, d=1$; $a$, $b$ vary. Term: $c \cdot d$.
• Group Z2: row $ab=11$, columns $cd=00$ and $cd=01$ ($m_{12}, m_{13}$) — a group of 2. Constant: $a=1, b=1, c=0$; $d$ varies. Term: $a \cdot b \cdot \bar{c}$.
• Group Z3: row $ab=01$, columns $cd=00$ ($m_4$) — pairs with row $ab=11$, column $cd=00$ ($m_{12}$) as a vertical group of 2. Constant: $b=1, c=0, d=0$; $a$ varies. Term: $b \cdot \bar{c} \cdot \bar{d}$.

Z1 covers $m_3, m_7, m_{11}, m_{15}$. Z2 covers $m_{12}, m_{13}$. Z3 covers $m_4, m_{12}$ (redundant for $m_{12}$). Remaining: $m_6$ (0110) and $m_{14}$ (1110) — both have $c=1, d=0$, so they are NOT covered by Z1 ($d=1$ required). Add:

• Group Z4: column $cd=10$, rows 01 and 11 ($m_6, m_{14}$) — a group of 2. Constant: $c=1, d=0$; $a$, $b$ vary. Term: $c \cdot \bar{d}$.

All zeros now covered. Simplifying: $c \cdot d + c \cdot \bar{d} = c$, so Z1 and Z4 combine to just $c$.

$\bar{f} = c + a \cdot b \cdot \bar{c} + b \cdot \bar{c} \cdot \bar{d}$

Apply De Morgan to get $f$ in POS form:

$f = \bar{c} \cdot (\bar{a} + \bar{b} + c) \cdot (\bar{b} + c + d)$

This is the minimal POS. The SOP equivalent $f = \bar{c} \cdot \bar{d} + \bar{a} \cdot \bar{b} + \bar{b} \cdot \bar{c}$ (from grouping ones) has a similar cost, illustrating that the choice between SOP and POS depends on the specific function.

The general rule: if the function has more 0s than 1s, POS grouping of zeros can give a simpler expression than SOP grouping of ones.

Summary: K-Map Simplification Steps

1. Draw the K-map with Gray code axes for the given number of variables.
2. Fill in 1s (or 0s for POS) from the truth table, DNF notation, or Boolean expression.
3. Group 1s (for SOP) or 0s (for POS) into maximal rectangular groups of size $2^k$.
4. Write each group as a product term (for SOP) containing only the variables that are constant.
5. OR together all group terms for the simplified SOP (or AND together all group terms, after De Morgan complementation, for POS).
6. Check that every 1 (or 0) is covered; every essential group should be included; non-essential groups may be dropped if all their cells are covered by other groups.

The K-map method is visual and reliable up to about 5 variables. For 6 or more, the map becomes unwieldy and tabular methods (see Quine-McCluskey) are preferred.