Karnaugh-Veitch Maps

For , it is difficult to use Gray Code Simplification. We can make it easier with K-maps.

Example

Find the simplest function for the truth table:
0 0 1
0 1 1
1 0 0
1 1 1

solution
The truth table can be represented in a k-map:

And we can group certain numbers in groups of some power of 2 to form our simplified function:

  • For the blue group, note that the value is whenever , so we have a term
    • Algebraically, this is
  • For the red group, note that the value is 1 whenever , so we have another term
    • Algebraically, this is

So our function is:

Strategy for SOP Simplification

  • For an SOP expression, all 1s in the k-map must be covered by at least one rectangle
  • Number of items in a group must be a power of 2 and rectangular
  • For best results, the rectangles must be as large as possible, and as few as possible (essential prime implicant)

Example - 3 Variable

Find the simplest function for the truth table:
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

solution

Example - 4 Variable

Simplify the function
(see minterms)

solution

Note that we group the red part into 4 because that reduces the cost (bigger group = better).

Note that each "coordinate" represents a binary number, with being the most significant bit.

Example - Corner Wrapping

Simplify the function

solution

Example - 5 Variable

Here, we have 2 k-maps layered on top of each other for a 5 variable k-map. Groups can be through layers as well, as long as the size of the group is a power of 2.

Example - POS and Edge Wrapping

Simplify the function
(see maxterms)

solution
Since we have POS, our maxterms correspond to "0" instead of "1", and for simplifying, we seek to group "0"s.