Simple finite state machine (FSM)

Aim of the tutorial:

In this tutorial we will learn the basic steps of creating a FSM with the help of a practical example

Prerequisites:

We will use the hardware and software mentioned in the previous sections. A little knowledge of digital electronics will be necessary for the implementation - logic gates and Karnaugh-maps. For hardware testing, we will use an arbitrary signal generator and an oscilloscope.

The noise pulse eliminator:

The noise pulse eliminator is a digital circuit which eliminates signal pulses which last for one clock period only. The behaviour of such a device is shown below:

Finite State Machines:

An FSM or automaton is an abstract machine, which can be in exactly one state from a set of a finite number of states. The state transition occurs as a response to external inputs.
The image on the right shows a generic FSM. The Z blocks are registers with the SAME clock signal.

The dashed boxes are optional. We can connect inputs directly to the CL, only if they are synchronised to the system clock signal. Otherwise, we must connect the inputs to a register.
The CL creates the next state based on the current state and the inputs.

Mealey FSM outputs depend on the current state and inputs, so they are prone to glitches - the output can change in the middle of a clock cycle.
Moore FMS outputs depend only on the current state; they don't change in the middle of a cycle - this is done with the help of an output register, which introduces a one clock delay.

We design FSMs starting with a state machine diagram. We name the states with letters a,b,... We are in a, when the input is zero. We wait for one, and we transit to b. This could be a noise pulse, so we wait for one cycle, for the input to stay one. If it is true, then we transit to state c. If the input goes back to zero, we go back to state a.

Similarly, in the case of state c, we detect an input of true 1 or noise pulse 0. This means overall we have four states, and the FSM diagram looks like:

The next step is to encode the state names. In our case, 2 bits are enough. a=00, b = 01, c = 11, d = 10. We use the Gray code instead of normal binary numbers because this will ease our combination logic.

The truth table:

We can find the next state and the output logic with the help of the Karnaugh table. The results are:

NS1 = (S0&S1) | In&(S0 | S1),

NS0 = In

Out = S1

We can write the filter logic based on the calculated logic functions.

This is the filter logic. We have two registers for the current and the next states, and we update the states synchronously to a clock signal rising edge - even the reset is synchronous. The next always block fires on any change of every used signal, and only contains the logic expression for the next state.

If we synthesize the project, we can check the implemented hardware:

The implemented design recognises the state machine and the output logic.

One hot encoding:

We saw that the states could be represented by 2 bit wide registers, but this representation requires a state logic implementation. The one hot encoding is a solution to this problem. We name the states a = 0001, b = 0010, c = 0100, d = 1000. We can see that we use 4bit wide register

Here we have the one hot implementation of the same logic. We used a registered output, which only depends on the states. We named the state parameters for writing convenience. We can write the state transitions in this configuration in a case statement with if conditionals.

If we synthesise the logic we get the hierarchical schematic:

The state machine (surprise surprise) is the same as before.

The gate level design is shown below.

The simulation confirms that our design indeed works as intended. Two things to note: We can see that the output is delayed with one clock cycle compared to our desired output - this is because we used a registered output Moore state machine. If we take a look at the state block above, we can see that the reset is handled as an input, and the actual reset pin is floating - this is because we used an active high reset, while the FPGA fabric uses active low resets, so our reset is incorporated in the logic.