GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
1.9k views

Consider a Boolean function $ f(w,x,y,z)$. Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $ i_{1}=\left \langle w_{1}, x_{1}, y_{1},z_{1}\right \rangle $ and $ i_{2}=\left \langle w_{2}, x_{2}, y_{2},z_{2}\right \rangle $ , we would like the function to remain true as the input changes from $ i_{1}$ to $ i_{2}$ ($ i_{1}$ and $ i_{2}$ differ in exactly one bit position) without becoming false momentarily. Let $ f(w,x,y,z)=\sum (5,7,11,12,13,15)$ . Which of the following cube covers of $f$ will ensure that the required property is satisfied? 

  1. $ \overline{w}xz,wx\overline{y},x\overline{y}z,xyz,wyz$
  2. $ wxy, \overline{w}xz,wyz$
  3. $ wx\overline{y} \overline{z}, xz, w\overline{x}yz$
  4. $ wx\overline{y}, wyz, wxz, \overline{w}xz, x\overline{y}z, xyz$
asked in Digital Logic by Loyal (4.2k points)   | 1.9k views
Could someone explain me the question plz.. ?
What to do with inputs i1 and i2 ?
How should I group ? In kmap every adjacent coloum differ by one bit , so should I group only adjacent coloums ?
Im not able to understand this question.

3 Answers

+8 votes
Best answer

The question is indirctly asking for static hazard in the circuit - that is output becoming 1 momentarily when it is supposed to be 0 or vice verse.

Here $f(w,x,y,z) = \sum (5,7,11,12,13,15)$

So, K-map will be 

  y'z' y'z yz yz'
w'x'        
w'x   5 7  
wx 12 13 15  
wx'     11  

 

So, its minimized sum of products expression will be $xz + wxy + w'yz$. Since all the minterms are overlapping, there is no chance of static hazard here.

Now, lets consider the options one by one:

A. $\overline{w}xz,wx\overline{y},x\overline{y}z,xyz,wyz$

  y'z' y'z yz yz'
w'x'        
w'x   5 7  
wx 12 13 15  
wx'     11  

Chance of static hazard

Here, when $y$ changes from $0$ to $1$, the GATE for $wyz$ should give 1 (from earlier 0, assuming $w=z=1$) and that of $wy'z$ should give 0 (from earlier 1). But there is a possibility of circuit giving 0 (static 1 hazard) momentarilly due to gate delays. In order to avoid this, we must add a gate with $wxz$ also which ensures all adjacent blocks in K-map are overlapped.

 

We can also have the sum of products as $xy'z + w'yz + wxy$ which is of course not minimal. But this also has hazard as when  $w$ changes from $0$ to $1$, the GATE for $wxy$ should give 1 (from earlier 0) and that of $w'yz$ should give 0 (from earlier 1). But there is a possibility of circuit giving 0 momentarilly (assuming $x=0$). This hazard can be avoided by adding $xyz$ and similarly we need $w'xz$ and $wxz$. Thus we get $ xy'z + w'yz + wxy + xyz + w'xz + wxz$

Now, each of these term will correspond to a GATE when the circuit is implemented. What we require is to avoid the output to change when any of the input literal changes its value (hazard).

 

B. $\overline{w}xz,wx\overline{y},x\overline{y}z,xyz,wyz$

  y'z' y'z yz yz'
w'x'        
w'x   5 7  
wx 12 13 15  
wx'     11  

Chance of static hazard

Here, when $y$ changes from $0$ to $1$, the GATE for $wyz$ should give 1 (from earlier 0, assuming $w=z=1$) and that of $wy'z$ should give 0 (from earlier 1). But there is a possibility of circuit giving 0 (static 1 hazard) momentarilly due to gate delays. In order to avoid this, we must add a gate with $wxz$ also which ensures all adjacent blocks in K-map are overlapped.

 

