# Finite State Machine and Miscellaneous

 Question 1
The state transition diagram for the circuit shown is
 A A B B C C D D
GATE EC 2019   Digital Circuits
Question 1 Explanation:
When $A=0, Q_{n+1}=1$
When $A=1, Q_{n+1}=\bar{Q}_{n}$
So, the correct state transition diagram is,

 Question 2
In the circuit shown below, a positive edge-triggered D Flip-Flop is used for sampling input data $D_{in}$ using clock CK. The XOR gate outputs 3.3 volts for logic HIGH and 0 volts for logic LOW levels. The data bit and clock periods are equal and the value of$\Delta T/T_{CK} = 0.15$, where the parameters $\Delta T$ and $T_{CK}$ are shown in the figure. Assume that the Flip-Flop and the XOR gate are ideal.
If the probability of input data bit $( D_{in})$ transition in each clock period is 0.3, the average value (in volts, accurate to two decimal places) of the voltage at node X , is _______.
 A 0.84 B 0.62 C 0.12 D 0.92
GATE EC 2018   Digital Circuits
Question 2 Explanation:

\begin{aligned} V_{X(\mathrm{avg})} &=\left[0.3 \times 3.3\left(1-\frac{\Delta T}{T_{C K}}\right)\right]+[0.7 \times 0] \mathrm{V} \\ &=0.3 \times 3.3 \times(1-0.15) \mathrm{V} \\ &=0.3 \times 3.3 \times 0.85 \mathrm{V}=0.8415 \mathrm{V} \end{aligned}

 Question 3
A traffic signal cycles from GREEN to YELLOW, YELLOW to RED and RED to GREEN. In each cycle, GREEN is turned on for 70 seconds, YELLOW is turned on for 5 seconds and the RED is turned on for 75 seconds. This traffic light has to be implemented using a finite state machine (FSM). The only input to this FSM is a clock of 5 second period. The minimum number of flip-flops required to implement this FSM is _______.
 A 4 B 5 C 6 D 7
GATE EC 2018   Digital Circuits
Question 3 Explanation:
\begin{aligned} \text{GREEN }&\rightarrow 70 \text{seconds}\\ \text { YELLOW } & \rightarrow 5 \text { seconds } \\ \text { RED } &\rightarrow 75 \text { seconds }\\ \text{Clock period }&\rightarrow 5 \text{seconds }\\ \end{aligned}
Total number of unique states required
$=\frac{70+5+75}{5}=30$
Minimum number of flip-flops required is,
$n=\left\lceil\log _{2}(30)\right\rceil=\lceil 4.91\rceil=5$
 Question 4
The state diagram of a finite state machine (FSM) designed to detect an overlapping sequence of three bits is shown in the figure. The FSM has an input 'In' and an output 'Out'. The initial state of the FSM is $S_{0}$.

If the input sequence is 10101101001101, starting with the left-most bit, then the number times 'Out' will be 1 is __________.
 A 2 B 3 C 4 D 5
GATE EC 2017-SET-2   Digital Circuits
Question 4 Explanation:
By observing the given state diagram, it is clear that the FSM can be used to detect the sequence '101'
It is given in the question that, the FSM detects overlapping sequences also. The given input sequence is,
$\underline{101}0\underline{110}1001\underline{101} \quad \Rightarrow$So, Output will be 1 for 4 times.
 Question 5
A finite state machine (FSM) is implemented using the D flip-flops A and B, and logic gates, as shown in the figure below. The four possible states of the FSM are $Q_{A}Q{B}$=00,01,10 and 11.

Assume that $X_{1N}$ is held at a constant logic level throughout the operation of the FSM. When the FSM is initialized to the state $Q_{A}Q_{B}$=00 and clocked, after a few clock cycles, it starts cycling through
 A all of the four possible states if $X_{IN}=1$ B three of the four possible states if $X_{IN}=0$ C only two of the four possible states if $X_{IN}=1$ D only two of the four possible states if $X_{IN}=0$
GATE EC 2017-SET-1   Digital Circuits
Question 5 Explanation:
In the given diagram,
$D_{A}=Q_{A} \oplus Q_{B} \text { and } D_{B}=\overline{Q_{A} X_{I N}}$
For $X_{I N}=0:$
$D_{A}=Q_{A} \oplus Q_{B} \text { and } D_{B}=1$

So, for $X_{I N}=0,$ Number of possible states =2
$For X_{I N}=1$
$D_{A}=Q_{A} \oplus Q_{B} \text { and } D_{B}=\bar{Q}_{A}$

So, for $X_{IN}=1$ of possible states = 3

There are 5 questions to complete.