Karnaugh Maps (K-Maps): Simplification, Don’t-Care Terms & Realization

TAKEAWAYS:

• K-Maps reduce Boolean expressions by grouping adjacent 1s (or 0s) in a 2^n grid, cutting unnecessary gates in hardware.
• Don’t-care terms (d) can be treated as 0s or 1s to simplify further, saving components.
• Grouping rules: Only adjacent cells (horizontally, vertically, or diagonally) with one variable change can be combined.
• Realization: Simplified SOP/POS forms are implemented using AND-OR or OR-AND gates, respectively.
• Applications: Used in eSewa’s transaction validation (parity checks), Khalti’s encryption (logic minimization for speed), and NTC’s call routing (priority encoders).
• Exam focus: Always show grouping steps, simplified expression, and logic diagram—even if the question only asks for the minimized form.

1. Introduction to Karnaugh Maps (K-Maps)

K-Maps are graphical tools for simplifying Boolean expressions by visually grouping terms. They work by arranging minterms in a grid where adjacent cells differ by one variable, making it easy to spot common factors.

How K-Maps Work

• Rows/Columns: Represent variables (e.g., 2 variables → 4-cell map; 3 variables → 8-cell map; 4 variables → 16-cell map).
• Adjacency: Wraparound is allowed (e.g., the first and last rows/columns are adjacent).
• Groups: Must be powers of 2 (1, 2, 4, 8) and cover as many 1s as possible.

Example: 3-Variable K-Map

graph TD
    A["AB\C"] --> B["00"]
    A --> C["01"]
    A --> D["11"]
    A --> E["10"]
    B --> F["0"]
    C --> F
    D --> G["1"]
    E --> G
    F --> H["0"]
    G --> H
    H --> I["F(A,B,C)"]

Caption: A 3-variable K-Map grid. Cells with 1s are grouped to simplify the expression.

A 4-variable K-Map showing minterms 0-15 with grouped 1s for simplification. (Image: Karnaugh_map_KV_4mal8_01.svg: RosarioVanTulpe derivative wor, Public domain, via Wikimedia Commons)

2. Steps to Simplify Using K-Maps

1. List minterms/maxterms: Convert the Boolean function to its canonical form (SOP/POS).
2. Fill the K-Map: Plot 1s (for SOP) or 0s (for POS) in the correct cells. Mark don’t-care terms (d) if given.
3. Group 1s/0s: Start with the largest possible groups (8, 4, 2), then fill smaller groups.
4. Write the simplified expression: Each group becomes a product term (for SOP) or sum term (for POS).

Worked Example: Simplify $F(A,B,C,D)=\sum m(3,4,5,7,9,13,14,15)$

1. Fill the 4-variable K-Map:

   | AB\CD | 00 | 01 | 11 | 10 |
   |-------|----|----|----|----|
   | 00    | 0  | 0  | 1  | 1  | (m3, m1)
   | 01    | 0  | 1  | 1  | 1  | (m5, m7, m4, m6)
   | 11    | 1  | 1  | 1  | 1  | (m13, m15, m14, m12)
   | 10    | 1  | 0  | 0  | 0  | (m9)
   

   Groups:

   • 8-cell group: All 1s in the bottom two rows (covered by $\overline{A}$).
   • 4-cell group: Top-right 4 cells (covered by $B\overline{C}$).
   • 2-cell group: Middle-right (covered by $A\overline{B}C$).

2. Simplified Expression: $F=\overline{A}+B\overline{C}+A\overline{B}C$.

3. Don’t-Care Conditions (d)

Don’t-care terms (d) can be treated as 0s or 1s to simplify the expression further. They are marked with X or d in the K-Map.

Example: Simplify with Don’t-Cares

Given: $F(A,B,C,D)=\sum m(0,2,6,8,10)$ Don’t-cares: $d(A,B,C,D)=\sum d(11,12,13,14,15)$

1. Fill the K-Map:

   | AB\CD | 00 | 01 | 11 | 10 |
   |-------|----|----|----|----|
   | 00    | 1  | 0  | X  | 1  | (m0, m2)
   | 01    | 0  | 0  | 0  | 0  |
   | 11    | X  | X  | X  | X  | (all d)
   | 10    | 1  | 0  | 0  | 0  | (m8, m10)
   

