Petrick's method

From Wikipedia, the free encyclopedia

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.

1. Reduce the prime implicant chart by eliminating the essential prime implicant rows and the corresponding columns.
2. Label the rows of the reduced prime implicant chart P₁, P₂, P₃, P₄, etc.
3. Form a logical function P which is true when all the columns are covered. P consists of a product of sums, each sum term having the form (P_i0 + P_i1 + ...), which represents the rows which cover column i.
4. Reduce P to a minimum sum of products by multiplying out and applying X + XY = X.
5. 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, find those terms which contain a minimum number of prime implicants.
6. For each of the terms found in step 5, count the number of literals in each prime implicant and find the total number of literals. Choose the term or terms which correspond to the minimum total number of literals, and write out the corresponding sums of prime implicants.

[edit] See also

• Quine-McCluskey algorithm