FSM Finite State Machine Questions and Answers
1. Design a finite state machine FSM for a serial two’s complement block and also draw the logic diagram associated with it by using D-flipflop.
The main logic behind this is, start from the least significant bit and retain the bits until and first 1-bit has occurred. Once a 1-bit is found, start complementing the bits if 1 makes it 0 and if 0 make it 1. Note retain the first 1-bit. (Don’t complement it, complement the bit which follows that first 1-bit).
State Assignment:
Let us assume State ‘a’ represents that 1 has not occurred yet. and assume State ‘b’ the situation after the first one has occurred. State flow diagram:
Designing the above FSM using D-flipflop: Truth table:
|
Present State (PS)
|
Input
|
Next State (NS)
|
Output (Q)
|
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
1
|
|
1
|
1
|
1
|
0
|
Logic diagram:
2. What is the behavior of the above Finite state machine?
3. Decide the Flip-flop which can be used by avoiding external logic gates.
2. By Analyzing the above logic, FSM logic behaves as an ODD-serial-parity-indicator. Since the output is one when the number of input arrived till are in odd numbers.
|
Present State (PS) Qn
|
Input X
|
Next State (NS) Qn+1
|
Output (Z)
|
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
0
|
Here, Z = Qn XOR X, Hence a T-flip-flop can be used.
The truth table
|
J
|
K
|
Qn
|
Qn+1
|
|
0
|
0
|
0
|
0
|
|
0
|
0
|
1
|
1
|
|
0
|
1
|
0
|
0
|
|
0
|
1
|
1
|
0
|
|
1
|
0
|
0
|
1
|
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
|
1
|
1
|
1
|
0
|
The state flow or transition diagram for a JK flip-flop
X(t+1) = p’X+pY
Y(t+1) = pX’+p’Y
where X and Y are the two flip-flop outputs and p is the main external input.
Draw the state transition table for the above-given logic function.
Also, draw the state transition diagram associated with it.
And What is the behavior of the circuit?
1. The state transition table is (PS-Present state, NS-Next state),
|
PS
|
Input
|
NS
|
||
|
X
|
Y
|
p
|
X(t+1)
|
Y(t+1)
|
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
1
|
0
|
1
|
|
0
|
1
|
0
|
0
|
1
|
|
0
|
1
|
1
|
1
|
1
|
|
1
|
0
|
0
|
1
|
0
|
|
1
|
0
|
1
|
0
|
0
|
|
1
|
1
|
0
|
1
|
1
|
|
1
|
1
|
1
|
0
|
0
|
2. The state transition diagram is
3. The above circuit behaves as an ENABLE-based-gray-counter.
If A = 0, the circuit oscillates between either one of the two cases. Case 1: 00-01-00-01… and Case 2: 10-11-10-11… And
If A = 1, it switches inter between two cases. Draw the state transition diagram and implement the same using JK flip-flop and by using basic logic gates.
1. The FSM for the above problem statement can be drawn as
2. Implementation using JK flip-flop
Excitation table for JK flipflop is
|
Qn
|
Qn+1
|
J
|
K
|
|
0
|
0
|
0
|
X
|
|
0
|
1
|
1
|
X
|
|
1
|
0
|
X
|
1
|
|
1
|
1
|
X
|
0
|
The state transition for the above problem statement is
|
PS
|
Input
|
NS
|
JK Flip-flop inputs
|
|||||
|
A
|
B
|
x
|
A(t+1)
|
B(t+1)
|
JA
|
KA
|
JB
|
KB
|
|
0
|
0
|
0
|
0
|
1
|
0
|
X
|
1
|
X
|
|
0
|
0
|
1
|
1
|
0
|
1
|
X
|
0
|
X
|
|
0
|
1
|
0
|
0
|
0
|
0
|
X
|
X
|
1
|
|
0
|
1
|
1
|
1
|
1
|
1
|
X
|
X
|
0
|
|
1
|
0
|
0
|
1
|
1
|
X
|
0
|
1
|
X
|
|
1
|
0
|
1
|
0
|
0
|
X
|
1
|
0
|
X
|
|
1
|
1
|
0
|
1
|
0
|
X
|
0
|
X
|
1
|
|
1
|
1
|
1
|
0
|
1
|
X
|
1
|
X
|
0
|
Simplify using Karnaugh Map for the expressions JA, KA, JB, and KB. JA=x; KA=x; JB=x’; KB=x’;
Answer:
|
Mealy Model (depends on both input and PS)
|
Moore Model (depends only on Present State)
|
|
In the Mealy model, the next state outputs are associated with the change in the input and also the current or present state.
|
In the Moore model, the next state outputs are associated with the change in the present state only and not with change in inputs.
|
|
These models give the input immediately upon receiving the inputs.
|
Here, the output will change only when there is a change in the present state. like only during clock transitions.
|
|
Here, the chances of Glitches in the output, since the delay difference between state and input.
|
This model avoids Glitches in the output since it only depends on change in the present state (PS).
|
7. Design an FSM for serial sequence detector with the pattern “1010” with overlapping and with non-overlapping.
Let us assume FSM for the Mealy model.
Four states
b (one 1 detected state),
c (10 detected state),
and d (101 detected state).
The state transition diagram for the overlapping case will be
The state transition diagram for the non-overlapping case will be
Four states
a (no 0 detected state),
b (one 0 detected state),
c (01 detected state),
and d (011 detected state). The state transition or flow diagram for the non-overlapping case will be
Let assume three states
a (no 1 detected state)
b (one 1 detected state)
c (two or more the two 1’s detected state) The state flow diagram for the overlapping case will be
|
PS
|
NS
|
Output
|
||
|
x=0
|
x=1
|
x=0
|
x=1
|
|
|
a
|
a
|
b
|
0
|
0
|
|
b
|
e
|
c
|
0
|
1
|
|
c
|
a
|
d
|
0
|
1
|
|
d
|
e
|
f
|
0
|
1
|
|
e
|
a
|
f
|
0
|
0
|
|
f
|
g
|
d
|
0
|
1
|
|
g
|
a
|
b
|
0
|
0
|
Answer:
The optimized transition table will be
|
PS
|
NS
|
Output
|
||
|
x=0
|
x=1
|
x=0
|
x=1
|
|
|
a
|
a
|
b
|
0
|
0
|
|
b
|
e
|
c
|
0
|
1
|
|
c
|
a
|
b
|
0
|
1
|
|
e
|
a
|
c
|
0
|
0
|
For original table
|
i/p
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
|
|
NS
|
a
|
a
|
b
|
e
|
f
|
g
|
b
|
e
|
f
|
g
|
a
|
b
|
|
o/p
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
For an optimized table:
|
i/p
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
|
|
NS
|
a
|
a
|
b
|
e
|
c
|
a
|
b
|
e
|
c
|
a
|
a
|
b
|
|
o/p
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
Input Sequence 0101011001
Output Sequence 0001011100
Answer:
The idea is we need to design a complex sequence generator which will detect the patterns 011, 101, 110, and 111. Let us assume four different states
a = no 1 detected state.
b = one 1 detected state or 01 or 1 detected state.
c = two or more than two 1’s detected state.
d = 001/010 detected state. The FSM diagram is
|
Input Sequence
|
0101001101010
|
|
Output Sequence
|
0001100001111
|
Answer:
Here, it is required to design an overlapping complex sequence detector that will detect the patterns 0101, 1101, 1010, and 1011. Let us assume four different states
a = no 1 detected state.
b = at least one 1 detected state.
c = the pattern 010 detected state.
d = the pattern 1101/0101 detected state. The finite state machine is
13. Design an FSM-finite state machine which detects the alternate 0’s and 1’s in the previous three samples. for example
|
Input Sequence
|
0010101101000
|
|
Output Sequence
|
0001111001100
|
Answer:
Here, we need to design a complex sequence detector that will detect the patterns 010 and 101. Let us assume four states
a = continuous 0’s or no 1 detected state.
b = one 1 detected state.
c = pattern 10 detected state.
d = continuous 1’s detected state. The finite state machine can be drawn as
|
Input Sequence
|
01001101100
|
|
Output Sequence
|
00000111110
|
Answer:
Here, the meaning of eliminating the short length pulses is removing 0’s which are between the continuous 1’s and similarly removing 1’s which are between the continuous 0’s. Let us made a 1 after two continuous 0’s as 0, and similarly a 0 after two continuous 1’s as 1. Let us consider four states
a = continuous 0’s detected state.
b = one 1 in the two 0’s detected state.
c = continuous 1’s detected state.
d = one 0 in the two 1’s detected state. The finite state machine can be drawn as
|
Input
|
Sequence
|
Value
|
Output
|
|
0
|
0
|
0
|
0
|
|
1
|
01
|
1
|
0
|
|
0
|
010
|
2
|
0
|
|
1
|
0101
|
5
|
1
|
|
0
|
01010
|
10
|
1
|
Answer:
Let us make five state a, b, c, d, and e and each represents remainder 0, remainder 1, remainder 2, remainder 3, and remainder 4 respectively.
The finite state machine can be drawn as
Answer:
Let us define or assign three samples in such a way that
State a when A is not equal to B,
State b when A is equaled to B for previous one sample, and
State c when A is equaled to B for the previous two samples.
The FSM can be drawn as
Answer:
It is a similar example which we already did earlier. The idea is to find the remainder at each state and deciding the multiple of four. Let us assume four states,
State a for remainder 0
State b for remainder 1
State c for remainder 2
State d for remainder 3
and the state machine diagram will be
|
A
|
00110010110
|
|
B
|
00000011010
|
|
Output
|
01010111010
|
Answer:
Let us assume four states such as
State a the initial state or reset state.
At state b, the value of M is 0 and value N is X (either 0 or 1)
At state c, the value of M is 1 and value N is X (either 0 or 1)
At state d, assume M has the same value for the last two samples and is 0.
At state e, assume M has the same value for the last two samples and is 1.
The sequential finite state machine can be drawn for the above state assignment as
Answer:
Let us consider four different states as
In-state a, even number of 0’s and even number of 1’s
In-state b, even number of 0’s and an odd number of 1’s
In-state c, odd number of 0’s and even number of 1’s
In state d, an odd number of 0’s an odd number of 1’s
outputs will be in the form of one-hot encodings, such as 1000, 0100, 0010, and 0001.
The FSM for the given problem statement will be
