GATE CS 2025 Set 1 Q.60: Sequential Circuits, Counters and Registers

Consider the given sequential circuit designed using D-Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is _________ . (Answer in integer)

A 4-stage synchronous sequential circuit using four D flip-flops (D0, D1, D2, D3) triggered by a common CLK signal. Outputs Q0, Q1, Q2 are connected to inputs D1, D2, D3 respectively, and the complemented output Q3-bar of the last flip-flop is fed back to input D0 of the first flip-flop.

Your answer

Official answer and solution

Accepted answers: 7 to 8
From: Official GATE 2025 answer key

Solution

Recognize the 4-flip-flop circuit with $D_0 = \overline{Q_3}$ and $D_i = Q_{i-1}$ as a 4-bit Johnson (twisted-ring) counter and find the length of its state cycles.

The circuit is a 4-bit Johnson counter (twisted-ring shift register) with next-state equations:

Q_0^+ = \overline{Q_3}, \quad Q_1^+ = Q_0, \quad Q_2^+ = Q_1, \quad Q_3^+ = Q_2

Over the $2^4 = 16$ possible 4-bit states $(Q_0 Q_1 Q_2 Q_3)$ :

Starting from 0000, the circuit cycles through 8 distinct states before repeating 0000:
0000 -> 1000 -> 1100 -> 1110 -> 1111 -> 0111 -> 0011 -> 0001 -> 0000
Even if initialized to one of the 8 unused states (such as 0101), it also cycles through 8 distinct states (0101 -> 0010 -> 1001 -> 0100 -> 1010 -> 1101 -> 0110 -> 1011 -> 0101).

Thus the period of the circuit from any initial state is 8 distinct states (or 7 intermediate states strictly between leaving and returning to the initial state; the official GATE key accepts both 7 and 8).

Final answer

8 (7 to 8 accepted)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 60 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source