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

- 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

¡@

Created by Jacky Yeung. Copyright 2003. All Rights Reserved.