Petrick's Method

Pre: Tabular Method

After applying row and column dominance, if the cover table is not empty, then use Petrick's method to find necessary, non-essential prime implicants for a minimum-cost implementation. Petrick's method is tedious but easy to program on a computer.

Procedure

  1. Form a logic function which is true when all columns are covered
    1. For each column, form a sum of the prime implicants (i.e do a logical OR on the prime implicants that have check marks in the column)
    2. Do a logical AND on all these sums to obtain a POS expression
  2. Reduce the POS to a minimum SOP
    • This can be done by multiplying out and applying the properties and
    • Each product term of the SOP represents a solution (a set of prime implicants which covers all the minterm in the table)
  3. Determine the minimum solutions
    1. Find the product terms which contain a minimum number of prime implicants
    2. For each of the terms found above, count the number of literals in each prime implicant and find the total number of literals
  4. Chose the term(s) composed of the minimum total number of literals, and write out the corresponding sums of prime implicants

Example

Consider the function . Given the initial cover table:

Prime Implicants
✓ ✓
✓ ✓
✓ ✓
✓ ✓
✓ ✓

Find necessary prime implicants.

solution
Note that there are no essential prime implicants in this table.
Applying Petrick's method, we first form the following sums of PIs and then a POS:

  • :
  • :
  • :
  • :

The resulting POS is .

Simplifying:

Among the five products, and have the minimum number of prime implicants. Thus we see that the minimum cost covers are either or . That is,