Petrick's method

"Branch-and-bound method" redirects here. Not to be confused with Branch and bound.

In Boolean algebra, Petrick's method^[1] (also known as Petrick function^[2] or branch-and-bound method) is a technique described by Stanley R. Petrick (1931–2006)^[3][4] in 1956^[5][6] for determining all minimum sum-of-products solutions from a prime implicant chart.^[7] Petrick's method is very tedious for large charts, but it is easy to implement on a computer.^[7] The method was improved by Insley B. Pyne and Edward Joseph McCluskey in 1962.^[8][9]

Algorithm

1. Reduce the prime implicant chart by eliminating the essential prime implicant rows and the corresponding columns.^[7]
2. Label the rows of the reduced prime implicant chart ${\displaystyle P_{1}}$, ${\displaystyle P_{2}}$, ${\displaystyle P_{3}}$, ${\displaystyle P_{4}}$, etc.^[7]
3. Form a logical function ${\displaystyle P}$ which is true when all the columns are covered. P consists of a product of sums where each sum term has the form ${\displaystyle (P_{i0}+P_{i1}+}$${\displaystyle \cdots }$${\displaystyle +P_{iN})}$, where each ${\displaystyle P_{ij}}$ represents a row covering column ${\displaystyle i}$.^[7]
4. Apply De Morgan's Laws to expand ${\displaystyle P}$ into a sum of products^{[nb 1]} and minimize by applying the absorption law ${\displaystyle X+XY=X}$.^[7]
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, first find those terms which contain a minimum number of prime implicants.^[7]
6. 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.^[7]
7. Choose the term or terms composed of the minimum total number of literals, and write out the corresponding sums of prime implicants.^[7]

Example of Petrick's method

Following is the function we want to reduce:^[10]

