GATE CS 2023 Q.43: Sequential Circuits, Counters and Registers

Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown in the figure. CLKIN is the clock input to the circuit. At the beginning, Q1, Q2 and Q3 have values 0, 1 and 1, respectively.

Sequential circuit with three flip-flops: T flip-flop Q1, D flip-flop Q2, and T flip-flop Q3 all clocked by CLKIN, where Q1 feeds D, Q2 feeds second T, and Q3 is inverted and fed back to the first T input.

Which one of the given values of (Q1, Q2, Q3) can NEVER be obtained with this digital circuit?

(0, 0, 1)

(1, 0, 0)

(1, 0, 1)

(1, 1, 1)

Official answer and solution

Official answer: A
From: Official GATE 2023 answer key

Solution

Formulate next-state equations for $Q_1, Q_2, Q_3$ and trace all reachable states from $(0, 1, 1)$ .

From the circuit schematic:

Flip-flop 1 (T-FF): $T_1 = \bar{Q}_3$ , so $Q_1^+ = Q_1 \oplus \bar{Q}_3$
Flip-flop 2 (D-FF): $D_2 = Q_1$ , so $Q_2^+ = Q_1$
Flip-flop 3 (T-FF): $T_3 = Q_2$ , so $Q_3^+ = Q_3 \oplus Q_2$

Starting from state $(Q_1, Q_2, Q_3) = (0, 1, 1)$ :

Clock 1: $T_1 = \bar{1} = 0$ , $D_2 = 0$ , $T_3 = 1 \implies Q_1^+ = 0 \oplus 0 = 0$ , $Q_2^+ = 0$ , $Q_3^+ = 1 \oplus 1 = 0$ . State: $(0, 0, 0)$
Clock 2: $T_1 = \bar{0} = 1$ , $D_2 = 0$ , $T_3 = 0 \implies Q_1^+ = 0 \oplus 1 = 1$ , $Q_2^+ = 0$ , $Q_3^+ = 0 \oplus 0 = 0$ . State: $(1, 0, 0)$
Clock 3: $T_1 = \bar{0} = 1$ , $D_2 = 1$ , $T_3 = 0 \implies Q_1^+ = 1 \oplus 1 = 0$ , $Q_2^+ = 1$ , $Q_3^+ = 0 \oplus 0 = 0$ . State: $(0, 1, 0)$
Clock 4: $T_1 = \bar{0} = 1$ , $D_2 = 0$ , $T_3 = 1 \implies Q_1^+ = 0 \oplus 1 = 1$ , $Q_2^+ = 0$ , $Q_3^+ = 0 \oplus 1 = 1$ . State: $(1, 0, 1)$
Clock 5: $T_1 = \bar{1} = 0$ , $D_2 = 1$ , $T_3 = 0 \implies Q_1^+ = 1 \oplus 0 = 1$ , $Q_2^+ = 1$ , $Q_3^+ = 1 \oplus 0 = 1$ . State: $(1, 1, 1)$
Clock 6: $T_1 = \bar{1} = 0$ , $D_2 = 1$ , $T_3 = 1 \implies Q_1^+ = 1 \oplus 0 = 1$ , $Q_2^+ = 1$ , $Q_3^+ = 1 \oplus 1 = 0$ . State: $(1, 1, 0)$
Clock 7: $T_1 = \bar{0} = 1$ , $D_2 = 1$ , $T_3 = 1 \implies Q_1^+ = 1 \oplus 1 = 0$ , $Q_2^+ = 1$ , $Q_3^+ = 0 \oplus 1 = 1$ . State: $(0, 1, 1)$ (cycle repeats)

The cycle visits: $(0, 1, 1) \to (0, 0, 0) \to (1, 0, 0) \to (0, 1, 0) \to (1, 0, 1) \to (1, 1, 1) \to (1, 1, 0) \to (0, 1, 1)$ . The state $(0, 0, 1)$ is never visited.

Final answer

Option (A)

Common trap

Miscalculating the XOR operation for T flip-flop transitions or missing the inverter on $Q_3$ .

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

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 43 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