• Register
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
  • Questions
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Unanswered
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Tags
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Categories
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Users
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exams Taken
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exam List
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Digital-Grand Test -Q3


Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
0 votes

Consider two 2-bit numbers A = a_1a_0 and B = b_1b_0 . The value of a 2-bit number X = x_1x_0 is defined as : 

v(X) = x_1 \times 2^1 + x_0 \times 2^0

Assume that A and B are such that | v(A) - v(B) | \leq 2 . A four-variable function f(a_1,a_0,b_1,b_0) is to have value 1 whenever v(A) \leq v(B) , 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

asked Jun 10, 2020 by gbeditor-2 (72,840 points)
reshown Jun 12, 2020 by gbeditor-2

1 Answer

0 votes
 
Best answer

Assume that A and B are such that | v(A) - v(B) | \leq 2 .

This means that the inputs when A and B are such that \dpi{100} | v(A) - v(B) | > 2  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 f(a_1,a_0,b_1,b_0) is to have value 1 whenever v(A) \leq v(B) , 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...2^n 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.

answered Jun 16, 2020 by deepak-gatebook (226,240 points)
Answer:

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
...