Bài giảng Chapter 4: Function minimization algorithms

mar65164_ch04.qxd<br /> <br /> 12/2/03<br /> <br /> 1:11 PM<br /> <br /> Page 211<br /> <br /> C h a p t e r<br /> <br /> 4<br /> <br /> Function Minimization<br /> Algorithms<br /> <br /> I<br /> <br /> n this chapter, we will look at two approaches to finding all of the<br /> prime implicants of a function and then algorithms for finding minimum sum of products solutions. We will then extend the approaches<br /> to problems with multiple outputs.<br /> The first approach to finding prime implicants is referred to as the<br /> Quine-McCluskey method. It starts with minterms and uses, repeatedly,<br /> the adjacency property<br /> ab
ab  a<br /> <br /> The second approach is iterated consensus. It starts with any set of<br /> terms that cover the function and uses the consensus operation and the<br /> absorption property<br /> a
ab  a<br /> Each of these methods has been computerized and is effective for a<br /> larger number of variables than the Karnaugh map, although the amount<br /> of computing becomes excessive for many practical problems.<br /> <br /> 4.1<br /> <br /> QUINE-McCLUSKEY METHOD<br /> FOR ONE OUTPUT<br /> <br /> In this section, we will use the Quine-McCluskey method to list all of<br /> the prime implicants of a function. In Section 4.3, we will use that<br /> list to find the minimum sum of products expression(s) for that function.<br /> We start with a list of minterms, in numerical form (that is, 1 for an<br /> 211<br /> <br /> mar65164_ch04.qxd<br /> <br /> 212<br /> <br /> 12/2/03<br /> <br /> 1:11 PM<br /> <br /> Page 212<br /> <br /> Chapter 4<br /> <br /> Function Minimization Algorithms<br /> <br /> uncomplemented variable and 0 for a complemented one). If we start<br /> with minterm numbers, this is just the binary equivalent of the minterm<br /> number. We order this list by the number of 1’s in each terms. We will<br /> use the function of Example 3.4:<br /> f(w, x, y, z) 
m(0, 4, 5, 7, 8, 11, 12, 15)<br /> Our initial list, grouped by the number of 1’s, is<br /> A<br /> B<br /> C<br /> D<br /> E<br /> F<br /> G<br /> H<br /> <br /> 0000<br /> -------0100<br /> 1000<br /> -------0101<br /> 1100<br /> -------0111<br /> 1011<br /> -------1111<br /> <br /> where we have labeled the terms for easy reference.<br /> We now apply the adjacency property to each pair of terms. Since<br /> that property requires all the variables to be the same except for one, we<br /> need only consider terms in consecutive groups. We produce a second<br /> column of terms with one variable missing:<br /> A
B  J  0 – 0 0 (where the dash represents a missing<br /> variable)<br /> A
CK–000<br /> B
DL010–<br /> B
EM–100<br /> C
D  none<br /> C
EN1–00<br /> D
FO01–1<br /> D
G  none<br /> E
F  none<br /> E
G  none<br /> F
HP–111<br /> G
HQ1–11<br /> <br /> mar65164_ch04.qxd<br /> <br /> 12/2/03<br /> <br /> 1:11 PM<br /> <br /> Page 213<br /> <br /> Quine-McCluskey Method for One Output<br /> <br /> 4.1<br /> <br /> Whenever a term is used to produce another term, it is checked off; it is<br /> not a prime implicant. These (three literal) terms are placed in a second<br /> column as shown in Table 4.1. All of the minterms have been covered<br /> by at least one term in the second column; thus, no minterms are prime<br /> implicants.<br /> Table 4.1<br /> <br /> Quine-McCluskey prime implicant computation.<br /> <br /> A 0000√<br /> ------------B 0100√<br /> C 1000√<br /> ------------D 0101√<br /> E 1100√<br /> ------------F 0111√<br /> G 1011√<br /> ------------H 1111√<br /> <br /> J 0–00√<br /> K –000√<br /> ------------L 010–<br /> M –100√<br /> N 1–00√<br /> ------------O 01–1<br /> ------------P –111<br /> Q 1–11<br /> <br /> R ––00<br /> <br /> We now repeat the process with the second column. Again, we need<br /> only consider terms in consecutive sections of that column (number of<br /> 1’s differing by only one). Also, we need only consider terms with<br /> dashes in the same position, since they are the only ones with the same<br /> three variables. Thus, we find<br /> J
NR––00<br /> K
M  R (same term)<br /> There are no adjacencies between the second and third group or between<br /> the third and fourth group.<br /> Since there is only one term in the third column, we are done. If<br /> there were more terms, we would repeat the process, forming a column<br /> with three literals missing (corresponding to a group of eight minterms).<br /> The prime implicants are<br /> L<br /> O<br /> P<br /> Q<br /> R<br /> <br /> 0<br /> 0<br /> –<br /> 1<br /> –<br /> <br /> 1<br /> 1<br /> 1<br /> –<br /> –<br /> <br /> 0<br /> –<br /> 1<br /> 1<br /> 0<br /> <br /> –<br /> 1<br /> 1<br /> 1<br /> 0<br /> <br /> wxy<br /> wxz<br /> xyz<br /> wyz<br /> yz<br /> <br /> If there are don’t cares in the problem, all of them must be included,<br /> since don’t cares are part of prime implicants.<br /> <br /> 213<br /> <br /> mar65164_ch04.qxd<br /> <br /> 12/2/03<br /> <br /> 214<br /> <br /> 1:11 PM<br /> <br /> Page 214<br /> <br /> Chapter 4<br /> <br /> Function Minimization Algorithms<br /> <br /> g(w, x, y, z) 
m(1, 3, 4, 6, 11)