${\displaystyle f(A,B,C)=\sum m(0,1,2,5,6,7)=A'B'C'+A'B'C+A'BC'+AB'C+ABC'+ABC}$

The prime implicant chart from the Quine-McCluskey algorithm is as follows:

	0	1	2	5	6	7	⇒	A	B	C
K = m(0,1)							⇒	0	0	—
L = m(0,2)							⇒	0	—	0
M = m(1,5)							⇒	—	0	1
N = m(2,6)							⇒	—	1	0
P = m(5,7)							⇒	1	—	1
Q = m(6,7)							⇒	1	1	—

Based on the ✓ marks in the table above, build a product of sums of the rows. Each column of the table makes a product term which adds together the rows having a ✓ mark in that column:

 (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 this example, there are two products with three terms:

 KNP
 LMQ

Referring to the prime implicant table, transform each product by replacing prime implicants with their expression as boolean variables, and substitute a sum for the product. Then choose the result which contains the fewest total literals (boolean variables and their complements). Referring to our example:

KNP    expands to    A'B' + BC' + AC   where K converts to A'B', N converts to BC', etc.
LMQ    expands to    A'C' + B'C + AB

Both products expand to six literals each, so either one can be used. In general, application of Petrick's method is tedious for large charts, but it is easy to implement on a computer.^[7]

Notes

1. This causes exponential blow-up in the number of columns: expanding the product of ${\displaystyle k}$ sums that have ${\displaystyle n_{1},n_{2},...,n_{k}}$ terms generally results in a sum with ${\displaystyle n_{1}n_{2}...n_{k}}$ terms.

References

1. Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977-04-01). "2.3.6. Selection of required prime implicants". Analysis and Design of Sequential Digital Systems. Electrical and Electronic Engineering (1 ed.). London & Basingstoke, UK: The Macmillan Press Ltd. pp. 19, 77. doi:10.1007/978-1-349-15757-0. ISBN 0-333-19266-4. Archived from the original on 2020-04-30. Retrieved 2020-04-30. (4+viii+146+6 pages)
2. Svoboda, Antonín; White, Donnamaie E. (2016) [2012, 1985, 1979-08-01]. "9.9. The Petrick function solution for the minimal ΣΠ-form of y" (PDF). Advanced Logical Circuit Design Techniques (PDF) (retyped electronic reissue ed.). Garland STPM Press (original issue) / WhitePubs Enterprises, Inc. (reissue). pp. 148–150. ISBN 978-0-8240-7014-4. LCCN 78-31384. Archived (PDF) from the original on 2017-04-14. Retrieved 2017-04-15. [1] [2]
3. "Biographical note". Archived from the original on 2017-04-13. Retrieved 2017-04-12. Stanley R. Petrick was born in Cedar Rapids, Iowa on August 16, 1931. He attended the Roosevelt High School and received a B. S. degree in Mathematics from the Iowa State University in 1953. During 1953 to 1955 he attended MIT while on active duty as an Air Force officer and received the S. M. degree from the Department of Electrical Engineering in 1955. He was elected to Sigma Xi in 1955.
   Mr. Petrick has been associated with the Applied Mathematics Board of the Data Sciences Laboratory at the Air Force Cambridge Research Laboratories since 1955 and his recent studies at MIT have been partially supported by AFCRL. During 1959–1962 he held the position of Lecturer in Mathematics in the Evening Graduate Division of Northeastern University.
   Mr. Petrick is currently a member of the Linguistic Society of America, The Linguistic Circle of New York, The American Mathematical Association, The Association for Computing Machinery, and the Association for Machine Translation and Computational Linguistics.
4. "Obituaries - Cedar Rapids - Stanley R. Petrick". The Gazette. 2006-08-05. p. 16. Archived from the original on 2017-04-13. Retrieved 2017-04-12. [...] CEDAR RAPIDS Stanley R. Petrick, 74, formerly of Cedar Rapids, died July 27, 2006, in Presbyterian/St. Luke's Hospital, Denver, Colo., following a 13-year battle with leukemia. A memorial service will be held Aug. 14 at the United Presbyterian Church in Laramie, Wyo., where he lived for many years. [...] Stan Petrick was born in Cedar Rapids on Aug. 6, 1931 to Catherine Hunt Petrick and Fred Petrick. He graduated from Roosevelt High School in 1949 and received a B.S. degree in mathematics from Iowa State University. Stan married Mary Ethel Buxton in 1953.
   He joined the U.S. Air Force and was assigned as a student officer studying digital computation at MIT, where he earned an M.S. degree. He was then assigned to the Applied Mathematics Branch of the Air Force Cambridge Research Laboratory and while there earned a Ph.D. in linguistics.
   He spent 20 years in the Theoretical and Computational Linguistics Group of the Mathematical Sciences Department at IBM's T. J. Watson Research Center, conducting research in formal language theory. He had served as an assistant director of the Mathematical Sciences Department, chairman of the Special Interest Group on Symbolic and Algebraic Manipulation of the Association for Computing Machinery and president of the Association for Computational Linguistics. He authored many technical publications.
   He taught three years at Northeastern University and 13 years at the Pratt Institute. Dr. Petrick joined the University of Wyoming in 1987, where he was instrumental in developing and implementing the Ph.D. program in the department and served as a thesis adviser for many graduate students. He retired in 1995. [...] (NB. Includes a photo of Stanley R. Petrick.)
5. Petrick, Stanley R. (1956-04-10). A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants. Bedford, Cambridge, Massachusetts, USA: Air Force Cambridge Research Center. AFCRC Technical Report TR-56-110.
6. Lewin, Douglas (1974) [1968]. Logical Design of Switching Functions (1981 7th reprinted edition of the 2nd ed.). Thomas Nelson and Sons Ltd / Van Nostrand Reinhold Co., Ltd. p. 60. ISBN 0-442-30747-0. ISBN 0-17-771044-6. NCN 420-5805-4.
7. Roth, Jr., Charles H. (1992). Fundamentals of Logic Design (4 ed.). West Publishing Company. ISBN 0-31492218-0.
8. Pyne, Insley B.; McCluskey, Jr., Edward Joseph (1962). "The reduction of redundancy in solving prime implicant tables". I.R.E. Transactions on Electronic Computers. EC-11 (4): 473–482.
9. Choudhury, Arun K. (February 1968). "I. B. Pyne and E. J. McCluskey Jr., The reduction of redundancy in solving prime implicant tables. IRE transactions on electronic computers, vol. EC-11 (1962), pp. 473–482". The Journal of Symbolic Logic. Reviews. 32 (4). Association for Symbolic Logic (ASL): 540–541. doi:10.2307/2270229. JSTOR 2270229. S2CID 57871609.
10. Frenzel, James "Jim" F. (2007). "Lecture #10: Petrick's Method". ECE 349 – Background Study in Digital Computer Fundamentals. Moscow, Idaho, USA: Department of Electrical and Computer Engineering, University of Idaho. Archived from the original on 2017-04-12. Retrieved 2019-08-08. [3]

Further reading

• Krambeck, Donald (2016-02-17). "Prime Implicant Simplification Using Petrick's Method". All About Circuits. EETech Media, LLC. Archived from the original on 2017-04-12. Retrieved 2020-04-03.
• Petrick, Stanley R. (1965). A Recognition Procedure for Transformational Grammars (PhD thesis). Massachusetts Institute of Technology.
• Bolton, Martin (1990). "4. Minimization". Written at University of Bristol, Bristol, UK. In Dagless, Erik L. (ed.). Digital Systems Design with Programmable Logic. Electronic Systems Engineering Series (1 ed.). Wokingham, UK: Addison-Wesley Publishers Ltd. pp. 100–101, 115. ISBN 0-201-14545-6. LCCN 90000007. ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r. Retrieved 2021-04-17. (xiv+379+1 pages)

External links

• Tutorial on Quine-McCluskey and Petrick's method
• Petrick C++ implementation based on the tutorial above