GATE CS 2001 Q2.12 — Sequential Circuits

The given circuit is a 3-bit Linear Feedback Shift Register (LFSR). By analyzing the connections of the flip-flops, we can determine the next-state equations for each flip-flop:

• $Q_2^+ = Q_1$ (value of $Q_1$ is shifted into $Q_2$)
• $Q_1^+ = Q_0$ (value of $Q_0$ is shifted into $Q_1$)
• $Q_0^+ = Q_2 \oplus Q_1$ (feedback is the XOR of $Q_2$ and $Q_1$)

The state of the circuit is represented in decimal as $4Q_2 + 2Q_1 + Q_0$, which corresponds to the binary representation $(Q_2 Q_1 Q_0)_2$.

Starting with the initial state $Q_2 Q_1 Q_0 = 001_2$ (Decimal $1$):

1. State 1 ($001_2$):
   • $Q_2^+ = 0$, $Q_1^+ = 1$, $Q_0^+ = 0 \oplus 0 = 0$
   • Next State: $010_2 = 2$
2. State 2 ($010_2$):
   • $Q_2^+ = 1$, $Q_1^+ = 0$, $Q_0^+ = 0 \oplus 1 = 1$
   • Next State: $101_2 = 5$
3. State 5 ($101_2$):
   • $Q_2^+ = 0$, $Q_1^+ = 1$, $Q_0^+ = 1 \oplus 0 = 1$
   • Next State: $011_2 = 3$
4. State 3 ($011_2$):
   • $Q_2^+ = 1$, $Q_1^+ = 1$, $Q_0^+ = 0 \oplus 1 = 1$
   • Next State: $111_2 = 7$
5. State 7 ($111_2$):
   • $Q_2^+ = 1$, $Q_1^+ = 1$, $Q_0^+ = 1 \oplus 1 = 0$
   • Next State: $110_2 = 6$
6. State 6 ($110_2$):
   • $Q_2^+ = 1$, $Q_1^+ = 0$, $Q_0^+ = 1 \oplus 1 = 0$
   • Next State: $100_2 = 4$
7. State 4 ($100_2$):
   • $Q_2^+ = 0$, $Q_1^+ = 0$, $Q_0^+ = 1 \oplus 0 = 1$
   • Next State: $001_2 = 1$ (cycles back)

Thus, the correct state sequence is $1, 2, 5, 3, 7, 6, 4$.