d(0, 8, 10, 12, 13)<br /> <br /> E X A M P L E 4.1<br /> <br /> The process proceeds as before<br /> 0000√<br /> -------0001√<br /> 0100√<br /> 1000√<br /> -------0011√<br /> 0110√<br /> 1010√<br /> 1100√<br /> -------1011√<br /> 1101√<br /> <br /> 000–<br /> 0–00√<br /> –000√<br /> -------00–1<br /> 01–0<br /> –100√<br /> 10–0<br /> 1–00√<br /> -------–011<br /> 101–<br /> 110–<br /> <br /> ––00<br /> <br /> Thus, the prime implicants are<br /> wxy<br /> wxz<br /> wxz<br /> wxz<br /> <br /> xyz<br /> wxy<br /> wxy<br /> yz<br /> <br /> Although wxy and wxz are prime implicants, they consist of all don’t cares<br /> and would never be used in a minimum solution. Indeed, as we will see in<br /> Section 4.3, only three of these are needed for a minimum solution.<br /> [SP 1; EX 1]<br /> <br /> This process works for larger number of variables, but the number<br /> of minterms and other implicants can increase rapidly. We will see one<br /> example with five variables in the solved problems. This process has<br /> been computerized.<br /> <br /> 4.2<br /> <br /> ITERATED CONSENSUS<br /> FOR ONE OUTPUT<br /> <br /> In this section, we will use the iterated consensus algorithm to list all of<br /> the prime implicants of a function. In the next section, we will use that<br /> list to find the minimum sum of products expression(s).<br /> To simplify the discussion, we will first define the relationship<br /> included in.<br /> Product term t1 is included in product term t2 (written t1  t2) if t2 is 1<br /> whenever t1 is 1 (and elsewhere, too, if the two terms are not equal).1<br /> 1<br /> <br /> The relationship included in is also applied to more complex functions than product<br /> terms, but that will not be important here.<br /> <br /> mar65164_ch04.qxd<br /> <br /> 12/2/03<br /> <br /> 1:11 PM<br /> <br /> Page 215<br /> <br /> 4.2<br /> <br /> Iterated Consensus for One Output<br /> <br /> All this really means for product terms is that either t1  t2, or t1  xt2,<br /> where x is a literal or a product of literals. From the perspective of the<br /> map, it means that t1 is a subgroup of t2. If an implicant, t1, is included in<br /> another implicant, t2, then t1 is not a prime implicant since<br /> t1
t2  xt2
t2  t2<br /> <br /> [P12a]<br /> <br /> The iterated consensus algorithm for single functions is as follows:<br /> 1.<br /> <br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> <br /> Find a list of product terms (implicants) that cover the function.<br /> Make sure that no term is equal to or included in any other term on<br /> the list. (These terms could be prime implicants or minterms or any<br /> other set of implicants. However, the rest of the algorithm proceeds<br /> more quickly if we start with prime implicants.)<br /> For each pair of terms, ti and tj (including terms added to the list in<br /> step 3), compute ti ¢ tj.<br /> If the consensus is defined, and the consensus term is not equal to<br /> or included in a term already on the list, add it to the list.<br /> Delete all terms that are included in the new term added to the list.<br /> The process ends when all possible consensus operations have<br /> been performed. The terms remaining on the list are ALL of the<br /> prime implicants.<br /> <br /> Consider the following function (Example 3.4 from Chapter 3 and<br /> the function we used to describe the Quine-McCluskey method in<br /> Section 4.1).<br /> f(w, x, y, z) 
m(0, 4, 5, 7, 8, 11, 12, 15)<br /> We chose as a starting point a set of product terms that cover the function; they include some prime implicants and a minterm, as well as other<br /> implicants.<br /> A<br /> B<br /> C<br /> D<br /> E<br /> <br /> wxyz<br /> wxy<br /> wyz<br /> xyz<br /> wyz<br /> <br /> We labeled the terms for reference and go in the order, B ¢ A, C ¢ B,<br /> C ¢ A, D ¢ C, . . . , omitting any computation when the term has been<br /> removed from the list. When a term is removed, we cross it out. The first<br /> consensus, B ¢ A, produces wyz; A is included in that term and can<br /> thus be removed. After the first step, the list becomes<br /> A<br /> B<br /> C<br /> <br /> wxyz<br /> wxy<br /> wyz<br /> <br /> D<br /> E<br /> F<br /> <br /> xyz<br /> wyz<br /> wyz<br /> <br /> 215<br /> <br />