ic
Section 8.3 Minimization
677
While the Quine–McCluskey procedure applies to truth functions with any
number of input variables, for a large number of variables, the procedure is extremely
tedious to do by hand. However, it is exactly the kind of systematic, mechanical process that lends itself to a computerized solution. In contrast, Karnaugh maps make
use of the human ability to quickly recognize visual patterns.
If the truth function f has few 0 values and a large number of 1 values, it may
be simpler to implement the Quine–McCluskey procedure for the complement of
the function, f ′, which will have 1 values where f has 0 values, and vice versa.
Once a minimal sum-of-products expression is obtained for f ′, it can be complemented to obtain an expression for f, although the new expression will not be in
sum-of-products form. (In fact, by De Morgan’s laws, it will be equivalent to a
product-of-sums form.) We can obtain the network for f from the sum-of-products
network for f ′ by tacking an inverter on the end.
The whole object of minimizing a network is to simplify the internal configuration while preserving the external behavior. In Chapter 9 we will attempt the
same sort of minimization on finite-state machine structures.
PraCtiCe 19 Use the Quine–McCluskey procedure to find a minimal sum-of-products form for the truth
function in Table 8.20.
table 8.20
x 1
x 2
x 3
f( x 1 , x 2 , x 3 )
1
1
1
1
1
1
0
1
1
0
1
0
1
0
0
1
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
1
■
S e c t i o n 8 . 3 review
tecHniQueS
• Minimize the canonical sum-of-products form for
a truth function by using a Karnaugh map.
• Minimize the canonical sum-of-products form for
a truth function by using the Quine–McCluskey
procedure.
main iDea
• Algorithms exist for reducing a canonical sumof-products form to a minimized sum-of-products
form.
W
W