Karnaugh Maps

Overview

A Karnaugh Map (K-map) is a visual method for minimizing Boolean expressions. It arranges truth-table rows so that adjacent cells differ by exactly one variable (Gray code ordering), making grouping of 1s easy to spot.

Cell Ordering (Gray Code)

Adjacent columns/rows differ by only one bit flip.

2-Variable K-map

     B=0   B=1
A=0 | m0  | m1 |
A=1 | m2  | m3 |

3-Variable K-map

       BC=00  BC=01  BC=11  BC=10
  A=0 |  m0  |  m1  |  m3  |  m2 |
  A=1 |  m4  |  m5  |  m7  |  m6 |

Note the 11 → 10 swap (not binary order) to maintain adjacency.

4-Variable K-map

         CD=00  CD=01  CD=11  CD=10
  AB=00 |  m0  |  m1  |  m3  |  m2 |
  AB=01 |  m4  |  m5  |  m7  |  m6 |
  AB=11 | m12  | m13  | m15  | m14 |
  AB=10 |  m8  |  m9  | m11  | m10 |

Grouping Rules

Rules for valid groups: 1. Groups must contain 2ᵏ cells (1, 2, 4, 8, …). 2. All cells in a group must contain 1 (or X for don't-cares). 3. The group must be rectangular (wrapping is allowed). 4. Wrap-around is valid: top/bottom edges and left/right edges are adjacent. 5. Groups may overlap. 6. Use the largest possible groups (fewer literals = simpler expression). 7. Every 1 must be covered by at least one group.

Reading a Group → Term

For each group, identify which variables are constant across all cells: - Constant 0 → variable appears complemented (A′) - Constant 1 → variable appears true (A) - Variable changes → eliminated from the term

Worked Example: 4-Variable SOP

F(A,B,C,D) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 10, 14)

         CD=00  CD=01  CD=11  CD=10
  AB=00 |  1   |  1   |  0   |  1  |
  AB=01 |  1   |  1   |  0   |  1  |
  AB=11 |  0   |  0   |  0   |  1  |
  AB=10 |  1   |  1   |  0   |  1  |

Each of the three is an essential prime implicant: - CD′ is the only PI covering m14. - A′C′ is the only PI covering m5. - B′C′ is the only PI covering m9.

Together they cover every 1, so the cover is complete.

Minimal SOP: F = A′C′ + B′C′ + CD′ (3 terms, 6 literals)

The wrap-around quads m0,m2,m8,m10 (B′D′) and m0,m2,m4,m6 (A′D′) are also prime implicants, but they cover nothing the essentials miss, so a minimal cover excludes them.

Simplified Example: 3-Variable

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

       BC=00  BC=01  BC=11  BC=10
  A=0 |  1   |  1   |  0   |  1  |
  A=1 |  1   |  1   |  0   |  0  |

Both are essential: B′ is the only prime implicant covering m1, m4, m5; A′C′ is the only one covering m2 (overlap at m0 is fine).

Minimal SOP: F = B′ + A′C′

Don't-Care Conditions (X)

Don't-care cells (marked X) represent input combinations that either: - Never occur (e.g., invalid BCD states 1010–1111), or - The output doesn't matter.

Use don't-cares freely to extend groups (treat as 1). They never need to be covered.

       BC=00  BC=01  BC=11  BC=10
  A=0 |  1   |  0   |  X   |  1  |
  A=1 |  0   |  1   |  X   |  0  |

The X's can be included in any group that makes it larger.

Prime Implicants and Essential Prime Implicants

Minimization procedure: 1. Find all prime implicants. 2. Identify essential prime implicants (each one must be included). 3. Cover remaining 1s with as few non-essential PIs as possible (Petrick's method for hard cases).

POS Minimization from K-map

To find minimal Product of Sums: 1. Group the 0s instead of 1s. 2. Each group → one maxterm (sum term). 3. Variables: constant 0 → uncomplemented, constant 1 → complemented. 4. Result is ANDed together.

K-map Wrap-Around Adjacency

4-variable — these cells ARE adjacent (wrap):
- m0, m2, m8, m10  (corners form a valid group of 4)
- m0 and m8        (top and bottom of column 00)
- m0 and m2        (left and right of row AB=00)

Always check corners and edges — beginners often miss wrap-around groups.

5-Variable K-map

Use two 4-variable maps (one for A=0, one for A=1). Cells in the same position on both maps are adjacent through the A variable.

Common Mistakes