Karnaugh Maps (K-Maps) & Quine-McCluskey: Minimization Techniques

TAKEAWAYS:

• K-Maps simplify Boolean functions by grouping adjacent 1s (or 0s) in a 2^n grid, reducing logic gates and cost.
• Quine-McCluskey is an algebraic method that systematically eliminates redundant terms using binary comparisons and prime implicant charts.
• Don’t-care conditions (d) can be used to further minimize functions by treating them as either 0 or 1 strategically.
• K-Maps are limited to 4–6 variables, while Quine-McCluskey handles any number of variables but is more complex.
• Real-world use: K-Maps optimize hardware in eSewa’s payment validation circuits, while Quine-McCluskey minimizes logic in Ncell’s SIM authentication modules.
• Exam focus: Expect construction of K-Maps, minimal SOP/POP, and Quine-McCluskey tables for given functions.

---

1. Karnaugh Maps (K-Maps): Visual Simplification

1.1 Definition and Purpose

A Karnaugh Map (K-Map) is a graphical tool for simplifying Boolean functions by grouping adjacent 1s (or 0s) to form maximal implicants. It reduces the number of logic gates in a circuit, lowering cost and power consumption.

Why use K-Maps?

• Intuitive: Visual grouping avoids algebraic complexity.
• Efficient: Directly identifies minimal sum-of-products (SOP) or minimal product-of-sums (POS).
• Limitation: Works best for 3–6 variables (beyond that, Quine-McCluskey is preferred).

1.2 K-Map Construction Rules

1. Variables: Plot on axes (e.g., AB for rows, CD for columns).
2. Adjacency: Cells are adjacent if they differ by one bit (wrap-around allowed).
3. Groups: Must be powers of 2 (2, 4, 8, ... cells) and maximal (no larger group possible).
4. Don’t-cares (d): Can be treated as 0 or 1 to optimize further.

1.3 Worked Example: 4-Variable K-Map

Function: $F(A,B,C,D)=\Sigma (0,2,5,7,8,10,13,15)+d(3,11)$ Steps:

1. Draw the 4-variable K-Map (2×4 grid):

A 4-variable K-Map grid with AB on rows and CD on columns. (Image: Karnaugh_map_KV_4mal8_01.svg: RosarioVanTulpe derivative wor, Public domain, via Wikimedia Commons)

2. Plot **1s** for minterms (0,2,5,7,8,10,13,15) and **d** for don’t-cares (3,11).
3. **Group 1s**:
- Group of 8: $\overline{A}\overline{B}$ (covers 0,1,2,3 → but 1 is missing; invalid).
- Group of 4: $\overline{A}CD$ (covers 13,15,11,7 → but 11 is don’t-care).
- Group of 4: $A\overline{B}C$ (covers 10,11,6,7 → but 6 is missing).
- Group of 2: $\overline{A}BC$ (covers 5,7).
- Group of 2: $AB\overline{C}D$ (covers 13,15).
4. **Simplified SOP**:
$F=\overline{A}CD+A\overline{B}C+\overline{A}BC+AB\overline{C}D$.

#### **1.4 K-Map vs. Quine-McCluskey**
| Feature               | K-Map                          | Quine-McCluskey               |
|-----------------------|--------------------------------|-------------------------------|
| **Method**            | Graphical (visual grouping)    | Tabular (algebraic)           |
| **Variables**         | 3–6 (best)                     | Any number                    |
| **Complexity**        | Intuitive, fast for small funcs| Systematic, error-prone       |
| **Don’t-cares**       | Easy to include                | Requires separate handling    |
| **Output**            | Minimal SOP/POS directly       | Needs prime implicant chart   |

#### **1.5 Real-World Application: eSewa Payment Validation**
**Scenario**: eSewa’s backend validates transactions using a **4-variable K-Map** to minimize the logic for fraud detection.
- **Inputs**: `A` (user verified), `B` (OTP correct), `C` (bank linked), `D` (amount ≤ limit).
- **Output**: `F` (approve payment).
- **K-Map groups** reduce the circuit to **3 AND gates + 1 OR gate**, saving power in mobile devices.

---

### **2. Quine-McCluskey Method: Algebraic Minimization**
#### **2.1 Definition and Steps**
The **Quine-McCluskey method** is a **systematic algebraic approach** to minimize Boolean functions by:
1. **Listing minterms** in binary.
2. **Comparing terms** to find **prime implicants**.
3. **Constructing a prime implicant chart** to select essential primes.
4. **Covering all minterms** with minimal primes.

**When to use?**
- Functions with **>6 variables** (K-Maps become unwieldy).
- **Automated tools** (e.g., CAD software for FPGAs).

#### **2.2 Step-by-Step Procedure**
**Function**: $F(A,B,C,D)=\Sigma (7,9,12,13,14,15)+d(4,11)$

