GATE CS 2018 Q.32 (CS Q.22): Sequential Circuits, Counters and Registers

Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops.

The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of “in” is _____.

Your answer

Official answer and solution

Solution

Determine the conditions for next-state equations $Q_1^+$ and $Q_2^+$ to equal current states $Q_1$ and $Q_2$ .

From the circuit schematic:

A state $(Q_1, Q_2)$ has a self-loop (transitions back to itself) if there exists an input $\text{in} \in \{0, 1\}$ such that:

Q_1^+ = Q_1 \implies \text{in} = Q_1

Q_2^+ = Q_2 \implies Q_1 = Q_2

The condition $Q_1 = Q_2$ restricts candidates to $(0, 0)$ and $(1, 1)$ :

State $(0, 0)$ : Setting $\text{in} = 0$ gives $Q_1^+ = 0, Q_2^+ = Q_1 = 0$ , returning to $(0, 0)$ .
State $(1, 1)$ : Setting $\text{in} = 1$ gives $Q_1^+ = 1, Q_2^+ = Q_1 = 1$ , returning to $(1, 1)$ .
States $(0, 1)$ and $(1, 0)$ : Require $Q_2^+ = Q_1$ , so $Q_2^+$ would be $0$ for $(0, 1)$ (different from current $Q_2 = 1$ ) and $1$ for $(1, 0)$ (different from current $Q_2 = 0$ ). Neither can transition back to itself.

Thus, exactly 2 states possess a self-transition.

Final answer

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

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.