Karnaugh Map (K-map)

Introduction

• Karnaugh Map is a technique to simplify Boolean expressions.
• Simplifying Boolean expressions reduces the number of logic gates required for implementation.
• Example: Minimizing Boolean expression to reduce 3 AND gates and 1 OR gate in canonical SOP form.

Benefits of K-map

• Reduces number of logic gates.
• Reduces total cost and space required for implementation.
• Easier than algebraic minimization, especially for more variables.

Constructing K-map

2-variable K-map

• Total 4 combinations; 4 minterms.
• Each cell represents a minterm (A’B’, A’B, AB’, AB).
• Cells are numbered and correspond to specific combinations of A and B.

3-variable K-map

• Total 8 combinations; 8 minterms.
• Cells numbered in Gray code form for easy adjacency (only 1-bit change between adjacent cells).
• Cells correspond to combinations of A, B, and C.

Mapping Boolean Expressions

• Expressions in sum-of-products (SOP) form are mapped with 1s indicating present minterms.
• Example: If F1 = A’B’ + A’B + AB, then map 1 on corresponding cells in K-map.

Minimizing Boolean Expressions

• Make groups of adjacent 1s in powers of 2 (e.g., groups of 2, 4).
• Groups can overlap, but must cover all 1s.

Rules for Grouping

• In K-map, cells are arranged such that between each pair of adjacent cells, only 1 bit changes.
• Variables that change within a group are discarded; variables that stay constant are included in result.
• Groups should be rectangular or square.

Example Minimizations

2-variable Example

• Function: F1 = m0, m1, m3 (map 1s in corresponding cells).
• Minimized: A’ + B

3-variable Example

• Function: F1 (A, B, C) = m0, m1, m5 (map 1s in corresponding cells).
• First group: 2 adjacent 1s (by rows or columns)
  • Discard changing variable, keep constant ones.
  • Result: A’B’
• Second group: Any remaining 1s.
  • Result: B’C
• Overall result: A’B’ + B’C

Overlapping Groups Example

• For overlapping groups, consider groups independently as well as combined if adjacent in Gray code.
• Ensure all 1s are covered using minimum number of groups.
• Example:
  • Map F1 = {m0, m1, m3, m5}
  • Group of A’B’, second group B’C, combined will give final result.

Advanced Grouping Patterns

• Make larger groups if only 1 variable changes among combinations (groups of 4 or 8).
• Example
  1. Group of 4
     • ABC’ = 0 → Group: A’B’
  2. Group of overlapping or edge cells if only one bit change.
     • Combine cells including corners.

K-map Insights

• Cells adjacent at edges can form groups (looping top-bottom, left-right, corners).
• Minimize expressions by creating the smallest number of groups.
• Cover all 1s by forming groups in power of 2.

Conclusion

• K-map simplifies Boolean functions without requiring intensive Boolean algebra.
• Upcoming video: 4-variable K-map.
• Engage with comments for questions or suggestions.
• Like and subscribe for more educational content on electronics.