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 $P\_1$, $P\_2$, $P\_3$, $P\_4$, etc.
# Form a logical function $P$ which is true when all the columns are covered. "P" consists of a product of sums where each sum term has the form $(P\_\{i0\}\; +\; P\_\{i1\}\; +$$cdots$$+\; P\_\{iN\})$, where each $P\_\{ij\}$ represents a row covering column $i$.
# Reduce $P$ to a minimum sum of products by multiplying out and applying $X\; +\; XY\; =\; X$.
# 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:

:$f(A,B,C,D)\; =sum\; m(0,1,2,5,6,7),$

The prime implicant chart from 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 + KMNP + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ Now use again the following equivalence to further reduce the equation: X + XY = X = KNP + 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.