GATE CS 2016 Set 1 Q.18 (CS Q.8): Sequential Circuits, Counters and Registers

We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is _____.

Your answer

Official answer and solution

Accepted answers: 3 to 4
From: Official GATE 2016 answer key

Note on this question

Official answer key accepts range 3.0 to 4.0.

Solution

Determine the number of distinct internal states needed to generate the repeating non-monotonic sequence.

The required count sequence of output values is:

0 \to 1 \to 0 \to 2 \to 0 \to 3 \to (\text{repeats})

Notice that the output value 0 appears three separate times in one complete cycle, and each occurrence must transition to a different next output:

The first 0 must transition to 1.
The second 0 must transition to 2.
The third 0 must transition to 3.

A sequential circuit requires a unique internal state for each step in the sequence so that the next-state logic is deterministic. Thus, at least 6 distinct internal states ( $S_0, S_1, S_2, S_3, S_4, S_5$ ) are required.

To represent $N = 6$ states using binary flip-flops:

2^n \ge 6 \implies n = \lceil \log_2 6 \rceil = 3

With 3 J-K flip-flops, $2^3 = 8 \ge 6$ states can be uniquely encoded. (If the counter is designed using one flip-flop per distinct state or specific output-state encodings, 4 flip-flops may also be used; the official key accepts both 3 and 4).

Final answer

Common trap

Looking only at the maximum output value 3 ( $0, 1, 2, 3$ ) and assuming 2 flip-flops suffice ( $2^2 = 4$ ), which fails because 0 transitions to three different values.

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

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 18 of 65, printed as CS Q.8
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