How to calculate number of flip flops for FSM | applied electronics engineering

# How to calculate number of flip flops for FSM

By Applied Electronics - Wednesday, September 7, 2016 No Comments
FSM(Finite State Machine) is a sequential circuit that that goes through a number of predefined states under the control of one or more inputs. Let p, q and clock be the inputs and X, Y and Z be the outputs. A block diagram of FSM is shown below.

Internally, the FSM is composed of next state logic, memory and output state logic. Depending on how these internal blocks are connected we can have Moore or Mearly FSM. Whatever the type of FSM, they require a specified number of flip flops. These flip flops forms the memory block. These flip flop stores a finite number of states. The number of flip flop is thus related to the number of the states.

The number of states is related to the number of flip flops by the formula below,

Number of States = 2Number of flip flops

Hence the number of flip flops is given by,

Number of flip flops = log10(Number of states)/ log10(2 )

As an example, a counter which counts from 0 to 10 has 10 states. Therefore number of flip flops required is;

Number of flip flops = log10(10)/ log10(2 ) = 1/0.3 = 3.33

We round up to highest number therefore,

Number of flip flops required = 4

Since 24 gives 16 states and we require only 10 states, 6 states will be unused. Had we taken 3 flip flops we would end up with only 8 states which is insufficient.

For more details see FSM-based Digital Design using Verilog