Karnaugh Maps

Introduction to Karnaugh Maps

A Karnaugh map (K-map) is a visual simplification tool:

• Arranges truth table entries in a grid
• Adjacent cells differ by exactly one variable
• Groups of adjacent 1s combine using adjacency rule
• Makes it easy to spot simplification patterns

Key insight: Physical adjacency on the K-map corresponds to logical adjacency (terms that can combine).

K-maps work well for 2-4 variables. Beyond 4, they become impractical.

Two-Variable K-maps

2-variable K-map layout:

        B=0   B=1
      ┌─────┬─────┐
A=0   │ $m_0$  │ $m_1$  │
      ├─────┼─────┤
A=1   │ $m_2$  │ $m_3$  │
      └─────┴─────┘

• 4 cells for 4 possible input combinations
• Adjacent cells (sharing an edge) differ by one variable
• $m_0$ and $m_1$ are adjacent (differ in B)
• $m_0$ and $m_2$ are adjacent (differ in A)
• $m_0$ and $m_3$ are NOT adjacent (differ in both A and B)

Three-Variable K-maps

3-variable K-map uses Gray code for column labels:

          BC
       00  01  11  10
     ┌────┬────┬────┬────┐
A=0  │ $m_0$ │ $m_1$ │ $m_3$ │ $m_2$ │
     ├────┼────┼────┼────┤
A=1  │ $m_4$ │ $m_5$ │ $m_7$ │ $m_6$ │
     └────┴────┴────┴────┘

Gray code (00, 01, 11, 10): adjacent columns differ by one bit.

Wraparound: The leftmost and rightmost columns are also adjacent!

(00 and 10 differ only in B)

Four-Variable K-maps

4-variable K-map - 16 cells with wraparound in both directions:

           CD
        00   01   11   10
      ┌────┬────┬────┬────┐
AB=00 │ $m_0$ │ $m_1$ │ $m_3$ │ $m_2$ │
      ├────┼────┼────┼────┤
AB=01 │ $m_4$ │ $m_5$ │ $m_7$ │ $m_6$ │
      ├────┼────┼────┼────┤
AB=11 │ $m_{12}$│ $m_{13}$│ $m_{15}$│ $m_{14}$│
      ├────┼────┼────┼────┤
AB=10 │ $m_8$ │ $m_9$ │ $m_{11}$│ $m_{10}$│
      └────┴────┴────┴────┘

Wraparound: Top$\leftrightarrow$Bottom AND Left$\leftrightarrow$Right Even the 4 corners are all mutually adjacent!

K-map Grouping Rules

Rules for valid K-map groups:

1. Power of 2: Groups must contain 1, 2, 4, 8, or 16 cells
2. Rectangle: Groups must form rectangles (including squares)
3. All 1s: Every cell in the group must contain a 1
4. Adjacent only: All cells must be adjacent (including wraparound)
5. Maximize size: Make groups as large as possible
6. Cover all 1s: Every 1 must be in at least one group
7. Overlap OK: Groups can share cells

Goal: Fewest groups of largest sizes $\to$ minimal expression.

Reading Expressions from K-maps

Converting a group to a product term:

1. Look at which variables are constant across the group
2. If variable is always 1 in the group $\to$ include it uncomplemented
3. If variable is always 0 in the group $\to$ include it complemented
4. If variable is both 0 and 1 in the group $\to$ omit it

Example (3-var K-map):

Group covers $m_0$, $m_4$ (column BC=00, both rows)

• A varies (0 and 1) $\to$ omit A
• B is always 0 $\to$ include $\neg$B
• C is always 0 $\to$ include $\neg$C
• Term: $\neg$B $\land$ $\neg$C

Prime Implicants

A prime implicant is a group that:

• Cannot be made larger (already maximal)
• Cannot be combined with another group

Finding prime implicants:

1. Start with each 1-cell
2. Expand to largest possible group containing that cell
3. A prime implicant is a maximal rectangular group of 1s

The minimal SOP expression uses only prime implicants. But not all prime implicants are needed - just enough to cover all 1s.

Essential Prime Implicants

An essential prime implicant (EPI) is a prime implicant that:

• Covers at least one 1-cell that NO other prime implicant covers
• Must be included in the minimal solution

Finding EPIs:

1. Identify all prime implicants
2. For each 1-cell, check how many prime implicants cover it
3. If a cell is covered by only ONE prime implicant $\to$ that PI is essential

After selecting all EPIs, check if all 1s are covered. If not, choose additional PIs.

K-map Practice

K-map simplification process:

1. Fill in K-map from truth table or expression
2. Identify all prime implicants (maximal groups)
3. Find essential prime implicants (cover unique 1s)
4. Add additional PIs if needed to cover remaining 1s
5. Write the simplified SOP expression

Remember: Make groups as large as possible, and use wraparound!

K-map from Expression

Building K-map from expression (not truth table):

Instead of building a full truth table first:

1. Identify each product term
2. Mark cells where that term is true
3. Repeat for all terms
4. Group and simplify

Example: A $\lor$ ($\neg$A $\land$ B)

• A is true for cells where A=1 (half the K-map)
• $\neg$A $\land$ B is true for cell where A=0, B=1
• Mark all those cells with 1

Multiple Valid Groupings

Multiple valid solutions:

Sometimes a K-map has several equally good groupings:

• Same number of terms
• Same number of literals
• Different but equivalent expressions

Example: A symmetric pattern might group horizontally OR vertically.

Key insight: All valid minimal solutions represent the same function!

Different groupings = different expressions = same truth table.

K-map Grouping Strategy

Optimal grouping strategy:

1. Start with largest possible groups (8, then 4, then 2, then 1)
2. Find essential prime implicants first (cover unique 1s)
3. Use wraparound - edges connect to opposite edges
4. Overlap is OK - groups can share cells
5. Every 1 must be covered - at least once

Common mistake: Starting with small groups, missing larger ones!

Reading SOP and POS from K-maps

Two ways to read a K-map:

SOP (Sum of Products) - group the 1s:

• Each group of 1s $\to$ one product term
• OR all terms together
• Variables: negated if that row/column is 0

POS (Product of Sums) - group the 0s:

• Each group of 0s $\to$ one sum term
• AND all terms together
• Variables: negated if that row/column is 1

Choose based on which has fewer groups!

4-Variable K-map Challenge

4-variable K-map structure:

      CD
      00  01  11  10
   ┌────────────────┐
00 │  0   1   3   2 │
AB │                │
01 │  4   5   7   6 │
   │                │
11 │ 12  13  15  14 │
   │                │
10 │  8   9  11  10 │
   └────────────────┘

Key patterns:

• All four corners are adjacent (wrap both ways!)
• Groups of 8 $\to$ 1 literal
• Groups of 4 $\to$ 2 literals
• Groups of 2 $\to$ 3 literals

K-map vs Algebraic Simplification

Comparing methods:

Use K-maps for 2-4 variables. Use algebra for more variables or when K-map isn't practical.