Lecture #10
** Petrick's Method
Petrick's method is a technique for finding all minimum
sum-of-products solutions from a prime implicant chart.
1. Remove all essential prime implicants and the minterms
they cover from the chart.
2. Label the rows of the reduced chart K, L, M, etc.
3. Form a logic function P that is true when all columns are
covered. P consists of a product of sum terms - one for
each column with at least one X.
4. Reduce P to a minimum sum of products by multiplying out and
applying X + XY = X.
5. Each term in the sum represents a solution. Choose the terms
with the fewest number of variables. Each of these terms
represents a solution with the minimum number of prime implicants.
6. Choose the remaining term or terms that correspond to the
fewest total number of literals.
f(a,b,c) = sum m(0,1,2,5,6,7)
| 0 1 2 5 6 7
---------------|------------
K (0,1) a'b' | X X
L (0,2) a'c' | X X
M (1,5) b'c | X X
N (2,6) bc' | X X
P (5,7) ac | X X
Q (6,7) ab | X X
Use (X + Y)(X + Z) = X + YZ and distributive law to multiply out.
P = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)
= (K+LM)(N+LQ)(P+MQ)
= (KN+KLQ+LMN+LMQ)(P+MQ)
= KNP + KMNP + LMNP + LMPQ +
KMNQ + KLMQ + LMNQ + LMQ
Use X + XY = X to reduce the equation.
P = KNP + KLPQ + LMNP + KMNQ + LMQ
Choose products with fewest terms.
KNP & LMQ
Choose term or terms with fewest total literals.
f(a,b,c) = a'b'+ bc'+ ac = a'c'+ b'c + ab
Application of Petricks method is tedious for large charts, but
it is easy to implement on a computer.
** Simplification of Incompletely Specified Functions
Treat X's as necessary minterms when finding prime implicants.
When forming the prime implicant chart, DO NOT include X minterms
on top.
Example:
f(a,b,c,d) = sum m(9,12,13,15) + sum d(1,4,5,7,8,11,14)
1 0001 (1,5) 0-01 (1,5,9,13) --01
4 0100 (1,9) -001 (1,9,5,13) --01
8 1000 (4,12) -100 (4,12,5,13) -10-
------- (8,9) 100- (8,9,12,13) 1-0-
5 0101 (8,12) 1-00 (8,12,9,13) 1-0-
9 1001 ------------ ----------------
12 1100 (5,7) 01-1 (5,7,13,15) -1-1
------- (5,13) -101 (5,13,7,15) -1-1
7 0111 (9,11) 10-1 (9,11,13,15) 1--1
11 1011 (9,13) 1-01 (9,13,11,15) 1--1
13 1101 (12,13) 110- (12,13,14,15) 11--
14 1110 (12,14) 11-0 (12,14,13,15) 11--
------- ------------
15 1111 (7,15) -111
(11,15) 1-11
(13,15) 11-1
(14,15) 111-
| 9 12 13 15
-----------------|-----------
K (1,5,9,13) | X X
L (4,12,5,13) | X X
M (8,9,12,13) | X X X
N (5,7,13,15) | X X
P (9,11,13,15) | X X X
Q (12,13,14,15) | X X X
P = (K+M+P)(L+M+Q)(K+L+M+N+P+Q)(N+P+Q)
= (K+M+P)(L+M+Q)(N+P+Q)
= (K+M+P)(Q+(N+P)(L+M))
= (K+M+P)(Q+LN+MN+LP+MP)
= KQ+KLN+KMN+KLP+KMP+
MQ+LMN+MN+LMP+MP+
PQ+LNP+MNP+LP+MP
Choose KQ, MQ, MN, MP, PQ, LP
c'd + ab, ac'+ ab, ac' + bd, ac'+ ad, ad + ab, bc' + ad
Each of these options is a minimum solution.