Petrick's method

Algorithm

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_1, P_2, P_3, P_4, etc.
3. 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.
4. Apply De Morgan's Laws to expand P into a sum of products and minimize by applying the absorption law 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, first find those terms which contain a minimum number of prime implicants.
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. Choose the term or terms composed of the minimum total number of literals, and write out the corresponding sums of prime implicants.

Pseudocode

The algorithm above can be implemented with the C# as shown below: private string DoPetriksMethod( Dictionary PIchart, List epis, List primeImplicants, List minterms) { PIchart = RemoveEPIs(PIchart, epis, minterms); string minimisedExpression; Dictionary termsImplicantMapping = MapTermsToImplicants(primeImplicants); List productOfSums = GetProductOfSums(termsImplicantMapping, PIchart); string[] sumOfproducts = GetSumOfProducts(productOfSums); string minProduct = GetMinProduct(sumOfproducts); minimisedExpression = GetFinalExpression(termsImplicantMapping, minProduct); return minimisedExpression; }

private static Dictionary MapTermsToImplicants(List primeImplicants) { var mapping = new Dictionary(); char minChar = (char)(primeImplicants[0].Length + 65); for (var i = 0; i { mapping.Add(minChar, primeImplicants[i]); minChar++; } return mapping; }

private static List GetProductOfSums(Dictionary termToImplicantMap, Dictionary primeImplicantChart) { var productOfSums = new List(); List sumsToAdd; string primeImplicant; foreach (string key in primeImplicantChart.Keys) { primeImplicant = primeImplicantChart[key]; for (var i = 0; i { if (primeImplicant[i] == '1') { sumsToAdd = GetSumsToAdd(primeImplicantChart, termToImplicantMap, key, i); AddSumsToList(productOfSums, sumsToAdd); } } } return productOfSums; }

private static void AddSumsToList(List productOfSums, List sumsToAdd) { foreach (Bracket s in sumsToAdd) { if (!productOfSums.Contains(s)) { productOfSums.Add(s); } } }

private static List GetSumsToAdd(Dictionary PIchart, Dictionary termToImplicantMap, string key, int positionWithinKey) { var sumsToAdd = new List(); Bracket sum; string implicant; char term1; char term2; for (var i = 0; i { implicant = PIchart.Keys.ToArray()[i]; if (PIchart[implicant][positionWithinKey] == '1') { term1 = GetTermFromImplicant(termToImplicantMap, key); term2 = GetTermFromImplicant(termToImplicantMap, implicant); if (term1 != term2) { sum = new Bracket(term1, term2); sumsToAdd.Add(sum); } } } return sumsToAdd; }

private static char GetTermFromImplicant(Dictionary termToImplicantMap, string implicant) { string[] implicants = termToImplicantMap.Values.ToArray(); char[] keys = termToImplicantMap.Keys.ToArray(); for (var i = 0; i { if (implicants[i] == implicant) { return keys[i]; } } throw new Exception("Could not map implicant to key"); }

private static string[] GetSumOfProducts(List productOfSums) { Bracket b1; Bracket b2; Bracket mergedTerm; bool merged = true; while (merged) { merged = false; for (var i = 0; i { for (var c = i + 1; c { b1 = productOfSums[i]; b2 = productOfSums[c]; if (b1.term1 == b2.term1 != (b1.term2 == b2.term2) != (b1.term1 == b2.term2) != (b1.term2 == b2.term1)) { mergedTerm = MergeBrackets(b1, b2); productOfSums.Add(mergedTerm); productOfSums.Remove(b1); productOfSums.Remove(b2); merged = true; i = c + 1; c = i + 1; } } } } List stringProducts = ConvertBracketsToString(productOfSums); List sumOfProducts = RecursiveDistributiveLaw(stringProducts); return sumOfProducts[0].ToArray(); }

private static Bracket MergeBrackets(Bracket b1, Bracket b2) { var b = new Bracket(); if (b1.term1 == b2.term1) { b.term1 = b1.term1; b.term2 = b1.term2 + b2.term2; return b; } else { b.term1 = b1.term2; b.term2 = b1.term1 + b2.term2; return b; } }

private static List ConvertBracketsToString(List brackets) { var result = new List(); List tmp; foreach (Bracket b in brackets) { tmp = new List { b.term1, b.term2 }; result.Add(tmp); } return result; }

private static List RecursiveDistributiveLaw(List brackets) { var lls = new List(); if (brackets.Count 1) { lls.Add(SingleDistributiveLaw(brackets[0], brackets[1])); brackets.RemoveAt(0); brackets.RemoveAt(0); lls.AddRange(brackets); return RecursiveDistributiveLaw(lls); } else { return brackets; } }

private static List SingleDistributiveLaw(List b1, List b2) { var lls = new List(); for (var i = 0; i { for (var j = 0; j { lls.Add(ApplyDistributiveLaw(b1[i], b2[j])); } } return lls; }

private static string ApplyDistributiveLaw(string a, string b) { string tempResult = a + b; string finalResult = ""; foreach (char c in tempResult) { if (!finalResult.Contains(c)) { finalResult += c; } } return finalResult; }

private static string GetMinProduct(string[] sumOfProducts) { string minProduct = sumOfProducts[0]; foreach (string p in sumOfProducts) { if (p.Length { minProduct = p; } } return minProduct; }

private string GetFinalExpression(Dictionary termToImplicantMap, string minProduct) { string subExpression; string implicant; string result = ""; for (var i = 0; i { implicant = termToImplicantMap[minProduct[i]]; subExpression = ConvertImplicantToExpression(implicant); result += subExpression; if (i { result += " + "; } } return result; }

The following code snippet assumes access to the bracket struct. struct Bracket { public Bracket(char term1, char term2) { // Sorting into alphabetical order. This can be done as OR is commutative. if (term1 { this.term1 = term1.ToString(); this.term2 = term2.ToString(); } else { this.term1 = term2.ToString(); this.term2 = term1.ToString(); } } // The two terms that make up the brackets. These are assigned to when the // product of sums is created in Petrick's method. public string term1; public string term2; }

Example of Petrick's method

Following is the function we want to reduce:

: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:

:{| class="wikitable" style="text-align:center;" |- ! || 0 || 1 || 2 || 5 || 6 || 7 || ⇒ || A || B || C

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.

Notes

References

References

1. (1977-04-01). "Analysis and Design of Sequential Digital Systems". [[The Macmillan Press Ltd.]].
2. (1992). "Fundamentals of Logic Design". West Publishing Company.
3. (1956-04-10). "A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants". [[Air Force Cambridge Research Center]].
4. "Biographical note".
5. (2006-08-05). "Obituaries - Cedar Rapids - Stanley R. Petrick". [[The Gazette (Cedar Rapids).
6. (2007). "Lecture #10: Petrick's Method". Department of Electrical and Computer Engineering, [[University of Idaho]].
7. (1974). "Logical Design of Switching Functions". [[Thomas Nelson and Sons Ltd]] / [[Van Nostrand Reinhold Co., Ltd.]].
8. (1962). "The reduction of redundancy in solving prime implicant tables". [[I.R.E. Transactions on Electronic Computers]].
9. (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.". [[Association for Symbolic Logic]] (ASL).
10. (2016). "Advanced Logical Circuit Design Techniques". [[Garland STPM Press]] (original issue) / WhitePubs Enterprises, Inc. (reissue).