GATE CS 2016 Set 1 Q8 — Sequential Circuits

To design a synchronous counter that counts the sequence $0 o 1 o 0 o 2 o 0 o 3 o 0 \dots$, we can analyze the minimum number of J-K flip-flops required using two different design perspectives (both of which were accepted in GATE):

Method 1: State Machine Perspective (Minimum States)

The given sequence has a repeating period of $6$ states:

Since the next state must be uniquely determined by the current state, we need at least $6$ distinct internal states to uniquely identify each step in the sequence (specifically to distinguish between the three different occurrences of $0$).

Let $n$ be the number of J-K flip-flops. The number of states $N$ that can be represented by $n$ flip-flops is $2^n$.

Thus, the absolute minimum number of flip-flops required is 3.

Method 2: Direct Output Representation Perspective

If the state of the flip-flops must directly contain the output count value:

• The maximum count value is $3$, which requires $2$ flip-flops (say, $Q_1 Q_0$) to represent the binary values $00, 01, 10, 11$.
• However, the value $0$ ($00$) appears three times in the sequence, each transitioning to a different next state ($1$, $2$, and $3$).
• To distinguish these three occurrences of $0$, we need auxiliary state variables. Since there are $3$ identical output states, we need at least $\lceil \log_2 3 \rceil = 2$ extra flip-flops (say, $y_1 y_0$) to act as control/distinguishing bits.

Total flip-flops required = $2 \text{ (for count)} + 2 \text{ (for distinguishing)} = \mathbf{4}$ flip-flops.

Both 3 and 4 are correct depending on whether output decoding logic is used.