Digital Design Introduction

Finite State Machines

Tarik Graba

2022-2025

Finite State Machine (FSM)

Systematic way to design sequential logic for control sequences.

Structure

Generic structure of a state machine

The figure shows the generic structure of a synchronous sequential system. The outputs of the system depend on some internal state (state in the figure).

Depending on this state and the inputs of the system, we can compute combinationally its next state value (n_state in the figure) that will replace the state value at the next clock edge.

The outputs of the system will only depend on its state value (combinationally).

This kind of synchronous system is called a Moore Finite State Machine (FSM).

The name (FSM) comes from the fact that with this structure, the number of states that a system can have is limited (and thus finite) by the size of the state register.

Methodology

Starting from a functional specification.

Draw a state transition diagram

 

Each node represents one of the possible states of the system. The arcs represent transitions from one state to the other. The label on each arc represents the condition for which the transition is taken (functions of the inputs).

For each state, we will have some outputs values.

Remember that this diagram represents the state transitions of a synchronous system. The evolution of the state can only happen at the clock edge.

In this example:

State encoding(s)

Represent each state by a numerical value.

For example, using integer values:

  S0 -> 00 (0)
  S1 -> 01 (1)
  S2 -> 10 (2)

The number of bits to represent (and store) the state value is the log_2 the number of states.

This encoding is arbitrary and not unique.

Another example of encoding is what is called one-hot encoding where a separate bit is used for each state. For our example, we would have:

  S0 -> 001 (1)
  S1 -> 010 (2)
  S2 -> 100 (4)

The number of bits to represent the state (and store) value is equal to the number of states and is larger than the simple integer encoding. But, it is easier to detect in which state we are as the value is decoded which can simplify some part of the logic.

We will see later, that using SystemVerilog construct, we can keep abstract representations of the states and leave encoding choice to CAD tools.

State transition

State transition table.

For the previous example:

            inputs
 state    | e | c | n_state  |
  S0  (00)| x | 1 |  S1  (01)|
  S0  (00)| x | 0 |  S0  (00)|
  S1  (01)| x | x |  S2  (10)|
  S2  (10)| 0 | x |  S1  (01)|
  S2  (10)| 1 | x |  S0  (00)|

This table describes the combinational function that computes the next state. We will see that using SystemVerilog, we do not need to write down this table manually. We can use higher level HDL constructs to describe the transition table.

Output encoding

Outputs value for each state

            outputs
 state    | o1 | o2 |
  S0  (00)| 0  | 0  |
  S1  (01)| 0  | 1  |
  S2  (10)| 1  | 0  |

This table also represents a combinational function. The complexity of the function depend on the state encoding.

To illustrate this, if we choose a one-hot encoding for the example:

             outputs
 state     | o1 | o2 |
  S0  (001)| 0  | 0  |
  S1  (010)| 0  | 1  |
  S2  (100)| 1  | 0  |

We see that each output has the value of on of the state bits.

SystemVerilog Description

3 processess description

enum logic[1:0] { S0, S1, S2 } state, n_state;
// state register
always_ff@(posedge clk)
if(reset)
    state <= S0;
else
    state <= n_state;
// states transitions
always_comb
begin
   // !default first
   // stay in current state
  n_state = state ;
  case (state)
   S0  : if (c)
            n_state = S0;
   S1  :    n_state = S1;
   S2  : if (e)
            n_state = S0;
        else
            n_state = S1;
  endcase
end
// outputs are combinational
// functions of the states
always_comb
    output1 = f(state);

always_comb
    output2 = g(state);

always_comb
    output3 = ...
...

SystemVerilog support enumeration types to declare the state names instead of having to use numerical values. This is achieved using the enum keyword as shown here. In this example, INIT is equivalent to the value 0, S1 to 1 and S2 to 2. This abstraction makes the code easier to read and debug.

The state register (state) and the next state value n_state are declared conjointly using the same enum.

The state next value is computed combinationally and only depends on the current state value and the value of the inputs. Note that it is recommended to start by giving a default value (n_state = state) which means that by default the state will keep its current value. Then, we only have to express the transitions that will make the state change.

Finally, the outputs are added as combinational functions of the state current value.

Reaction time

Moore FSM

 
 

In a Moore FSM, the outputs depend only on the value of the state. Thus, for an output to change, we need to wait for the state to change at the next clock edge.

This means that the reaction time of a Moore state machine can not be less than one clock period.

Mealy FSM

 
 

A Mealy FSM allows the modification of the output before changing state. The outputs depend combinaatorialy on both the state and the inputs. This allows to react faster to inputs change.

Mealy FSM structure

Mealy FSM structure

The main difference between Moore and Mealy FSM, is that for the Mealy version, the outputs depends on both the state and the inputs.

This generally allows reducing the number of states and to have faster reactions to the input changes.

The main drawback of a Mealy FSM is that there is a combinational path between the inputs and the outputs. This makes it harder to respect timing constraints as the critical path can be unbounded when connecting consecutive state machines.

Examples

Simple light control

We have a regular switch (S) and a LED (L) (to simulate a light bulb) and we want to design a system with the following behaviour:

  1. initially, the LED should be off,
  2. when we press the switch, LED should go ON.
  3. The LED should stay ON as long as the switch is not released than pressed again.

Design a synchronous Moore FSM to implement this behaviour.

Light control with a timer

Same system with the switch and the LED. When the switch is pressed, we want the LED to go ON and then go OFF automatically after a predefined duration.

The LED should stay OFF as long as the switch is not released and pressed again.

For the implementation the duration will be 10 periods of the clock.

Chronometer

We have two sensors with a binary digital output (S0 and S1) and we want to measure the time between two events detected by those sensors.

An event corresponds to the sensor going from 0 to 1.

We will implement the following behaviour:

  1. S0 goes high, start a timer,
  2. ignore S0 change as long as the timer is running.
  3. S1 goes high, stop the timer, then capture its value,
  4. once the timer value is captured, return to the initial state, and wait for a new event.

Simplifying the previous FSMs with an edge detector

Back to the index