Prime Implicant Simplification Using Petrick’s Method

What is Petrick's Method?

Petrick's Method is used for determining minimum sum-of-product (SOP) solutions in a given prime implicants chart. Petrick's Method is another method used in Boolean Algebra, a simplification method used for complex circuits. Illustrated in Table 1.1 is an example that has two minimum solutions. If the number of variables increase in a given function, the number of prime implicants and complexity of the prime chart can increase drastically. In these types of cases, trial and error might be the best bet to find all of the minimum solution(s). The method mentioned in the previous article was a good way to find all the minimum solutions from a chart, but Petrick's method has a much better systematic approach. Before attempting to execute Petrick's method, all of the essential prime implicants; as well as the minterms they are covering need to be taken out of the prime implicants chart.

Table 1.1

To grasp this concept fully, Table 1.1 will be used to illustrate Petrick's method. To start, each row on the table (P₁, P₂, P₃) will need to be labeled. A logic function, P, will be formed, which holds true when all minterms have been covered up. This allows P₁ to be a logic variable, which is true if the prime implicants in the P₁ row are included in the solution. P₂ should also be a logic variable, which is true when the prime implicants in the P₂ row are included in the solution, etc. Looking at column 0, it appears that this column has X's in rows P₁ and P₂; so rows P₁ and P₂ must be chosen to cover the minterm 0. Now, in order to cover the next minterm, minterm 1, rows P₃ or P₁ must be chosen; therefore, (P₁ + P₃) must hold to be true. Likewise, in order to cover minterm 2, (P₂ and P₄) must also hold true. To easily cover the minterms 5, 6, and 7, expression (P₃ + P₅), (P₄ + P₆), and (P₅ + P₆) must hold to be true. Since all of the minterms need to be covered in order apply Petrick's method, the function below must hold true:

P = (P₁ + P₂)(P₁ + P₃)(P₂ + P₄)(P₃ + P₅ )(P₄ + P₆)(P₅ + P₆) = 1, What this means is that rows P₁ or P₂ need to be chosen, and row P₁ or P₃, and row P₂ or P₄, et al. 

Next, P needs to be completely reduced to a minimum SOP. This is relatively easy due to the fact that there are no compliments of the expression. After multiplying out, using the Boolean algebra rule (X + Y)(X + Z) = X + YZ, as well as the distributive law, the function below is as follows:

P = (P₁ + P₂P₃)(P₄ + P₂P₆)(P₅ + P₃P₆)

= (P₁P₄ + P₁P₂P₆ + P₂P₃P₄ + P₂P₃P₆)(P₅ + P₃P₆)

= P₁P₄P₅ + P₁P₂P₅P₆ + P₂P₃P₄P₅ + P₂P₃P₅P₆ + P₁P₃P₄P₆ + P₁P₂P₃P₆ + P₂P₃P₄P₆ + P₂P₃P₆

After this, using X + XY = X to remove redundant terms from the logic function P, the following function is produced:

P = P₁P₄P₅ + P₁P₂P₅P₆ + P₂P₃P₄P₅ + P₁P₃P₄P₅ + P₁P₃P₄P₆ + P₂P₃P₆

Now because P must hold true (or P = 1) to cover every minterm, the function can be described as follows. To completely cover every minterm, rows P₁ and P₄ and P₅ must be chosen, or rows P₁ and P₂ and P₅ and P₆, or rows P₂ and P₃ and P₆. Even though there are a total of five solutions for which the minimum number of prime implicants can be obtained by, the only two solutions chosen are rows P₁, P₄, and P₅ or rows P₂, P₃, and P₆. Choosing the first set provides F = a'b'  + bc' + ac, and the second with F = a'c' + b'c + ab, which are written as the two minimum SOP solutions.

 

Petrick's method summarized, is as follows: 

1. Start by reducing the prime implicants chart; this can be done by removing any essential prime implicants row and the columns corresponding. 
2. Each row that has been reduced in the prime implicants chart needs to be labeled, P₁, P₂, P₃, et al.
3. A logic function P is formed, which holds true when all columns are covered. This function is comprised of a product of sum terms, where each sum term has the form (P_i0 + P_i1 + ...), where P_i0, P_i1 ... indicate the rows which cover the i column. 
4. The logic function P needs to be reduced to a minimum sum of products by multiplying outward and applying the Boolean algebra rule X + XY = X. 
5. Each term in the resulting function represents a solution, or, a set of rows that cover all minterms in the prime implicants chart. To determine what the minimum solutions are, terms that contain a minimum number of variables are chosen. Each of these terms represents a solution with minimal numbers of prime implicants.
6. For each term found, the number of literals in each prime implicants is counted and noted for. The term(s) that correspond to the minimum total number of literals are chosen, and then the corresponding sums of prime implicants are written out accordingly. 

This method is very tedious for rather large charts, but on the other hand, it is easily implementable on a personal computer.

 

Simplifying with Quine-McCluskey Method

When presented with a function that is incompletely specified, the proper assignment of values to the don't-care terms is necessary if a minimum form for the function wants to be obtained. Below, the Quine-McCluskey method will be modified and used to obtain a minimum solution when any don't-care terms exist. During the process, don't-care terms, when present, will be treated as though they are required minterms. By doing so, the two can combine together with additional minterms to remove literals, if they are available. Extra prime implicant(s) may be generated from don't cares, this is okay because the extra prime implicant(s) will be removed in the next step of the process. While forming a prime implicants chart, the don't-cares are not written at the top. This is done to ensure that all of the required minterms are completely covered by one of the selected prime implicants when solving the chart. Still, the don't-care terms are not included in the solution at the end unless they have already been used in the process of forming a selected prime implicant. An example of simplifying a function that is incompletely specified is shown to provide a better understanding of what's just been explained.

F(A,B,C,D)=∑m(2,3,7,9,11,13)+∑d(1,10,15)

(The summation of d and its terms are don't-care terms)

Now to find the prime implicants:

The columns that have don't-care terms are removed when the following chart is formed:

* denotes an essential prime implicant

F = B'C + CD + AD

Noting that even though the original function given was incompletely specified, this final expression for F is simplified, and is defined for all possible values for A, B, C and D, thus is completely specified. Through this method, values have been automatically assigned to the don't-cares in the truth table for F that was originally provided. By replacing each and every term in the final expression for F (shown above) with its corresponding sum of minterms, the expression can be written as follows:

F  = (m₂ + m₃ + m₁₀ + m₁₁) + (m₃ + m₇ + m₁₁ + m₁₅) + (m₉ + m₁₁ + m₁₃ + m₁₅)

When m₁₀ and m₁₅ appear in this expression and m₁ does not, this insinuates that the don't-care terms in the truth table originally given for F have been denoted as follows:

for ABCD = 0001; F = 0;     for 1010, F = 1;     for 1111, F = 1

 

Coming Up

As of now, you should have an understanding of what Petrick's method is, how to apply it, and how to simplify incompletely specified functions using the Quine-McCluskey method. The Quine-McCluskey method can be used with a digital computer to simplify functions with up to 15 or more variables. Next, a method of map-entered variables will be used to find a minimum SOP expression of a given function.