GATE CS 2015 Set 2 Q.17 (CS Q.7): Sequential Circuits, Counters and Registers

The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence $(0,0,1,1,2,2,3,3,0,0,\dots)$ is _____.

Your answer

Official answer and solution

Official answer: 3
From: Official GATE 2015 answer key

Solution

Determine the number of distinct states required by the counter cycle.

The counter sequence repeats the pattern:

(0, 0, 1, 1, 2, 2, 3, 3, 0, 0, \dots)

In a sequential circuit, state transitions must be deterministic. When the counter is at count $0$ , the next state is either another $0$ or $1$ . To distinguish the first $0$ from the second $0$ , distinct internal states must represent them.

Thus, each count value ( $0, 1, 2, 3$ ) appears twice in the complete repeating cycle, requiring:

N = 8\text{ distinct internal states}:\quad (0_A, 0_B, 1_A, 1_B, 2_A, 2_B, 3_A, 3_B).

The minimum number of flip-flops $n$ required to represent $N = 8$ states is:

n = \lceil \log_2 8 \rceil = 3\text{ flip-flops}.

Final answer

Common trap

Counting only the 4 unique output values (0, 1, 2, 3) and incorrectly answering $\lceil \log_2 4 \rceil = 2$ .

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

Source

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