GATE 2022 IN Q.46: solution and answer

GATE 2022 · INQ.46 · 2 marks · MCQ

The digital circuit shown ________

GATE 2022 IN question 46: Three positive-edge-triggered D flip-flops (clock inputs drawn with a triangle, no bubble) share one common clock line CLK. — Figure from the GATE 2022 IN paper. It is part of the question.

(A)
is a divide-by-5 counter
(B)
is a divide-by-7 counter
(C)
is a divide-by-8 counter
(D)
does not function as a counter due to disjoint cycles of states

Answer and solution

ANSWER

(A) The circuit is a divide-by-5 counter. Its states cycle $000 \to 100 \to 110 \to 011 \to 001 \to 000$ , and all three unused states lead into that cycle.

Official answer: ASource: Official answer key, GATE 2022 IN (IIT Kharagpur)

Read the next-state equations off the wiring. For a D flip-flop, $Q^{+} = D$ . The overline means complement: $Q_{0}^{+} = \overline{Q_{1} + Q_{2}}, Q_{1}^{+} = Q_{0}, Q_{2}^{+} = Q_{1}$
Write the state as $Q_{0} Q_{1} Q_{2}$ , start from $000$ and apply the equations one clock at a time. From $000$ : $Q_{0}^{+} = \overline{0 + 0} = 1$ and the other two bits shift right, which gives $100$ .
$100 \to 110$ (the NOR output is still $1$ ). $110 \to 011$ (now $Q_{1} = 1$ , so the NOR gives $0$ ). $011 \to 001$ . $001 \to 000$ ( $Q_{2} = 1$ , so the NOR gives $0$ ).
So the main cycle is $000 \to 100 \to 110 \to 011 \to 001 \to 000$ , which has $5$ distinct states.
Check the three unused states to rule out a second, separate cycle: $010 \to 001$ , $101 \to 010 \to 001$ , and $111 \to 011$ . Each one reaches the main cycle within at most two clocks. The counter is therefore self-starting, there is no lock-out loop, and option (D) is ruled out.
Every output (for example $Q_{2}$ , which runs $0, 0, 0, 1, 1$ and then repeats) has a period of $5$ clock pulses, so its frequency is $f_{c l k} /5$ . The circuit is a divide-by-5 counter.

KEY IDEA

This is a 3-stage shift register with feedback $D_{0} = \overline{Q_{1} + Q_{2}} = \overline{Q_{1}} \overline{Q_{2}}$ . A plain Johnson (twisted-ring) counter uses $D_{0} = \overline{Q_{2}}$ and has $2 n = 6$ states. Adding $Q_{1}$ to the NOR makes $110$ go to $011$ instead of $111$ , so one state is skipped and the counter has $2 n - 1 = 5$ states. To find the modulus of any feedback shift register, trace the state sequence from $000$ , then check every unused state for a separate loop.

WATCH OUT FOR

Treating the circuit as an ordinary Johnson counter (mod 6), or as a 3-bit binary counter (mod 8), without reading the second NOR input. Another mistake is to pick (D) after finding only the 5-state main cycle, without tracing the unused states $010$ , $101$ and $111$ . All three lead into the main cycle, so there is no disjoint loop.

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

GATE 2022 IN Q.46: solution and answer

Answer and solution

More Sequential questions