[ENGN3213 Home]

### Karnaugh Maps (K-Maps)

Karnaugh or K- maps   are useful tool fot boolean function minimization, and for visualization of the boolean function. In brief,

• K-maps provide a graphical method for minimizing boolean functions via pattern recognition forup to about n=6 variables.
• For larger numbers of variables, there are computer algorithms which can yield near-minimal implementations.
• K-maps are a way of expressing truth tables to make minimization easier. They are constructed from minterm codes.

Consider the boolean function

The truth table is
 A B f 0 0 1 m0 0 1 1 m1 1 0 1 m2 1 1 0 m3

The K-map is shown in Figure 26. The essence of the K-map is the two dimensional representation of f, which is equivalent to the truth table but more visual.

To minimize f, we loop out logical adjacencies, Figure 26.

Therefore

This is less complex than f in canonical SOP form.

Note. Looping out logical adjacencies is a graphical alternative to algebraic calculations.

Unit distance code (Gray code.)   For two bits, the Gray code is:

 00 01 11 10
Only one bit changes as you go from left to right. This code preserves logical adjacencies.

The K-map method is to loop out groups of 2n logically adjacent minterms. Each looped out group corresponds to a product term in a minimal SOP expression.

1.
Loop out single 1s (n=0) which have no logical adjacencies.
2.
Loop out all pairs of 1s (n=1) which cannot be included in a larger group.
3.
Loop out all quads of 1s (n=2) which cannot be included in a larger group.
4.
Etc.

Example. The K-map is shown in Figure 27.

Moving left to right or up to down in the K-map changes only one digit in the minterm code. Note the wrap-around at the ends: because of logical adjacency, the top and bottom are joined, and the left and right are joined.

n=0: none

n=1:

n=2:

Therefore the minimal SOP representation is

Example. The K-map is shown in Figure 28.

Therefore the minimal SOP representation is

Don't cares.   In some applications it doesn't matter what the output is for certain input values. These are called don't cares.

For instance, in the Binary Coded Decimal   code, not all input values occur:

 0 0 0 0 0 0 0 0 1 1 0 0 1 0 2 0 0 1 1 3 0 1 0 0 4 0 1 0 1 5 0 1 1 0 6 0 1 1 1 7 1 0 0 0 8 1 0 0 1 9 1 0 1 0 10 1 0 1 1 11 1 1 0 0 12 1 1 0 1 13 1 1 1 0 14 1 1 1 1 15
The decimal numbers are those in the range , and a minimum of 4 bits is needed to encode these. The remaining numbers correspond to code values which are not used in BCD.

We shall use the symbols or X to denote don't cares.

Don't cares can be exploited to help minimize boolean functions.

Example. The K-map is shown in Figure 29.

The minimal SOP representation is

Check out the web page kmap.html for more on kmaps and how they work.

[ENGN3213 Home]

ANU Engineering - ENGN3213