1. **List minterms in binary** (with don’t-cares marked `d`):

2. **Group by number of 1s**:
- **Group 2**: 0100 (4), 0111 (7)
- **Group 3**: 1001 (9), 1011 (11), 1100 (12)
- **Group 4**: 1101 (13), 1110 (14), 1111 (15)

3. **Compare adjacent groups** (differ by 1 bit):
- Combine 0100 (4) and 0111 (7) → `01-1` (don’t-care in C).
- Combine 1001 (9) and 1011 (11) → `10-1`.
- Combine 1100 (12) and 1101 (13) → `110-`.
- Combine 1110 (14) and 1111 (15) → `111-`.

4. **Repeat until no more combinations**:
- Combine `10-1` and `1101` → `1-01` (but 1101 is already covered).
- Final prime implicants:
  - `01-1` (covers 4,7)
  - `10-1` (covers 9,11)
  - `110-` (covers 12,13)
  - `111-` (covers 14,15)

5. **Prime Implicant Chart**:

6. **Select essential primes**:
- Minterm **15** is only covered by `111-` → **essential**.
- Minterm **12** is only covered by `110-` → **essential**.
- Minterm **9** is only covered by `10-1` → **essential**.
- Minterm **7** is covered by `01-1` → **essential**.
- **Final minimal SOP**:
  $F=\overline{A}BC+A\overline{B}C+AB\overline{C}+ABC$.

#### **2.3 Handling Don’t-Cares**
- **Option 1**: Include don’t-cares in groups to reduce primes.
- **Option 2**: Exclude them if they complicate the chart.
- **Example**: In the above, `d(4)` was used to form `01-1`.

#### **2.4 Real-World Application: Ncell SIM Authentication**
**Scenario**: Ncell’s SIM authentication module uses Quine-McCluskey to minimize logic for **IMSI validation**.
- **Inputs**: `A` (network registered), `B` (SIM PIN entered), `C` (IMSI valid), `D` (roaming allowed).
- **Output**: `F` (authenticate SIM).
- **Quine-McCluskey** reduces the circuit to **4 AND gates + 1 OR gate**, improving response time.

---

