Digital-Grand Test -Q3

Question

Consider two 2-bit numbers and . The value of a 2-bit number is defined as : 

Assume that A and B are such that . A four-variable function is to have value 1 whenever , and value 0 otherwise. 

The number of prime implicants and essential prime implicants for this function f, respectively, are

(A). 5,5

(B). 5,4

(C). 6,5

(D). 6,4

Answer 1

Assume that A and B are such that  .

This means that the inputs when A and B are such that   can not occur. So, when A=3,B=0 Or A=0,B=3, then for these inputs output of this function is Don't-care.

 A four-variable function  is to have value 1 whenever  , and value 0 otherwise. 

So the K-map will be as follows :

PI are as follows : 

1. Cell (2,3,10,11)  [Also an EPI, covers minterm 10 uniquely ]

2. Cell(3,5,11,15)  [Also an EPI, covers minterm 15 uniquely]

3. Cell (2,3,6,7)   [Also an EPI, covers minterm 6 uniquely]

4. Cell (1,3,5,7)   [Also an EPI, covers minterm 5 uniquely]

5. Cell (0,1,2,3 )  [Also an EPI, covers minterm 0 uniquely] 

6. Cell (12)  [NOT an EPI because it doesn't cover a "1" uniquely]

So, 6 PI, 5 EPI.

NOTE that in finding PI, we consider don't cares as if they were 1's.

 

---

---

Some Extra Notes :

Don't Cares :

For invalid input values, we don't care what the output value is Or we simply don't care what the output value is for a particular input value.

K-map :

To Find prime implicants (pretend don’t care cells set to 1) 

To Find essential prime implicants (discount don’t care cells) 

In the process of finding prime implicants, don’t-cares are treated just like 1’s. However, a prime implicant composed entirely of don’t-cares can never be part of the minimum solution.

One way of finding essential prime implicants on a map is simply to look at each 1 on the map that has not already been covered, and check to see how many prime implicants cover that 1. If there is only one prime implicant which covers the 1, that prime implicant is essential. 

If a don’t-care minterm is present on the map, we do not have to check it to see if it is covered by one or more prime implicants.

https://user.eng.umd.edu/~danadach/ENEE_244_Fall_15/lec_10_notes.pdf

https://electronics.stackexchange.com/questions/391206/prime-implicant/391220#391220

https://electronics.stackexchange.com/questions/391556/number-of-prime-implicants

https://cse.sc.edu/~hoskinsw/classes/csce211/LecturesF15/Lecture8.pdf

---

Read the discussion on this thread (Soumya and Arjun sir's comments specifically)

https://gateoverflow.in/233283/pi-and-epi-in-case-of-dont-care

Note that : "As per standard reference we do include only don't cares also as prime implicants - definition of PI is modified in presence of don't cares"

At many places, the definition of PI that you read is for the case when Don't cares are Not present. Definition of PI is modified in presence of don't cares.

---

Definitions in case of NO Don't cares :

An implicant of a function is a product term that can be used in an SOP expression for that function. From the point of view of the map, an implicant is a rectangle of 1,2,4,8... 1’s. No 0’s may be included.

A prime implicant is an implicant that (from the point of view of the map) is not fully contained within any one other implicant.

An essential prime implicant is a prime implicant that includes at least one 1 that is not in any other prime implicant.

Definitions in case of Don't cares :

Implicants can have don’t cares in them too.

An implicant is a rectangle of 1, 2, 4, 8, … 1’s or X’s .

A prime implicant is a rectangle of 1, 2, 4, 8, … 1’s 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.

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