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.