A Worked Example

Problem:

 Given a Boolean expression:

F = AB + B'C

use a Karnaugh map (K-map) to minimize.

Wondering how to pronounce "Karnaugh map?" Click here.

Approach:

Determine the size (number of cells) for the Karnaugh map. To do this, count the number of unique variables in the expression. Do not count B' (the complement of B) as a separate variable from B. Hence, in  AB + B'C there are 3 variables: A, B, and C.

For k variables, each of which can take one of two values (e.g., 1 or 0, true or false, high or low voltage), there are 2k possible combinations of variable values. Here, 2 is the base of the number system, since there are only 2 possible values. Hence, for the 3 variables in this problem, we must have 23 = 2 x 2 x 2 = 8 cells in the Karnaugh map to hold all the possible combinations.

Number of cells in map = 23 = 8

Just in case you are curious, here is a truth table of all 8 combinations, color-coded so we can match them up easily with the Karnaugh map that we are doing next:

Possible Combinations:

A B C
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0

Next we examine an empty Karnaugh map with 8 cells, this time colored (for educational purposes only) to show which ABC value from the above table corresponds to which cell. Here the four rows represent all the combinations of the variables BC, and the two columns represent all the values that can be taken by the remaining variable, A.  Note that the values of B and C are in Gray code order in the rows.

We can see that the upper left cell corresponds to an ABC value of 000, and the lower right to an ABC value of 110.  Inside each cell will go the value of F = AB + B'C for that cell's ABC value.

Here's an untinted version of the same empty 3-variable Karnaugh map. Having an empty version can be handy, so that you can quickly make a new 3-variable Karnaugh map without having to redraw one each time. To save the image to your hard drive, right-click on it, and depending on your browser, choose "Save Picture As" or an equivalent command.

Now back to the problem. Let's populate the empty Karnaugh map with values of F = AB + B'C, one for each possible value of ABC. First make a truth table for F, so we can know what values to put in the cells. The leftmost 3 columns of the truth table for F are the same as the truth table above showing all possible value combinations for ABC.

Side Note: At left, the text corresponding to the number of unique variables is highlighted in yellow, and the text corresponding to the base of the number system is highlighted in turquoise.

Note that color is not used in Karnaugh-map-related homework, although with more complex maps sometimes different colors are used around the prime implicants, for clarity.

 Color is used here only as an educational aid.

 


 

Truth Table for F = AB + B'C

A

B

C

B'

AB

B'C

F = AB + B'C

1

1

1

0

1

0

1

1

1

0

0

1

0

1

1

0

1

1

0

1

1

1

0

0

1

0

0

0

0

1

1

0

0

0

0

0

1

0

0

0

0

0

0

0

1

1

0

1

1

0

0

0

1

0

0

0

 

Continuing on:

 

Here is the 8-cell Karnaugh map, filled with the values from the truth table:

Next, combine prime implicants, which are maximal groupings of 1's of sizes that are powers of 2, such as 1 one, 2 ones, 4 ones, 8 ones, etc.  Here the largest number of 1's that is a power of two that we can find in a block or straight line is 2. We do have one column of three 1's, but 3 is not an integral power of 2, so we can't use that. Two groupings of 2 ones each is the best we can manage.

The lower circle represents A=1  and B=1, with no reference to C since C can be either 0 or 1. Hence the prime implicant represented by the lower circle is  AB.

The upper circle represents B=0 and C=1, with no reference to A since A can be either 0 or 1. Hence the prime implicant represented by the upper circle is B'C.

Since there are the only two prime implicants, the resulting answer for the minimized representation of  F is:

F = AB + B'C

which is coincidentally the same representation we had for F at the start. This means that F was already in its minimal form when we started the problem.

DONE

 

For the drawing Smartdraw Professional Plus v. 6.2 was used, with the resulting screen image captured by Snagit from Techsmith.com, and further embellished, then optimized for the Web, using Photoshop7. The title graphic was done in Photoshop 7.

 

Copyright © 2003 Crystal Sloan and Dr. Yul Williams
Page Design and Original Graphics Copyright 2003 Crystal Sloan.