Karnaugh Maps

Karnaugh Maps

Overview

Karnaugh Maps (K-maps) provide a visual method for simplifying Boolean expressions. By arranging minterms in a special grid where adjacent cells differ by only one variable, we can easily identify patterns that lead to simplified expressions. K-maps are particularly effective for functions with up to 5-6 variables.

Detailed Explanation

Basic Structure

2-Variable:    3-Variable:
   B               BC
A  0  1      A  00 01 11 10
0 |__|__|    0 |__|__|__|__|
1 |__|__|    1 |__|__|__|__|

Cell Grouping Rules

1. Group Size: 2ⁿ (1,2,4,8,16)
2. Adjacent cells only
3. Overlap allowed
4. Maximum possible size
5. All 1s must be covered

Valid Groups:
┌──┐  ┌────┐  ┌──────┐
|11|  |1111|  |111111|
└──┘  └────┘  └──────┘

Simplification Process

Example:
F(A,B,C) = ∑m(0,1,2,3,4,5,7)

    BC
A   00 01 11 10
0   1  1  1  1
1   1  1  0  1

Groups:
1) 0xx = 4 cells → A'
2) x0x = 4 cells → B'
Result: F = A' + B'

Don’t Care Conditions

Mark with 'X'
Can be used as 1 or 0
Choose based on simplification

Example:
    B
A   0  1
0   1  X
1   X  1

Can group as:
┌──┐
|11|  = A'B' + AB
└──┘

Practice Problems

  1. Simplify using K-map:

    F(A,B,C) = ∑m(0,1,3,5,7)
F(A,B,C,D) = ∑m(0,2,4,6,8,10,12,14)

  2. Solve with don’t cares:

    F(A,B,C) = ∑m(1,3,5,7), d(0,2,6)

References

← Back to Minor - Digital Electronics