Quine Cluskey Thuật toán

Chapter 4


Quine McClusky Method

Quine-McCluskey Method
Group

Common

Table
Quine-McCluskey Method for Generating Prime Implicants
Group minterms by the number of 1’s

Apply adjacency (a b′ + a b = a) to each pair of terms, forming a second list. Check those terms in the first list that are covered by the new terms. Note that only terms in adjacent groups (that differ by one 1) need be paired.

Repeat process with second list (and again if multiple terms are formed on a third list).
The iterated consensus algorithm for single functions is as follows:
1. Find a list of product terms (implicants) that cover the function. Make sure that no term is equal to or included in any other term on the list. (These terms could be prime implicants or minterms or any other set of implicants. However, the rest of the algorithm proceeds more quickly if we start with prime implicants.)
2. For each pair of terms, ti and tj (including terms added to the list in step 3), compute ti ¢ tj.
3. If the consensus is defined, and the consensus term is not equal to or included in a term already on the list, add it to the list.
4. Delete all terms that are included in the new term added to the list.
5. The process ends when all possible consensus operations have been performed. The terms remaining on the list are ALL of the prime implicants.
A + C + E + G
A + F + B + D
(E + F)(F + G)(B + G)(D + E)(C + D)(B + C)
= (F + EG)(B + CG)(D + CE)
= (BF + BEG + CFG + CEG)(D + CE)
= BDF + BDEG + CDFG + CDEG + BCEF + BCEG + CEFG + CEG
Petrick’s Method
f(a, b, c) = m(2, 3, 7)
g(a, b, c) = m(4, 5, 7)
a b c g 0 1 0 – 0
a b c g 0 1 1 – 0
a b c f  1 0 0 0 –
a b c f  1 0 1 0 –
a b c 1 1 1 – 
f = ab + abc
g = ab + abc
f(a, b, c, d) = m(2, 3, 4, 6, 9, 11, 12) + d(0, 1, 14, 15)
g(a, b, c, d) = m(2, 6, 10, 11, 12) + d(0, 1, 14, 15)
f = bd + abd + ad
g = ac + abd + cd