Karnaugh Maps

Karnaugh maps or K-maps are a useful graphic technique to perform the minimization of a canonical form. They utilise Boolean theorems in a mapping procedure which results in a simplified Boolean expression being developed.

There are five basic steps in the minimization procedure, these are

1. Develop the first canonical expression (minterm form) from the associated truth table. This has already been described in the section on canonical forms.
2. Plot 1s in the Karnaugh map for each minterm in the expression. Each AND-ed set of variables in the minterm expression is placed in the corresponding cell on the K-map. See below for more information on labelling the K-map.
3. Loop adjacent groups of 2, 4 or 8 1s together. A more detailed summary of looping rules can be found below.
4. Write one minterm per loop, eliminating variables where possible. When a variable and its complement are contained inside a loop then that variable can be eliminated (for that loop only), save the variables that are left.
5. Logically OR the remaining minterms together to give the simplified minterm expression.

A detailed example of using Karnaugh maps for circuit simplification is available in the Solved Problems.

In the case of simplifying a maxterm expression the steps are very similar with only slight differences due to the OR-AND nature of the maxterm expressions. The steps involved are

1. Develop the second canonical expression (maxterm form) from the associated truth table. This has already been described in the section on canonical forms.
2. Plot 1s in the Karnaugh map for each maxterm in the expression. Each OR-ed set of variables in the minterm expression is placed in the corresponding cell on the K-map. See below for more information on labelling the K-map. Note here you are propogating 0s in the truth table through as 1s in the K-map.
3. Loop adjacent groups of 2, 4 or 8 1s together. A more detailed summary of looping rules can be found below.
4. Write one maxterm per loop, eliminating variables where possible. When a variable and its complement are contained inside a loop then that variable can be eliminated (for that loop only), save the variables that are left.
5. Logically AND the remaining maxterms together to give the simplified maxterm expression.

Labelling Karnaugh Maps

Special care must be taken when labelling Karnaugh maps. An incorrectly-labelled K-map will not allow the correct minimization to occur. The sequence used along each axis is binary 00,01,11,10. This is an example of Gray coding where only one bit is changed at a time. Gray coding will be discussed in a later lecture.

For minterm expressions, the correct labelling for a Karnaugh map corresponding to a 4-input circuit (inputs A, B, C and D) is

whilst the correct labelling for a maxterm K-map for the same circuit is

the labelling for 2- and 3-input maps follows logically from this.

Looping on Karnaugh Maps

Specific rules apply to looping on a Karnaugh Map, they are summarised here

• Loops must contain 2ⁿ cells set to 1.
• A single cell (loop of 2⁰) cannot be simplified.
• A loop of 2 (2¹) is independant of 1 variable, a loop of 4 (2²) is independant of 2 variables. In general a loop of 2ⁿ cells is independant of n variables.
• Using the largest loops possible will give the simplest functions.
• All cells in the K-map set to 1 must be included in at least one loop when developing the minterm or maxterm form.
• Loops may overlap if they contain at least one other unlooped cell in the K-map.
• Any loop that has all of its cells included in other loops is redundant.
• Loops must be square or rectangular. Diagonal or L-shaped loops are invalid.
• The edges of a K-map are considered to be adjacent. Therefore a loop can leave at the opt of a K-map and re-enter at the bottom, similarly for the two sides.
• There may be different ways of looping a K-map since for any given circuit there may not be a unique minimal form.