2. Groups:
   • Use don’t-cares to form larger groups (e.g., combine $m0$ and $m8$ via $\overline{B}\overline{D}$).
3. Simplified Expression: $F=\overline{B}\overline{D}+\overline{A}\overline{C}\overline{D}$.

4. K-Map vs. Boolean Algebra

5. Real-World Applications

In the Real World

1. eSewa Transaction Validation

   • Idea Used: Parity generators (simplified using K-Maps).
   • How: A 3-bit parity generator (from past exams) checks if the number of 1s in a transaction ID is odd/even. K-Maps minimize the logic to reduce hardware cost.
   • Example: For inputs $A,B,C$, the parity output $P=A\oplus B\oplus C$ is simplified using a K-Map to avoid redundant gates.

2. Khalti’s Encryption Logic

   • Idea Used: Logic minimization for faster encryption.
   • How: Khalti’s backend uses simplified Boolean logic (via K-Maps) to validate user inputs (e.g., OTPs) in real-time. Fewer gates mean lower latency.

3. NTC’s Call Routing Priority Encoder

   • Idea Used: Priority encoders (simplified using K-Maps).
   • How: When multiple calls come in, NTC’s system uses a 4-to-2 priority encoder (like in past exams) to route the highest-priority call first. The encoder’s logic is minimized via K-Maps to save space on the circuit board.

Worked Example: NTC Call Routing

Suppose NTC has 4 incoming call lines ($I_0$ to $I_3$), where $I_3$ has the highest priority. Design a priority encoder using K-Maps.

1. Truth Table:

   | I3 | I2 | I1 | I0 | Y1 | Y0 |
   |----|----|----|----|----|----|
   | 1  | x  | x  | x  | 1  | 1  |
   | 0  | 1  | x  | x  | 1  | 0  |
   | 0  | 0  | 1  | x  | 0  | 1  |
   | 0  | 0  | 0  | 1  | 0  | 0  |
   

2. K-Map for $Y1$ and $Y0$:
   • Group 1s to get $Y1=I3+I2$ and $Y0=I3+I1$.
3. Logic Circuit: Use AND/OR gates to implement the simplified expressions.

6. Implementing Simplified Logic

Once simplified, the Boolean expression can be realized using:

• AND-OR gates for SOP.
• OR-AND gates for POS.
• NAND/NOR gates (universal gates) for any logic.

Example: Realize $F=\overline{A}+B\overline{C}$ using NAND gates

1. Convert to NAND-NAND form: $F=\overline{\overline{\overline{A}}\cdot \overline{B\overline{C}}}$.
2. Logic Diagram:

   flowchart LR
     A["A"] --> N1["NAND"]
     B["B"] --> N2["NAND"]
     C["C"] --> N3["NAND"]
     N2 -->|"B"| N4["NAND"]
     C -->|"C"| N4
     N1 -->|"A"| N5["NAND"]
     N4 -->|"B\overline{C}"| N5
     N5 --> F["F"]

   Caption: NAND-NAND realization of $F=\overline{A}+B\overline{C}$.

7. Common Mistakes to Avoid

1. Incorrect Grouping: Only adjacent cells (including wraparound) can be grouped.
   • ❌ Grouping non-adjacent cells (e.g., $m0$ and $m5$ in a 4-variable map).
2. Ignoring Don’t-Cares: Don’t-cares can simplify the expression further—always use them if they help form larger groups.
3. Missing Groups: Always check for groups of 8, 4, 2, and 1. Overlook a group of 4? You might miss a simpler term.
4. Variable Order: Ensure variables are ordered correctly (e.g., $AB\text{CD}$ for 4 variables).

Exam Tip

1. Show All Steps:
   • Always draw the K-Map with groups circled.
   • Write the simplified expression clearly.
   • If asked for a logic diagram, draw it using standard gate symbols (AND, OR, NOT, etc.).
2. Handle Don’t-Cares:
   • If don’t-cares are given, mark them in the K-Map and explain how you used them.
3. Realization Questions:
   • For questions asking to realize the circuit (e.g., using NAND gates), show the conversion steps from simplified Boolean to NAND-NAND form.
4. Past Exam Patterns:
   • Often combines simplification + realization (e.g., "Simplify using K-Map and draw the circuit using NOR gates").
   • Example Question: "Design a full adder using K-Map simplification" → First simplify the sum and carry outputs, then draw the circuit.