Register

GATE CSE 2005 | Question: 62

• edited by
26,408 views
85 85 votes

Consider the following circuit involving a positive edge triggered D FF.

Consider the following timing diagram. Let $A_{i}$ represents the logic level on the line $A$ in the $i$-th clock period.

Let $A'$ represent the complement of $A$. The correct output sequence on $Y$ over the clock periods $1$ through $5$ is:

  1. $A_{0} A_{1} A_{1}' A_{3} A_{4}$
  2. $A_{0} A_{1} A_{2}' A_{3} A_{4}$
  3. $A_{1} A_{2} A_{2}' A_{3} A_{4}$
  4. $A_{1} A_{2}' A_{3} A_{4} A_{5}'$

5 Answers

Best answer
102 102 votes
  • $D = AX + X'Q'$
  • $Y = D$

$A_i$ represent the logic level on the line $A$ at the $i^{th}$ clock period. If we see the timing diagram carefully, we can see that during the rising edge, the output $Y$ is determined by the $X$ value just before that rising edge. i.e., during the rising edge say for clk2, $X$ value that determines the output is $1$ and not $0$ (because it takes some propagation delay for the $0$ to reach the flip flop). Similarly, the $A$ output that determines the output for clk $i,$ is $A_{i-1}.$

  • For clk1, $X$ is $1,$ so, $D = A = A_0$
  • For clk2, $X$ is $1,$ so $D = A = A_1$
  • For clk3, $X$ is $0,$ so $D = Q_2' = A_1'$
  • For clk4, $X$ is $1,$ so $D = A = A3$
  • For clk5, $X$ is $1,$ so $D = A = A4$

So, answer is A choice. 

• edited by
55 55 votes

Answer: (A) 

Explanation: The Flip Flop used here is a Positive edge triggered D Flip Flop, which means that only at the “rising edge of the clock” flip flop will capture the input provided at D and accordingly give the output at Q. And at other times of the clock the output doesn’t change. The output of D flip flop is same as input, i.e. Y=Q=D ( at the rising edge ).

Now, in the question above, 5 clock periods are given, and we have to find the output Q or Y in those clock periods.

First, let’s derive the boolean expression for the Logic gate.

which is :
D = AX + X’ Q’

Now,

In the 1st clock period, (i.e. when t = 0 to 1 )

here the clock has rising edge at t= 0, hence at this moment only, D flip flop will change its state.

In the 1st clock,  X = 1, So,  D = A. Now A logic line may have different levels at different clock periods, i.e. may be high or low, therefore we have to answer with respect to the ith clock period where Ai is the logic level ( high or low ) of logic line A in the ith clock.

So in the 1st clock period, A logic value should be A1 ( i.e. value of A in 1st clock period), but due to the delay provided by the Logic Gates ( Propagation Delay) the value of A used by Flip Flop is previous value of A only, i.e.it will capture the value of D resulted by using the logic line A in the 0th clock period, which is A0. Same happens with the value of X, i.e. instead of Xi, previous value of X  is used in the in the ith clock period, which is Xi-1.

Now, In the 1st clock period value of X is same as in the 0th clock, i.e. logic 1. So, X = 1 ,and A = A0, therefore, D = A0, and hence Q = Y = A0

Similarly we have to do for other clock periods, i.e. instead of taking Ai and Xi,  Ai-1 and Xi-1 need to be taken for getting the output in the ith clock period.

In the 2nd clock period, (i.e. when t = 1 to 2 )

X = 1 ( value in the previous clock), So, D = A1 ( value of A in the previous clock)  , therefore Q = Y = A1

In the 3rd clock period, (i.e. when t = 2 to 3 )

X = 0 ( value in the previous clock,see the timing diagram), So, D = Q’ = A1′ , therefore Q = Y = A1′   ( because of the feedback line )

In the 4th clock period, (i.e. when t = 3 to 4 )

X = 1 ( value in the previous clock,  ), So, D = A3 , therefore Q =  Y = A3

In the 5th clock period, (i.e. when t = 4 to 5 )

X = 1 ( value in the previous clock ), so, D = A4 , therefore Q = Y = A4

Hence the output sequence is : A0 A1 A1′ A3 A4

 

