K-Map Simplification Process
---
K-Map Grid Layouts
2-Variable K-Map (4 cells):
| AB | 0 | 1 |
|---|---|---|
| 0 | m₀ | m₁ |
| 1 | m₂ | m₃ |
3-Variable K-Map (8 cells) — Gray Code column order (00,01,11,10):
| A BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | m₀ | m₁ | m₃ | m₂ |
| 1 | m₄ | m₅ | m₇ | m₆ |
4-Variable K-Map (16 cells) — Gray Code for both axes:
| AB CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | m₀ | m₁ | m₃ | m₂ |
| 01 | m₄ | m₅ | m₇ | m₆ |
| 11 | m₁₂ | m₁₃ | m₁₅ | m₁₄ |
| 10 | m₈ | m₉ | m₁₁ | m₁₀ |
Why Gray Code? Adjacent cells differ by exactly 1 bit, ensuring logically adjacent minterms are physically adjacent in the K-map.
---
7 Rules for K-Map Grouping
- Only powers of 2: Groups must contain 1, 2, 4, 8, or 16 cells
- Only 1s and X (don't cares): Never group 0s
- Rectangular or square: Groups must be rectangular/square (wrapping allowed)
- Largest groups first: Maximize group size to maximize simplification
- Overlapping allowed: A cell can belong to multiple groups
- Wrap-around: Top row wraps to bottom; left column wraps to right
- Use don't cares to enlarge groups: X cells may be treated as 1
---
Worked SOP Example: F(A,B,C,D) = Σ(0,1,2,5,8,9,10)
Fill K-map with 1s at minterms 0,1,2,5,8,9,10:
| AB CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 0 | 1 |
| 01 | 0 | 1 | 0 | 0 |
| 11 | 0 | 0 | 0 | 0 |
| 10 | 1 | 1 | 0 | 1 |
Group 1 (orange): m₀,m₁,m₈,m₉ — A'C'+A'C (wraps top↔bottom, CD=00,01) → B'D' ... actually: cells (00,00),(00,01),(10,00),(10,01) = B=0 across both A values, D varies but C=0 → B'C'
Group 2 (green): m₀,m₂,m₈,m₁₀ — cells at CD=00,10 in rows AB=00,10 → B'D'
Group 3 (blue): m₁,m₅ — A=0,C=0,D=1 → A'CD' ... wait, m₁=(0000+1)=A'B'C'D, m₅=A'BC'D → A'C'D
Simplified result: F = B'C' + B'D' + A'C'D
---
Don't Care Conditions
A don't care (X) occurs when:
- The input combination is physically impossible (e.g., BCD code: 1010–1111 never occur)
- The output for that input is irrelevant (circuit never uses it)
Strategy: Use X cells as 1s if they help form larger groups; use as 0s otherwise. Goal: maximize group sizes.
---
Study Deep: Prime Implicants and Essential Prime Implicants
A Prime Implicant (PI) is the largest possible group that cannot be further enlarged.
An Essential Prime Implicant (EPI) is a PI that is the only PI covering some minterm. EPIs must be included in the minimal expression.
Petrick's method finds all minimum SOP covers when EPIs alone do not cover all minterms.
📝 Exam Tips: - Always use the largest possible groups - Groups wrap around K-map edges (top↔bottom, left↔right) - 4-variable K-map also wraps corner-to-corner (diagonal corners are adjacent) - Don't cares can be grouped but need not be covered