Essential Prime Implicant with Don't Care

Discussion in 'Homework Help' started by Beyond.Multiverse, Aug 17, 2018.

  1. Beyond.Multiverse

    Thread Starter New Member

    Aug 17, 2018
    3
    0
    [​IMG]
    According to me, 3 is the number of Essential Prime Implicants.

    This is how minimal expression is obtained.
    [​IMG]


    Thus we have 5 Prime Implicants and 3 Essential Prime Implicants.
    [​IMG]

    One of my classmates is saying that number of Essential Prime Implicants is 2. We can't include don't cares even if they are a part of minimal expression.
    So, the number of Essential Prime Implicants is 2 or 3?
     
  2. WBahn

    Moderator

    Mar 31, 2012
    23,093
    6,946
    Ask your classmate to draw the two essential prime implicants as they see things. If they are correct, then all of the 1's in the function have to be covered because, by definition, any 1 that is NOT covered MUST be a member of an additional essential prime implicant.

    I could see someone claiming that there are four essential prime implicants if you aren't allowed to include don't cares.

    One thing to keep in mind is that the function definition INCLUDES the don't care designations -- not just the 1 and 0 designations. If you have two don't cares, what you are really saying is that your defined function can be any one of four functions and it doesn't matter which one. So the number of essential prime implicants is usually taken to mean the essential prime implicants for one of the allowed functions that has no more essential prime implicants than any of the others.
     
  3. Beyond.Multiverse

    Thread Starter New Member

    Aug 17, 2018
    3
    0
    He is not excluding don't cares altogether. He is saying that don't cares can be considered for forming Prime Implicant but not in Essential Prime Implicant even if they are not a part of any other Prime implicant. He finally says that there are 2 Essential Prime Implicants. y'w'x' and ywx' are those Essential Prime Implicants. But I am saying that there are 3 Essential Prime Implicants(y'w'x', ywx' and zx). He is arguing that zx is not an Essential Prime Implicant. So, my question, is zx an Essential Prime Implicant?
     
  4. WBahn

    Moderator

    Mar 31, 2012
    23,093
    6,946
    If (y'w'x') and (ywx') are the only two essential prime implicants, then all input conditions that must produce a 1 output must be covered by at least one of them. So which of them covers w'xy'z and which covers wxyz?
     
  5. Beyond.Multiverse

    Thread Starter New Member

    Aug 17, 2018
    3
    0
    He argued that "All input conditions that must produce a 1 output must be covered by at least one of the EPI" is false by giving the below K-Map as a counter example :
    [​IMG]
     
  6. WBahn

    Moderator

    Mar 31, 2012
    23,093
    6,946
    Okay, so let's look at that. I might well find myself in agreement with your classmate. I'm coming at this pretty blind as I don't recall us messing with these details (we might well have done so, but it then apparently had no practical impact on any of the circuits I designed in the decades sense -- which doesn't mean that it doesn't have practical implications, just that it didn't for me).

    So, by definition, a prime implicant (for a 1-based K-map) is product of inputs that can't be reduced and remain an implicant of the function.

    So I would agree that all five of the groupings above are, by definition, prime implicants.

    An essential prime implicant is a prime implicant containing a 1 term that is not covered by any other prime implicant. I just looked this up and it is a different definition than the one I looked up previously which stated that it contains a 1 not covered by another essential prime implicant. But the more I look the more I find that this definition was apparently in error.

    That being the case, I have to agree that the two blue groups are the only essential prime implicants. The red prime implicant is not because both of it's elements are covered by one of the black prime implicants and neither of the black prime implicants are essential because one of the 1's in each is covered by a blue prime implicant and the other is covered by the red one.

    I just dug out the text I used (Wakerly, Digital Design Principles and Practices, Prentice Hall. 1990, 1st ed) and it does spend some time on prime implicants. I don't recall to what degree we covered them, but the prof I had was pretty thorough, so I would bet we did. In reading it over, it does look somewhat familiar, so I think we did cover it (nearly 30 years ago), but I also think I see why it went out of my memory eventually -- and the author even states so directly: "In real logic-design applications, you are likely to encounter only two kinds of minimization problems: functions of a few variables that you can "eyeball" using the methods of this section, and more complex, multiple-output functions that are hopeless without the use of a minimization program." The methods developed based on the theoretical underpinnings of prime implicants, essential prime implicants, and secondary essential prime implints are easy enough to comprehend, retain, and apply that it quickly simply becomes second nature and so the detailed definitions slip away.

    So let's go back to the original problem and see where this all leads.

    prime_implicants.png

    I would say that all of these are prime implicants, including the blue one since we are allowed to treat the don't cares as 1's.

    But only the red ones are essential prime implicants. The two ones in the blue prime implicant are also covered by the green prime implicants. The fact that the 1's in the blue prime implicant are NOT covered doesn't matter since we are not required to treat the don't cares as 1's and including them in a prime implicant doesn't change that.

    The key is that any minimal-logic solution (where we are defining "minimal" in the normal way for a K-map based minimization) absolutely MUST include ALL essential prime implicants -- they are not in any way optional. So let's look at a case where treating the blue as an essential prime implicant would violate this touchstone.

    prime_implicants2.png
    In this case we have a minimal solution including JUST the prime implicants, which, by contradiction, means that the blue prime implicant CANNOT be an essential prime implicant.

    It also makes since that while all essential prime implicants MUST be including in ANY minimal solution, that it is NOT the case that ALL 1's in the function have to be covered by an essential prime implicant.
     
    Last edited: Aug 18, 2018
Loading...