Karnaugh Maps

Introduction

A technique which helps to derive logical functions from truth tables
Purpose is to minimize prime implicants, vastly employed for designing digital circuits
Maurice Karnaugh's system of mapping and simplifying Boolean expressions
K-maps are different from truth tables in that the output of a particular set of values is placed in the corresponding row and column

Karnaugh Maps with 2 Variables

A 2 row by 2 column table is required, because there are 4 possible combinations of output when there are two Boolean variables (NA*NB, NA*B, A*NB, and A*B)
The following is an example of a 2 Variables K-Map Table

Cell 1 is where the output of NA*NB is stored, cell 2 is where the output of NA*B is stored, and so on
After all the cells of the K-Map is filled, adjacent 1's are looped together in groups of two, four, or eight, etc.
Each loop is a new term in the simplified Boolean expression.
For example, suppose the original Boolean expression is NA*B + A*NB + A*B = Y, the K-Map would look like:

The two loops in the K-map means that the simplified expression will have two terms ORed together
Simplifying the expression can now begin, the bottom loop can be simplified to just A since the A is included along with a B and NB, therefore, the B and NB terms can be eliminated according to the rules of Boolean algebra
Similarly with the vertical loop, the A and NA terms can be eliminated, leaving only the B behind
These two leftover terms, A and B, are then ORed together, giving the simplified Boolean expression A + B = Y

Karnaugh Maps With 3 Variables

2 columns and 4 rows, a total of 8 combinations
Basically the same as with 2 variables, but it is important to prepare the K-map in a particular way
As the K-map progresses downward on the left side of the map, only one variable should change for each step, if the first row is NA*NB, then the second row should be NA*B or A*NB but should not be A*B. This is vital because the loops will be affected, meaning that the simplifying will be affected as well

Here is an example of a 3 variable problem, suppose the original Boolean expression is A*NB*NC + NA*NB*NC + NA*NB*C + A*B*NC = Y

Summary

The procedure of simplifying Boolean expressions using K-maps can be summarized in 6 steps

Construct the K-map, make sure that only one variable changes at a time from column to column or row to row
Record 1's on the K-map
Loop adjacent 1's (loops of multiples of 2)
Simplify expression by dropping terms that contain a term and its complement within a loop
OR the remaining terms (one term per loop)
Write the simplified Boolean expression

References

Karnaugh maps: representations for configurations. (1999). Retrieved April 30, 2003 from the Internet: http://tecfa.unige.ch/~lemay/thesis/THX-Doctorat/node33.html