State Machines (FSM)

State machines are everywhere, from a simple edge detection to washing machines to CPUs. The State Machines we will talk about have a finite amount of states those are called Finite-State-Machines (FSM).

We directly start with a small State machine (I skip all the talking about washing machines and stuff, just read through this and you will get the idea).

Lets assume we want to detect a rising edge of a signal. Just in the clock period where the input changed from 0 to 1, the output should be high.

Edge Detection

 

You may notice that there is a delay between input and output, the reason is that the input is checked on the rising edge of the clock and if there was a change from 0 to 1 the output will be set to 1 for 1 cycle.

From the diagram above we can extract our 3 states which are the following:

  1. idle (input is low, we are idling around
  2. edge detected (input changed from 0 to 1)
  3. input high (input is at 1 and not changing)

The timing diagram now can also be seen like this:

Mealy edge detection

 

So we simply need to assign the output to the "edge detected" state and we are done, but before we do so, we go a bit more into the theory, first of all we introduce state diagrams.

State Diagrams

Due to the simplicity of the state machine and because I don't want to to mess up the diagrams the variable names are skipped in the diagrams, for more complex state machines they have to be added next to the input and output.
The diagrams have the following elements:

State

Every state has a unique number, this number also has to be in the state symbol, followed by the name
UML_state

 

Unfortunately there is no real standard for those diagrams, there are different ways on how to indicate the output of a state, I want to show 2:

state with out 1 state

 

both show the same, in this state the output is 0.

Transition

The step of going from one state to the other is called transition. Every transitions comes with a condition, in our very simple example this is the input.

state

We can see that if the input is 1 we change to state 2.

So the whole diagram now can be drawn, every state should have 2 transitions, one for every possible state of the input:

state

 

As we want to work in the digital domain we need to change the state numbers into something machine readable. There are different approaches, like gray code or "1 hot" but we want to keep it simple so we just use normal binary numbers.

state

The reason I added the state "11" is that with 2 bits we have 4 possible states. Due to an error it might happen we end up in state "11" and boom... we are trapped. So it is good practice to add all possible states to the diagram to add the possibility to recover from an error. It might be possible that one edge is lost but this is still better than losing the complete functionality. It also is good practice to add an entry point so we know the initial state after startup:

state

Great, so we have everything, lets bring it into hardware!
From that point on we already could implement the state machine using a switch case which would look like this:

(I added a reset input to force the FSM to the initial state and I had to rename the pins as "input" and "output" are reserved keywords.)

Simulation is giving what we expected:

sim

 

We can dig a bit deeper and observe the internal state which gives us:

sim

To access the internal register we need to add a wire and assign the register to the wire:

output wire [1:0] state_out assign state_out = state;
Going for real hardware

The way described above is how you would implement in software, if we talk about hardware we need to simplify the structure, this will also make the implementation in HDL more efficient.

First we need the truth table of the circuit which is having the following structure:

input S1 S0 S1* S0* output

We split the bits of the State into S1 and S0.
S1* and S0* describe the state that is followed by the condition on the left side. For now the output depends on the current state.

Ok, lets fill that table!

input S1 S0 S1* S0* output
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 0 0
0 1 1 0 0 0
1 0 0 0 1 0
1 0 1 1 0 1
1 1 0 1 0 0
1 1 1 0 0 0

Based on this truth table we can set up logical conditions for the output variables.
I will use KV-Diagrams to get the required equations (d is the input):

For S0*

kv

Therefore:
S0*=d AND (NOT S1 AND NOT S0)

For S1*

kv

 

Therefore:
S1*=d AND (S1 XOR S0)

 

For output

kv

Therefore:
output=(NOT S1) AND S0

With some simplifications the hardware now could look like this:

state

In Verilog we can write:

Simulation

sim

and with observation of the internal states:
sim

Mealy and Moore Machines

The way of how to implement a State Machine that was shown above was a Moore Machine. There are different ways on how to implement a State Machine, which one to use depends on the task and the requirements.

However, Moore and Mealy State Machines are the most common ones. The difference is that Moore based machines create the output based on the current state. Each state has a defined output (as we did above).

Moore based State Machine

Moore based State Machine

Mealy State Machines build the output based on the current state AND the current input. This also has the effect that the output becomes asynchronous, if you want to make it synchronous, you will have to add a Flipflop to the output signal :

mealy

Mealy based State Machine

 The Edge detection as Mealy Machine

Now that the theory is known, the edge detection can be implemented as a Mealy machine, first thing that may be noticed is that now there is no more direct assignment of the output to the state but to the transitions! The transitions now determine the output, therefore we only have to states, the input is high or the input is low. The number at the tip of the error is the input, the number at the end of the arrow (a.k.a. transition) is the output:

state

The truth table from this diagram is:

input S S* output
0 0 0 0
0 1 0 0
1 0 1 1
1 1 1 0

you immediately can see that this is now more compact than the Moore machine.
The Result can be directly seen from the Table:
S*=input
output=input AND NOT S

The result therefore looks like this:
mealy

For and simple example like this, the solution above might be the intuitive way, but for more complex requirements its usually not that obvious.

Verilog:

Simulation:

sim

 

With current state:

sim

2 thoughts on “State Machines (FSM)

  1. gmm

    Excellent post, Thomas, this is what I needed to get me started with the LUT component for the PSoCs. Hopefully you can keep working on the blog, you have some very interesting content here!

Leave a Reply