📜 Lecture 6: Karnaugh Maps (K-Maps)

This lecture introduces the Karnaugh Map (K-map), a graphical method for simplifying Boolean expressions, as an easier alternative to Boolean algebra.

Key Concepts

• Problem: Simplifying expressions using Boolean algebra (like in Lecture 5) is difficult, non-systematic, and gets harder with more variables.
• Solution: The Karnaugh Map (K-map), which provides a visual, step-by-step method for grouping terms.
• K-Map Structure (3-Variable):
  • An 8-cell grid, representing the 8 minterms.
  • Rows are labeled for one variable (e.g., A, values 0 and 1).
  • Columns are labeled for the other variables (e.g., BC).
  • Crucial Rule: The column order must be in Gray code (00, 01, 11, 10). This ensures that only one bit changes between any two adjacent cells.
  • This ordering makes adjacent cells "logically adjacent" (differ by one complement).
  • The cells map to minterms: | | 00 (B'C') | 01 (B'C) | 11 (BC) | 10 (BC') | |---|---|---|---|---| | 0 (A') | m0 | m1 | m3 | m2 | | 1 (A) | m4 | m5 | m7 | m6 |
• Adjacency: Cells are adjacent horizontally, vertically, and by wrapping around (e.g., m0 is adjacent to m2, and m4 is adjacent to m6).

K-Map Simplification Steps (SOP)

1. Draw the Map: Draw the K-map for the number of variables (e.g., 3-variable map for A, B, C).
2. Fill the Map: Place a 1 in the cell corresponding to each minterm in the function's On-Set (e.g., for f = Σm(2, 3, 5, 7)). Place 0s in all other cells.
3. Group the 1s: Draw loops (groups) around adjacent 1s.
   • Groups must be as large as possible.
   • The number of 1s in a group must be a power of 2 (1, 2, 4, 8, ...).
   • You must use the minimum number of groups to cover all the 1s.
   • Groups can overlap and wrap around the edges.
4. Read the Groups: For each group, write down the product term that represents it.
   • Identify the variable(s) that do not change within that group.
   • If the variable is 0 in the group, write it as complemented (e.g., A').
   • If the variable is 1, write it as uncomplemented (e.g., A).
   • If a variable changes (is 0 and 1) within the group, it is eliminated.
5. Sum the Terms: The final simplified expression is the sum (OR) of all the group terms.

• Example (Prime Detector): f(A,B,C) = Σm(2, 3, 5, 7)

  • Fill: Place 1s at cells 2, 3, 5, 7.
  • Group 1: Loop m3 and m7.
    • A changes (0 -> 1) -> Eliminated.
    • B stays 1.
    • C stays 1.
    • Term = BC
  • Group 2: Loop m2 and m3.
    • A stays 0 -> A'.
    • B stays 1 -> B.
    • C changes (0 -> 1) -> Eliminated.
    • Term = A'B
  • Group 3: Loop m5 and m7.
    • A stays 1 -> A.
    • B changes (0 -> 1) -> Eliminated.
    • C stays 1 -> C.
    • Term = AC
  • Issue: Grouping (m2, m3), (m5, m7), (m3, m7) gives f = A'B + AC + BC.
  • Redundancy: The BC group (m3, m7) is redundant because its 1s are already covered by the other two groups.
  • Better Grouping: Group (m2, m3) and (m5, m7).
  • Final Result: f = A'B + AC. This matches the result from Boolean algebra (Lecture 5).

• Grouping Notes:

  • A group of 4 (e.g., m4, m5, m7, m6) simplifies to a single variable (A).
  • A group of 4 (e.g., m0, m1, m4, m5) simplifies to B'.
  • The goal is largest groups, fewest groups.