Search code examples
cpu-architecturedigital-logicvlsidigital-design

Number of Prime Implicant and EPI

My TA solve this problem, Number of Prime Implicant (PI) for 

f(a,b,c,d)= Sigma m(0,2,4,5,8,10,11,13,15)

is 7 and number of Essential PI (EPI) is 1. how this will be calculated? I think it's wrong. any idea?

My solution is :

enter image description here

Solution

  • In order to provide you more of a learning opportunity, I will do the process for determining PI and EPI graphically on another function, similar to yours. You can use the exact same method to then solve the numbers for function you gave in your question. Note, there are multiple ways to determine PI and EPI, but I like the Kmap method as it illustrates the concept nicely. [NOTE: After the OP adding his solutions, I amended my answer to include the original function]

    Example:

    Lets say we have this function:

    g(a,b,c,d) = Sigma m(0,4,7,9,10,11,12,13,15)

    And we want to determine the number of Prime Implicants (PI) and Essential Prime Implicants (http://en.wikipedia.org/wiki/Implicant).

    The first step is to generate the Kmap (http://en.wikipedia.org/wiki/Karnaugh_map) for the given function (as it is given as the sum of min terms, fill the spot in the Kmap with 1s that form the binary representation of the given list of terms):

    Kmap Uncovered

    Now we have to find the largest coverings for all the terms of the Kmap. The number of these largest covers is the number of PI and each largest covering is a prime implicant (ie, a implicant, or partial function, that cannot be further simplified with any other implicant to form a more general implicant, or bigger covering). Such a covering is like this:

    Kmap Covered

    Now that we have the covering, we can count these largest coverings. There are 6, so there are 6 PIs and these coverings represent them. Now, to get the number of EPI, we need to look and see how many terms in our Kmap are covered by one and only one covering. Looking over the terms, these are 0 (covered only by blue), 7 (covered only by green), 9 (covered only by orange), and 10 (covered only by cyan). Thus, there are 4 EPIs.

    Now, try this method on your problem and see what numbers you get!

    [Update: Heres the information about your solution]

    Both you Kmap and covering seems good to me:

    OP Kmap

    As you can see from your covering, there are 7 total coverings of largest size; 6 along the diagonal and 1 large one covering the four corners. Thus, as described above, there are 7 PIs. To get the EPIs, we need to see how many of these PIs uniquely cover one of the terms, ie find terms covered by one and only one of our PIs, and those are the EPIs. Looking at the Kmap, only the corners with terms 8 and 2 are solely covered by one PI (ie, the 4 corners covering). While there are two terms, they share the save covering, and remember that coverings are implicants. So, as there is only one covering including terms covered by one and only one covering, there is only 1 EPI. (So, your TA was correct; 7 PIs, and 1 EPI).