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

• Hence, the simplified expression becomes A*NC + NA*NB = Y

¡@

Summary

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

1. Construct the K-map, make sure that only one variable changes at a time from column to column or row to row
2. Record 1's on the K-map
3. Loop adjacent 1's (loops of multiples of 2)
4. Simplify expression by dropping terms that contain a term and its complement within a loop
5. OR the remaining terms (one term per loop)
6. 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

¡@