GATE CS 2015 Set 1 Q.30 (CS Q.20): Sequential Circuits, Counters and Registers

Consider a 4-bit Johnson counter with an initial value of $0000$ . The counting sequence of this counter is:

$0, 1, 3, 7, 15, 14, 12, 8, 0$

$0, 1, 3, 5, 7, 9, 11, 13, 15, 0$

$0, 2, 4, 6, 8, 10, 12, 14, 0$

$0, 8, 12, 14, 15, 7, 3, 1, 0$

Official answer and solution

Official answer: D
From: Official GATE 2015 answer key

Solution

Trace the register state transitions of a 4-bit twisted ring (Johnson) counter.

A 4-bit Johnson counter uses four flip-flops $(Q_3, Q_2, Q_1, Q_0)$ where the serial input to the highest bit is the inverted output of the lowest bit: $D_3 = \overline{Q_0}$ , with shift $Q_i(t+1) = Q_{i+1}(t)$ .

Tracing starting from $0000_2 = 0$ :

State 0: $0000_2 = 0$
Next: $D_3 = \overline{0} = 1 \implies 1000_2 = 8$
Next: $D_3 = \overline{0} = 1 \implies 1100_2 = 12$
Next: $D_3 = \overline{0} = 1 \implies 1110_2 = 14$
Next: $D_3 = \overline{0} = 1 \implies 1111_2 = 15$
Next: $D_3 = \overline{1} = 0 \implies 0111_2 = 7$
Next: $D_3 = \overline{1} = 0 \implies 0011_2 = 3$
Next: $D_3 = \overline{1} = 0 \implies 0001_2 = 1$
Next: $D_3 = \overline{1} = 0 \implies 0000_2 = 0$

The sequence of decimal states is:

0, 8, 12, 14, 15, 7, 3, 1, 0.

This matches option D.

Final answer

Common trap

Tracing in the opposite shift direction without checking the option values, or confusing Johnson counter with a standard ring counter.

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 1
Question: 30 of 65, printed as CS Q.20
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