Petrick's method
In Boolean algebra, Petrick's method (also known as the branch-and-bound method) is a technique for determining all minimum sum-of-products solutions from a prime implicant chart. Petrick's method is very tedious for large charts, but it is easy to implement on a computer.
- Reduce the prime implicant chart by eliminating the essential prime implicant rows and the corresponding columns.
- Label the rows of the reduced prime implicant chart , , , , etc.
- Form a logical function which is true when all the columns are covered. P consists of a product of sums where each sum term has the form , where each represents a row covering column .
- Reduce to a minimum sum of products by multiplying out and applying .
- Each term in the result represents a solution, that is, a set of rows which covers all of the minterms in the table. To determine the minimum solutions, first find those terms which contain a minimum number of prime implicants.
- Next, for each of the terms found in step five, count the number of literals in each prime implicant and find the total number of literals.
- Choose the term or terms composed of the minimum total number of literals, and write out the corresponding sums of prime implicants.
Example of Petrick's method (copied from http://www.mrc.uidaho.edu/mrc/people/jff/349/lect.10)
Following is the function we want to reduce:
The prime implicant chart from the Quine-McCluskey algorithm is as follows:
| 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
Based on the X marks in the table above, build a product of sums of the rows where each row is added, and columns are multiplied together:
(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)
Use the distributive law to turn that expression into a sum of products. Also use the following equivalences to simplify the final expression: X + XY = X and XX = X and X+X=X
= (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 + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ
Now use again the following equivalence to further reduce the equation: X + XY = X
= KNP + KLPQ + LMNP + LMQ + KMNQ
Choose products with fewest terms, in our example, there are two products with three terms:
KNP LMQ
Choose term or terms with fewest total literals. In our example, the two products both expand to 6 literals total each:
KNP expands to a'b'+ bc'+ ac LMQ expands to a'c'+ b'c + ab
So either one can be used. In general, application of Petricks method is tedious for large charts, but it is easy to implement on a computer.
External links
- Tutorial on Quine-McCluskey and Petrick's method (pdf).
- Prime Implicant Simplification Using Petrick’s Method