GATE 2024 IN Q.42: solution and answer

GATE 2024 · INQ.42 · 2 marks · MCQ

In the figure shown, the positive edge triggered D flip-flops are initially reset to Q = 0. The logic gates and the multiplexers have no propagation delay. After reset, a train of clock pulses (CLK) are applied. The logic-states of the inputs DIN, S and the clock pulses are also shown in the figure. Assuming no timing violations, the sequence of output Y from the 3rd clock to the 5th clock, $Y_{3} Y_{4} Y_{5}$ is

GATE 2024 IN question 42: Circuit: three identical stages, each a 2:1 MUX (inputs labelled 0 on top and 1 below, select line S common to all three)… — Figure from the GATE 2024 IN paper. It is part of the question.

(A)
001
(B)
010
(C)
000
(D)
011

Answer and solution

ANSWER

$Y_{3} Y_{4} Y_{5} = 001$ , option (A). The register goes $000 \to 100 \to 110 \to 011$ , holds at $011$ on clock 4 (S = 0), then shifts to $101$ on clock 5. Here $Y = \overline{\overline{Q_{1}} Q_{2} Q_{3}}$ , which is 0 only in state 011.

Official answer: ASource: Official answer key, GATE 2024 IN (IISc Bengaluru)

Read the MUX wiring. In each stage the 2:1 MUX drives the D input, with input 0 on top and input 1 below: $D_{i} = \overline{S} Q_{i} + S (input 1)$ , where input 1 is DIN, $Q_{1}$ and $Q_{2}$ for stages 1, 2 and 3. So $S = 1$ shifts right ( $Q_{1} \leftarrow DIN, Q_{2} \leftarrow Q_{1}, Q_{3} \leftarrow Q_{2}$ ) and $S = 0$ holds the state, because each flip-flop reloads its own $Q$ .
Output logic (overline = complement): the left AND gate takes $\overline{Q_{1}}$ and $Q_{2}$ , the right AND gate takes $Q_{2}$ and $Q_{3}$ , and both feed a NAND gate: $Y = \overline{(\overline{Q_{1}} Q_{2}) (Q_{2} Q_{3})} = \overline{\overline{Q_{1}} Q_{2} Q_{3}}$ So $Y = 0$ only in the state $Q_{1} Q_{2} Q_{3} = 011$ , and $Y = 1$ in every other state.
Sample S and DIN at each rising edge. A positive-edge D flip-flop stores whatever is on D at the instant of the edge. From the timing diagram, S falls just after edge 3 and DIN rises just after edge 3, so at edges 1 to 5: $S = 1, 1, 1, 0, 1$ and $DIN = 1, 1, 0, 1, 1$ .
Step through the states, starting from the reset state $Q_{1} Q_{2} Q_{3} = 000$ . Edge 1 ( $S = 1$ , DIN $= 1$ ): shift gives $100$ . Edge 2 ( $S = 1$ , DIN $= 1$ ): $110$ . Edge 3 ( $S = 1$ , DIN $= 0$ ): $Q_{1} = 0, Q_{2} = 1, Q_{3} = 1$ , so $011$ .
Edge 4 ( $S = 0$ ): every flip-flop reloads its own output, so the state stays $011$ . Edge 5 ( $S = 1$ , DIN $= 1$ ): $Q_{1} = 1$ , $Q_{2} =$ old $Q_{1} = 0$ , $Q_{3} =$ old $Q_{2} = 1$ , so $101$ .
Evaluate Y after each clock. After clock 3 the state is $011$ , so $\overline{Q_{1}} Q_{2} Q_{3} = 1 \cdot 1 \cdot 1 = 1$ and $Y_{3} = 0$ . After clock 4 the state is still $011$ , so $Y_{4} = 0$ . After clock 5 the state is $101$ , so $\overline{Q_{1}} = 0$ , the product is $0$ and $Y_{5} = 1$ .
Therefore $Y_{3} Y_{4} Y_{5} = 001$ , which is option (A).

KEY IDEA

Each MUX in front of a D flip-flop picks between holding and shifting. With $S = 1$ each stage loads the stage to its left (DIN for stage 1), so the circuit is a right-shift register. With $S = 0$ each stage reloads its own $Q$ and nothing changes. The NAND of the two AND terms reduces to $Y = \overline{\overline{Q_{1}} Q_{2} Q_{3}}$ , so you only need to find when the register sits in state 011. Take S and DIN at the instant of each rising edge.

WATCH OUT FOR

The usual slip is to miss the hold on clock 4. S is 0 at that edge, but students often shift DIN = 1 in anyway, which gives states 011, 101, 110 and $Y_{3} Y_{4} Y_{5} = 011$ , the trap option (D). A second slip is reading S or DIN just after an edge instead of at it. Both change shortly after edge 3, so at edge 3 they are still S = 1 and DIN = 0. A third is misreading the left AND input as $Q_{1}$ when the wire actually comes from $\overline{Q_{1}}$ .

From the GATE 2024 IN paper. Every question of this paper · Download the full paper · All 30 Sequential questions, with notes

GATE 2024 IN Q.42: solution and answer

Answer and solution

More Sequential questions