GATE CS 2025 Set 1 Q50 — Sequential Circuits

The given sequential circuit is a 3-bit Linear Feedback Shift Register (LFSR). Let the outputs of the three D flip-flops be $Q_2, Q_1, Q_0$ from left to right.

The state transition equations for the circuit are:

Let us trace the states starting from an initial non-zero state, say $001$:

1. State 1: $001 \implies D_2 = 0 \oplus 1 = 1, D_1 = 0, D_0 = 0 \implies \text{Next State} = 100$
2. State 2: $100 \implies D_2 = 0 \oplus 0 = 0, D_1 = 1, D_0 = 0 \implies \text{Next State} = 010$
3. State 3: $010 \implies D_2 = 1 \oplus 0 = 1, D_1 = 0, D_0 = 1 \implies \text{Next State} = 101$
4. State 4: $101 \implies D_2 = 0 \oplus 1 = 1, D_1 = 1, D_0 = 0 \implies \text{Next State} = 110$
5. State 5: $110 \implies D_2 = 1 \oplus 0 = 1, D_1 = 1, D_0 = 1 \implies \text{Next State} = 111$
6. State 6: $111 \implies D_2 = 1 \oplus 1 = 0, D_1 = 1, D_0 = 1 \implies \text{Next State} = 011$
7. State 7: $011 \implies D_2 = 1 \oplus 1 = 0, D_1 = 0, D_0 = 1 \implies \text{Next State} = 001$ (Returns to initial state)

The cycle of distinct states visited is:

Thus, the circuit goes through 7 distinct states before returning to the initial state.

Note: The official GATE answer key accepts both 7 and 8 to account for interpretations where the return state is counted as the 8th step, or considering the total state space of $2^3 = 8$ states.