We can also have the sum of products as $xy'z + w'yz + wxy$ which is of course not minimal. But this also has hazard as when  $w$ changes from $0$ to $1$, the GATE for $wxy$ should give 1 (from earlier 0) and that of $w'yz$ should give 0 (from earlier 1). But there is a possibility of circuit giving 0 momentarilly (assuming $x=0$). This hazard can be avoided by adding $xyz$ and similarly we need $w'xz$ and $wxz$. Thus we get $ xy'z + w'yz + wxy + xyz + w'xz + wxz$

Now, each of these term will correspond to a GATE when the circuit is implemented. What we require is to avoid the output to change when any of the input literal changes its value (hazard).

B. $wxy, \overline{w}xz,wyz$

Is not correct as $wxy$ is not a minterm for the given function

C. $wx\overline{y} \overline{z}, xz, w\overline{x}yz$

  y'z' y'z yz yz'
w'x'        
w'x   5 7  
wx 12 13 15  
wx'     11  

Here, also there are hazards possible as the middle 4 pairs are separated by 1 bit difference to both $wxy'z'$ as well as $wx'yz$. Could have been avoided by using $wxy'$ instead of $wxy'z'$ and $wyz$ instead of $wx'yz$ which ensures all neighbouring blocks are overlapped.

D. $wx\overline{y}, wyz, wxz, \overline{w}xz, x\overline{y}z, xyz$

These minterms cover all the minterms of $f$ and also, all the neighbouring blocks are overlapping. So, no chance of hazard here and hence is the required answer.

answered by Veteran (13.2k points)  
selected by

@Sonam,Is D the right answer?You mentioned that there is no one bit difference?Can you please tell what is the correct answer?And I have seen at some places the first term in D option is not there,and with remaining 5 terms there is no static hazard as all adjacent blocks are overlapped.

 

What do you mean by comment

"and in option d ) which have 5 correct term but one is not matched ... in fact that is not 1 bit difference ...."

Please help

@Rahul, the answer was later edited by me and hence the comments don't make sense now. Everything is explained now in answer- there is no use in saying what is the "correct answer" unless you yourself get to know the reason. (GATE is not ISRO exam where they copy the same question and options again).

The question paper was taken from here:

https://drive.google.com/file/d/0B8_aYGBndW4HbHBnM05WTXZjaDg/view

thankyou. finally understood. :)
Shouldn't the minimized SOP be $xz+wx\overline{y}+wyz$?
+2 votes

Given that,  function to remain true as input changes from i1 to i2 and i1, i2 differ in exactly one bit position.

We know that adjacent cells in kmap differ by exactly 1 bit. So, we have to group cells in function represented by kmap such that all adjacent cells are grouped as below.

all these 6 groups gives : 

answered by (345 points)  
+1 vote

I found a better way to answer this question .

Go according to the Question .  i1 and i2 differs in exactly one bit position without becoming false momentarily.

Go to option (a)

Draw K map and find  the binary covered by implicant

w'xz =5,7    0101 , 0111    here you will see it is one bit different

wxy'=12,13   1100,1101   here you will see it is also one bit different

xy'z=5,13  0101,1101  here you will see it is one bit different

xyz=7,15 0111, 1111 here you will see it is one bit different

wyz=11,15  1011,1111 here you will see it is one bit different

Option (a) misses wxz possible one bit  change.So it is false.

 

 

(b)

wxy = 15,14 but 14 is not covered by K map so b is wrong option

 

(c)

wxy'z' = 12 =1100  here there is not bit change so it is wrong option

 

(d)

wyz=11,15  1011,1111 here you will see it is one bit different

wxz=13,15  1101,1111 here you will see it is one bit different

w'xz =5,7    0101 , 0111    here you will see it is one bit different

xy'z=5,13  0101,1101  here you will see it is one bit different

xyz=7,15 0111, 1111 here you will see it is one bit different

wxy'=12,13   1100,1101   here you will see it is also one bit different

So option d satisfy whole f so it is Answer .

answered by Active (1.8k points)  
edited by
Answer:

Related questions



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2064 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,647 answers
79,695 comments
31,069 users