### **3. Comparison: K-Maps vs. Quine-McCluskey**
```mermaid
graph LR
 A[K-Maps] -->|Pros| B1[Visual\nEasy for 3-6 vars]
 A -->|Cons| B2[Limited to small funcs]
 C[Quine-McCluskey] -->|Pros| D1[Handles any vars\nSystematic]
 C -->|Cons| D2[Complex\nError-prone]
 B1 & D1 --> E[Minimal SOP/POS]
 B2 & D2 --> F[Choose based on function size]

3.1 When to Use Which?

---

4. Exam Tip: What to Expect

1. K-Map Questions (60% chance):

   • Construct K-Maps for given functions (3–6 variables).
   • Find minimal SOP/POS by grouping.
   • Include don’t-cares to optimize further.
   • Example:

     F(A,B,C,D) = Σ(1,3,4,6,7,11,13,15) + d(0,2,5,10)
     

     Solution: Group 111- (14,15), 1-01 (5,7,13), 01-1 (3,7), and use don’t-cares to merge.

2. Quine-McCluskey Questions (40% chance):

   • List minterms and group by 1s.
   • Find prime implicants by comparing.
   • Draw the prime implicant chart and select essential primes.
   • Example:

     F(A,B,C,D) = Σ(0,2,5,7,8,10,13,15)
     

     Solution: Primes are 0-0-, A-B-, A-C-, AB-, ABC.

3. Common Mistakes to Avoid:

   • Incorrect adjacency: Wrapping around is allowed (e.g., 0000 and 0001 are adjacent).
   • Non-maximal groups: Always check for larger possible groups.
   • Missing don’t-cares: They can simplify the function further.
   • Quine-McCluskey errors: Forgetting to combine all possible terms in each step.

4. Time Management:

   • K-Maps: ~5–7 minutes per question (practice grouping speed).
   • Quine-McCluskey: ~10–12 minutes (focus on systematic comparison).

---

5. In the Real World

1. eSewa Payment Gateway:

   • K-Maps are used to minimize the logic for transaction approval circuits.
   • Example: A 4-variable K-Map reduces the fraud detection circuit from 5 gates to 3 gates, saving battery on user devices.

2. Ncell SIM Authentication:

   • Quine-McCluskey minimizes the IMSI validation logic in base stations.
   • Example: A 5-variable function for SIM authentication is simplified to 4 essential primes, reducing latency in network responses.

3. Daraz Order Processing:

   • K-Maps optimize the stock availability checker (inputs: A=item in stock, B=warehouse X, C=fast shipping, D=discount applied).
   • Example: The minimal SOP ensures the system checks stock in 2 clock cycles instead of 3.

4. Bank Loan Approval (Nepal Bank Ltd):

   • Quine-McCluskey simplifies the credit score logic (inputs: A=income ≥ threshold, B=no defaults, C=collateral, D=loan amount ≤ limit).
   • Example: The minimal expression reduces the approval circuit to 3 AND gates, speeding up loan processing.

---

6. Worked Example: Traffic Light Controller (K-Map)

Scenario: Design a 3-variable K-Map for a traffic light controller where:

• A = Pedestrian button pressed
• B = Car sensor active
• C = Timer expired
• F = Green light for pedestrians.

Function: $F(A,B,C)=\Sigma (1,2,4,7)$

1. Draw the 3-variable K-Map:

2. Plot 1s for minterms 1,2,4,7.
3. Group:
   • Group of 4: $\overline{A}$ (covers 0,1,4,5 → but 5 is missing).
   • Group of 2: $AC$ (covers 4,5 → but 5 is 0).
   • Group of 2: $BC$ (covers 2,3 → but 3 is 0).
   • Correction: Only valid group is $A\overline{B}+\overline{B}C$.
4. Simplified SOP: $F=A\overline{B}+\overline{B}C$.

Real-World Tie-In:

• This logic is used in Kathmandu’s smart traffic lights to prioritize pedestrians when the button is pressed (A=1) and no cars are detected (B=0).

---

7. Worked Example: WhatsApp Message Encryption (Quine-McCluskey)

Scenario: Simplify a 4-variable function for WhatsApp’s end-to-end encryption key validation:

• A = Key length valid
• B = Checksum correct
• C = Timestamp recent
• D = Device verified
• Function: $F(A,B,C,D)=\Sigma (3,5,6,7,10,11,12,13,14,15)$

1. List minterms:

   | Minterm | ABCD |
   |---------|------|
   | 3       | 0011 |
   | 5       | 0101 |
   | 6       | 0110 |
   | 7       | 0111 |
   | 10      | 1010 |
   | 11      | 1011 |
   | 12      | 1100 |
   | 13      | 1101 |
   | 14      | 1110 |
   | 15      | 1111 |
   

2. Group by 1s:
   • Group 2: 0011 (3), 0111 (7)
   • Group 3: 0101 (5), 0111 (7), 1011 (11)
   • Group 4: 1100 (12), 1101 (13), 1110 (14), 1111 (15)
3. Combine:
   • 0011 + 0111 → 0-11
   • 0101 + 0111 → 01-1
   • 1010 + 1011 → 101-
   • 1100 + 1101 → 110-
4. Prime implicants:
   • 0-11 (covers 3,7)
   • 01-1 (covers 5,7)
   • 101- (covers 10,11)
   • 110- (covers 12,13)
   • 111- (covers 14,15)
5. Essential primes:
   • 101- (covers 10,11, no overlap)
   • 110- (covers 12,13, no overlap)
   • 111- (covers 14,15, no overlap)
   • 0-11 (covers 3,7, but 7 is also in 01-1 → not essential).
6. Final minimal SOP: $F=BC+AB\overline{C}+ABC$.

Real-World Tie-In:

• This simplified logic reduces WhatsApp’s encryption validation circuit from 8 gates to 5 gates, improving message delivery speed.

---

8. Summary Table: Key Formulas and Steps

---

9. Exam Tip: Quick Revision Checklist

Before the exam, verify you can:

1. Draw K-Maps for 3–6 variables correctly.
2. Group 1s maximally (including wrap-around).
3. Apply don’t-cares to reduce terms.
4. List minterms in binary for Quine-McCluskey.
5. Construct prime implicant charts and select essential primes.
6. Write minimal SOP/POS from simplified groups.

Pro Tip: Practice 10 K-Map problems and 5 Quine-McCluskey problems under timed conditions. Focus on grouping speed for K-Maps and systematic comparison for Quine-McCluskey.

---

10. Real Chip Example: 74LS138 Decoder

How K-Maps Apply:

• The enable inputs (G1, G2A, G2B) are minimized using K-Maps to reduce gate count in the IC.
• Example: The active-low enable logic is derived from a 3-variable K-Map to ensure only one output is active at a time.

---

11. Final Worked Example: NEPSE Stock Alert System

Scenario: Design a 4-variable K-Map for a stock alert system where:

• A = Price > moving average
• B = Volume > average
• C = News sentiment positive
• D = Analyst rating upgraded
• Function: $F(A,B,C,D)=\Sigma (3,7,11,15)+d(5,13)$

1. K-Map:

2. Groups:
   • Group of 4: $BC$ (covers 3,7,11,15 → but 11,15 are not adjacent to 3,7).
   • Correction: Use don’t-cares to form B-C- (covers 3,7,11,15).
3. Simplified SOP: $F=BC$.

Real-World Tie-In:

• This minimal logic is used in NEPSE’s trading terminals to trigger alerts with zero gate delay, improving trader response time.

---