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

Chapter 4: Function minimization algorithms. Quine mccluskey method for one output, iterated consensus for one output, prime implicant tables for one output, quine mccluskey for multiple output problems, iterated consensus for multiple output problems, prime implicant tables for multiple output problems, solved problems, exercises7 | 12/2/03 1:11 PM Page 211 C h a p t e r 4 Function Minimization Algorithms I n this chapter, we will look at two approaches to finding all of the prime implicants of a function and then algorithms for finding minimum sum of products solutions. We will then extend the approaches to problems with multiple outputs. The first approach to finding prime implicants is referred to as the Quine-McCluskey method. It starts with minterms and uses, repeatedly, the adjacency property ab ab a The second approach is iterated consensus. It starts with any set of terms that cover the function and uses the consensus operation and the absorption property a ab a Each of these methods has been computerized and is effective for a larger number of variables than the Karnaugh map, although the amount of computing becomes excessive for many practical problems. QUINE-McCLUSKEY METHOD FOR ONE OUTPUT In this section, we will use the Quine-McCluskey method to list all of the prime implicants of a function. In Section , we will use that list to find the minimum sum of products expression(s) for that function. We start with a list of minterms, in numerical form (that is, 1 for an 211 212 12/2/03 1:11 PM Page 212 Chapter 4 Function Minimization Algorithms uncomplemented variable and 0 for a complemented one). If we start with minterm numbers, this is just the binary equivalent of the minterm number. We order this list by the number of 1’s in each terms. We will use the function of Example : f(w, x, y, z) m(0, 4, 5, 7, 8, 11, 12, 15) Our initial list, grouped by the number of 1’s, is A B C D E F G H 0000 -------0100 1000 -------0101 1100 -------0111 1011 -------1111 where we have labeled the terms for easy reference. We now apply the adjacency property to each pair of terms. Since that property requires all the variables to be the same except for one, we need only consider terms in consecutive groups. We produce a .