PHYS345 Electricity and Electronics

Quiz 8: Karnaugh Mapping

Convert the following truth table to a Karnaugh map:

A B C D   E
0 0 0 0   0
0 0 0 1   1
0 0 1 0   1
0 0 1 1   1
0 1 0 0   1
0 1 0 1   0
0 1 1 0   1
0 1 1 1   0
1 0 0 0   0
1 0 0 1   1
1 0 1 0   1
1 0 1 1   1
1 1 0 0   1
1 1 0 1   0
1 1 1 0   1
1 1 1 1   0

Find the simplest combination of gates that will represent this truth table.

Solution

 CD 00  01  11  10 
AB\
 00    0 1 1 1
 01    1 0 0 1
 11    1 0 0 1
 10    0 1 1 1

Boxing ones:

 CD 00  01  11  10 
AB\
 00    0 1 1 1
 01    1 0 0 1
 11    1 0 0 1
 10    0 1 1 1
    The four boxed ones are represented by
    C.D'

 CD 00  01  11  10 
AB\
 00    0 1 1 1
 01    1 0 0 1
 11    1 0 0 1
 10    0 1 1 1
    The four boxed ones are represented by
    D.B'

 CD 00  01  11  10 
AB\
 00    0 1 1 1
 01    1 0 0 1
 11    1 0 0 1
 10    0 1 1 1
    The four boxed ones are represented by
    B.D'

In total then:

 CD 00  01  11  10 
AB\
 00    0 1 1 1
 01    1 0 0 1
 11    1 0 0 1
 10    0 1 1 1
    The boxed ones are represented by
    C.D' + D.B' + B.D'

Since two NOTed inputs are required, the total gate count for this solution is six gates: two NOT gates, three 2-input AND gate, and a 3-input OR gate.

Alternative Solution

Since there are fewer zeroes than ones and they are "well-clumped," a simpler combination of gates can be realized by boxing the zeros.

 CD 00  01  11  10 
AB\
 00    0 1 1 1
 01    1 0 0 1
 11    1 0 0 1
 10    0 1 1 1
    The four boxed zeroes are represented by
    B.D

 CD 00  01  11  10 
AB\
 00    0 1 1 1
 01    1 0 0 1
 11    1 0 0 1
 10    0 1 1 1
    The two boxed zeroes are represented by
    B'.C'.D'

Since zeroes were boxed, the gate combinations for each individual box must be NORed together. When boxing ones, the individual AND combinations are ORed; when boxing zeroes, the ORed combinations must be NOTed to get zeroes back from the ones resulting from the AND combinations. So a simpler combination of gates to derive the truth table is   (B.D + B'.C'.D')'

Application of DeMorgan's theorem removes the NOTed inputs:   (B.D + (B+C+D)')'
Note that no NOTed inputs are required, thus this approach requires only three gates!

Finally, by another application of DeMorgan's theorem, this result may take another form:   (B.D)' . (B+C+D)

Deciding between the two preceding gate combinations for simplicity would be up to personal preference.


"http://www.physics.udel.edu/~watson/phys345/quiz/8soln.html"
Last updated Nov. 11, 1998.
Copyright George Watson, Univ. of Delaware, 1998.