Source : http://geeksquiz.com/gate-gate-cs-2005-question-62/

6 6 votes

 

Derive Equation

$$D = (A \cdot X) + (\overline{X} \cdot \overline{Q})$$

Since it is a positive edge-triggered D Flip-Flop, the output $Q$ at the next clock cycle ($Q_{n+1}$) is equal to the value of $D$ at the moment of the rising edge. Since $Y = Q$, our equation for the output at period $i$ is:

$$Y_i = D_{i-1} = (A_{i-1} \cdot X_{i-1}) + (\overline{X}_{i-1} \cdot \overline{Y}_{i-1})$$

 

Trace the Sequence

We evaluate the output for each clock period based on the timing diagram for $X$:

  • Period 0: $X = 1$. The rising edge at the start of Period 1 captures $D_0$.

    • $D_0 = (A_0 \cdot 1) + (0 \cdot \overline{Y}_0) = A_0$.

    • $Y_1 = A_0$.

  • Period 1: $X = 1$. The rising edge at the start of Period 2 captures $D_1$.

    • $D_1 = (A_1 \cdot 1) + (0 \cdot \overline{Y}_1) = A_1$.

    • $Y_2 = A_1$.

  • Period 2: $X = 0$. The rising edge at the start of Period 3 captures $D_2$.

    • $D_2 = (A_2 \cdot 0) + (1 \cdot \overline{Y}_2) = \overline{Y}_2$.

    • Since $Y_2 = A_1$, then $Y_3 = \overline{A}_1$ (denoted as $A'_1$).

  • Period 3: $X = 1$. The rising edge at the start of Period 4 captures $D_3$.

    • $D_3 = (A_3 \cdot 1) + (0 \cdot \overline{Y}_3) = A_3$.

    • $Y_4 = A_3$.

  • Period 4: $X = 1$. The rising edge at the start of Period 5 captures $D_4$.

    • $D_4 = (A_4 \cdot 1) + (0 \cdot \overline{Y}_4) = A_4$.

    • $Y_5 = A_4$.

 

Combining the results for periods 1 through 5:

$$Y_1 Y_2 Y_3 Y_4 Y_5 = A_0 A_1 A'_1 A_3 A_4$$

Answer is A

1 1 vote

I think answer may be B

if see the cases 

D=AX+X'Q'

Y=D

A X Q Q' y
0 1 0 1 0=A
0 1 1 0 0=A
1 1 0 1 1=A
1 1 1 0 1=A
A 0 A A' A'
A 1 A' A A
A 1 A A' A
1 1 vote

Hi, diagram is little small , open image in new tab with right click and just zoom it 😀. Or download it 🥲

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 1993 | Ques...Next → · Parameter passing te...
← Previous in category · to multiply a binary...Next in category → · minimization of circ...
Position:
Show:

Related questions

199 199 votes
9 answers 9 answers
79.0k
79.0k views
Kathleen asked Sep 22, 2014
78,988 views
GATE CSE 2005 | Question: 68
A $5$ stage pipelined CPU has the following sequence of stages:IF – instruction fetch from instruction memoryRD – Instruction decode and register readEX – Execute: ALU op...
27 27 votes
4 answers 4 answers
13.3k
13.3k views
Kathleen asked Sep 22, 2014
13,259 views
GATE CSE 2005 | Question: 15
Consider the following circuit. Which one of the following is TRUE?$f$ is independent of $x$$f$ is independent of $y$$f$ is independent of $z$None of $x, y, z$ is red...
34 34 votes
4 answers 4 answers
14.7k
14.7k views
Kathleen asked Sep 22, 2014
14,720 views
GATE CSE 2005 | Question: 64
Consider the following circuit:The flip-flops are positive edge triggered $D$ $\textsf{FF}$s. Each state is designated as a two-bit string $Q_0Q_1$. Let the initial state...
32 32 votes
3 answers 3 answers
15.5k
15.5k views
gatecse asked Sep 21, 2014
15,490 views
GATE CSE 2005 | Question: 12, ISRO2009-64
Let $f(x)$ be the continuous probability density function of a random variable $x$, the probability that $a < x \leq b$, is :$f(b-a)$$f(b) - f(a)$$\int\limits_a^b f(x) dx...