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 Dflipflop.
The main logic behind this is, start from the least significant bit and retain the bits until and first 1bit has occurred. Once a 1bit is found, start complementing the bits if 1 makes it 0 and if 0 make it 1. Note retain the first 1bit. (Don’t complement it, complement the bit which follows that first 1bit).
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 Dflipflop: 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 Flipflop which can be used by avoiding external logic gates.
2. By Analyzing the above logic, FSM logic behaves as an ODDserialparityindicator. 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 Tflipflop 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 flipflop
X(t+1) = p’X+pY
Y(t+1) = pX’+p’Y
where X and Y are the two flipflop outputs and p is the main external input.
Draw the state transition table for the abovegiven 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 (PSPresent state, NSNext 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 ENABLEbasedgraycounter.
If A = 0, the circuit oscillates between either one of the two cases. Case 1: 00010001… and Case 2: 10111011… And
If A = 1, it switches inter between two cases. Draw the state transition diagram and implement the same using JK flipflop and by using basic logic gates.
1. The FSM for the above problem statement can be drawn as
2. Implementation using JK flipflop
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 Flipflop 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 nonoverlapping.
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 nonoverlapping 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 nonoverlapping 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 FSMfinite 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
Instate a, even number of 0’s and even number of 1’s
Instate b, even number of 0’s and an odd number of 1’s
Instate 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 onehot encodings, such as 1000, 0100, 0010, and 0001.
The FSM for the given problem statement will be