next up previous contents index

[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,

Consider the boolean function

\begin{displaymath}f(A,B) = \sum m(0,1,2) \end{displaymath}

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.  


  
Figure 26: K-map showing looped-out terms and also corresponding minterms.
\begin{figure} \begin{center} \epsfig{file=images/diglogimg16.eps}\end{center}\end{figure}

Therefore

\begin{displaymath}f = \overline{A} + \overline{B} \end{displaymath}

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. $f(A,B,C) = \sum m(0,2,3,4,6)$ The K-map is shown in Figure 27.

  
Figure: K-map for $f(A,B,C) = \sum m(0,2,3,4,6)$.
\begin{figure} \begin{center} \epsfig{file=images/diglogimg17.eps}\end{center}\end{figure}

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: $m_2+m_3 = \overline{A}B$

n=2: $m_0 + m_2 + m_4 + m_6 = \overline{C}$

Therefore the minimal SOP representation is

\begin{displaymath}f = \overline{A}B + \overline{C} \end{displaymath}

Example. $f(A,B,C,D) = \sum m(0,1,4,8,9,12,14,15)$ The K-map is shown in Figure 28.

  
Figure: K-map for $f(A,B,C,D) = \sum m(0,1,4,8,9,12,14,15)$.
\begin{figure} \begin{center} \epsfig{file=images/diglogimg18.eps}\end{center}\end{figure}

Therefore the minimal SOP representation is

\begin{displaymath}f = ABC + \overline{C}.\overline{D} + \overline{B}.\overline{C} \end{displaymath}

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 $0,1,\ldots,9$, and a minimum of 4 bits is needed to encode these. The remaining numbers $10,11,\ldots,15$ correspond to code values which are not used in BCD.

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

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

Example. $f(A,B,C) = \sum m(0,1,5,7) + \phi (2,4)$ The K-map is shown in Figure 29.

  
Figure: K-map for $f(A,B,C) = \sum m(0,1,5,7) + \phi (2,4)$.
\begin{figure} \begin{center} \epsfig{file=images/diglogimg19.eps}\end{center}\end{figure}

The minimal SOP representation is

\begin{displaymath}f = \overline{B} + AC \end{displaymath}

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

next up previous contents index

[ENGN3213 Home]

ANU Engineering - ENGN3213