The Gateway to Computer Science Excellence
+1 vote
201 views

in Digital Logic by Boss (11.5k points) | 201 views

1 Answer

+5 votes
Best answer

A prime implicant is a rectangle of 1, 2, 4, 8... or X’s not included in any one larger rectangle. Thus, from the point of view of finding prime implicants, X’s (don’t cares) are treated as 1’s.

Here the ones in RED and GREEN color are the PIs.
 


An essential prime implicant is a prime implicant that covers at least one 1 that is not covered by any other prime implicant. Don’t cares (X’s) do not make a prime implicant essential.

The 1's marked by STAR can't be covered by any other PI. So the PI to which they belong are EPIs. They are 2 in number.

The larger rectangle of size 4 shouldn't be counted as an EPI because all the 1's are already covered by other PIs (marked by GREEN). The don't cares are not covered but that is not what we see while checking for EPI.

You may be having a doubt that the 1's in 4 sized rectangle are not covered by max sized PI so that should also be EPI but EPI is not defined in such a way. Please refer the link below. I actually didn't know this and thought no. of EPI is 3 but going by the definition and the link I got to know this now. 

EPI=2 ( the solution given by ME is wrong i guess :/ )

Ref: https://gateoverflow.in/138655/prime-implicants-and-essential-prime-impliccants

 

by Boss (23.5k points)
selected by
+1
but other than donot care middle prime implicant also not possible

So, I guess 3
0
This is what i was getting, but some people argued otherwise.
0
3 is correct
+1
What is wrong with MiniPanda's explanation?
0
If a don't care is used in getting minimal solution, then the group with that don't care can also be considered as EPI(provided it is grouped only once). Don't care must be included to form a quad. That quad is necessary to form Minimal Expression.
0

This is how we get minimal expression.

0

Thus we have 5 Prime Implicants and 3 Essential Prime Implicants

0
@Balaji Any reference for including the quad with dont cares in EPI?
0
Sir if donot care we donot consider, then EPI will be 4

because then we not considering middle quad
0
How?

Wrt GREEN bordered PI, all the 1's there are covered by other PIs( one 1 is covered by RED quad and other 1 is covered by RED pair) . So GREEN PI can't be called EPI.
0

@MiniPanda

https://en.wiktionary.org/wiki/essential_prime_implicant

definition of EPI is

prime implicant on a Karnaugh map which "covers" at least one 1 which is not covered by any other prime implicant.

It doesnot requirs prime implicants to be all 1

middle quad has atleast one 1

right? 

+1
@srestha All '1s' in the middle quad is covered by some other prime implicants rt? So, can you give at least one '1' in the middle quad which satisfies the requirement for EPI?
+2
Middle quad has total of 2 1's. But both of them are covered by other PI (green PI).

Green pi also has two 1's. Both of them are covered by other PI (one by red quad and other by red pair).

Red pair PI has two 1's. One of them is covered by green PI. But the other 1 is not covered by any other PI. So these two red pair PIs are EPI.
0
yes, It need to searching for each 1 and if any one 1 covered by only one PI, then it will be EPI
+1
@Balaji , if you are not convinced , then you can use Quine–McCluskey algorithm . This is also a method to find EPIs. it will take 5-10 minutes but will give the answer as 2.
0

I believe Tabulation method gives PI = 5 and EPI = 2. As per Morris Mano, while calculating EPI, we don't take don't care in the table.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,220 comments
104,907 users