en>Awesomeaardvark at 07:22, 21 January 2014

2014-01-21T07:22:08Z

New page

In [[Boolean algebra (logic)|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 [[Quine–McCluskey algorithm|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 <math>P_1</math>, <math>P_2</math>, <math>P_3</math>, <math>P_4</math>, etc.
# Form a logical function <math>P</math> which is true when all the columns are covered. ''P'' consists of a product of sums where each sum term has the form <math>(P_{i0} + P_{i1} + </math><math>\cdots</math><math> + P_{iN})</math>, where each <math>P_{ij}</math> represents a row covering column <math>i</math>.
# Reduce <math>P</math> to a minimum sum of products by multiplying out and applying <math>X + XY = X</math>.
# 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:

:<math>f(A,B,C) =\sum m(0,1,2,5,6,7)\,</math>

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==
* [http://www.simpogical.com/download] Tutorial on Quine-McCluskey and Petrick's method (pdf).

{{DEFAULTSORT:Petrick's Method}}
[[Category:Boolean algebra]]

Disability-adjusted life year - Revision history

en>Awesomeaardvark at 07:22, 21 January 2014