Petrick's method

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Quine–McCluskey algorithm — The Quine–McCluskey algorithm (or the method of prime implicants) is a method used for minimization of boolean functions which was developed by W.V. Quine and Edward J. McCluskey. It is functionally identical to Karnaugh mapping, but the tabular… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Messerschmitt Bf 109 variants — Main article: Messerschmitt Bf 109 Bf 109 Bf 109G 10, with Erla Haube canopy and taller, wooden vertical fin/rudd …   Wikipedia

  • Lyme disease — Classification and external resources Nymphal and adult deer ticks can be carriers of Lyme disease. Nymphs are about the size of a poppy seed. ICD 10 A …   Wikipedia

  • Perfluorooctanoic acid — IUPAC name pentadecafluorooctanoic acid …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”