Implementing Finite State Machines

Up to now the projects have been very linear - mostly counters that work like clockwork. Now we are going to investigate how you can get your logic to allow external signals change it’s behaviour, rather than just processing the results. The technique introduced is used in many different areas of a design, such as:

• Communication protocols, where data may be sent asynchronously or different data required different responses

• Scheduling of control signals in a memory controller

• Decoding and executing instructions in a CPU

• Control of simple machine

• Implementing simple user interfaces

Introduction to the project

For the project we are going to build a combination lock, which works as follows:

• All of the switches must be turned off

• Then switch 7 must be turned on

• Then switch 6 must be turned on

• Then switch 5 must be turned on

• Finally switch 4 must be turned on

If this sequence is followed, all the LEDs will turn on and stay on until all switches are moved back to off.

In software this would be quite easy - using the console for user input something like this would be quite close :

while(1)

{

if(getchar() = ’7’ && getchar() = ’6’ && getchar() = ’5’ && getchar() = ’4’)

{

LEDs = 0xFF;

getchar();

}

}

To get the same result, we need to use a finite state machine (FSM) - a directed graph of states and how the system moves between the states. There is a formalized way to document FSMs, but here’s my somewhat less formal approach which works well when sketching designs on paper

At any point in time your design is at a state indicated by a circle. On the next clock tick ”it must” follow an arrow. All options ”must” be mutually exclusive. I have added bold arrows to indicate the "no other arrow applies" option.

So when the system is in the "START" state the options are either:

• If switches are set to "0000000" we go to the "START" state.
• If switches are set to "1000000" we go to the "ONE RIGHT" state.
• Otherwise we go to the "ERROR" state.
Likewise, in the "ERROR" state the options are:
• If switches are set to "0000000" we go to the "START" state.
• Otherwise we go to the "ERROR" state.

 Implementing in VHDL

Implementation is relatively easy.

You can either use enumerated types (that have not been covered), but it is usually better to use constants:
...
constant state_error : STD_LOGIC_VECTOR(3 downto 0) := "0000";
constant state_start : STD_LOGIC_VECTOR(3 downto 0) := "0001";
constant state_one_right : STD_LOGIC_VECTOR(3 downto 0) := "0010";
...
signal state : STD_LOGIC_VECTOR(3 downto 0) := (others => ’0’);

If you use constants, then you can encode output signals within the states, ensuring that you get glitch-less signals. If you like, you could include this in your project to help with debugging:

leds(3 downto 0) <= state;

In your project’s process it is usually easiest to code it using a CASE statement like this:

if rising_edge(clk) then
case state is
when state_error =>
case switches is
when "00000000" => state <= state_start;
when others => state <= state_error;
end case;
when state_start =>
case switches is
when "00000000" => state <= state_start;
when "10000000" => state <= state_one_right;
when others => state <= state_error;
end case;
when state_one_right =>
case switches is
when "10000000" => state <= state_one_right;
when "11000000" => state <= state_two_right;
when others => state <= state_error;
end case;
....
when others =>
state <= state_error;
end case;
end if;

Project - Combination lock 1

• Code the above FSM to implement the combination lock. To give some feedback on success set LEDs to "11111111", and
• Test it in the simulator, using this in the testbench stimulus process

switches <= "00000000";
wait for 200 ns;
switches <= "10000000";
wait for 200 ns;
switches <= "11000000";
wait for 200 ns;
switches <= "11100000";

If I have designed it correctly, the only way to get to the "OPEN" state is to move the switches through "00000000", "10000000", "11000000", "11100000", then finally to "11110000"

wait for 200 ns;
switches <= "11110000";
wait for 1000 ns;
switches <= "00000000";

• Try running it in hardware - it most probably won’t work reliably - 50:50 if you are lucky.

The problem with switch bounce

This design will work perfectly well - as long as the switch contacts don’t bounce. If they bounce the FSM will view that as an "otherwise" case and go to the error state.

Solutions are:

• Debounce the switches in hardware
• Debounce the switch signals using logic within the FPGA
• Sample the switches at intervals that should mask any bounce - perhaps every 1/10th of a second
• Update the FSM to allow for switch bounces

The "debounce" solutions are all relatively hard, while updating the FSM will only need a few lines of code.

Project - Combination lock 2

• Trace through the FSM diagram to work out why a bounce causes it to fail
• Update the FSM to ignore switch bounces

If you wish, test it in the simulator - here is stimulus that looks like four bouncing switches:

switches <= "00000000";
wait for 200 ns;
switches <= "10000000";
wait for 50 ns;
switches <= "00000000"; -- bounce
wait for 50 ns;
switches <= "10000000";
wait for 300 ns;
switches <= "11000000";
wait for 50 ns;
switches <= "10000000"; -- bounce
wait for 50 ns;
switches <= "11000000";
wait for 300 ns;
switches <= "11100000";
wait for 50 ns;
switches <= "11000000"; -- bounce
wait for 50 ns;
switches <= "11100000";
wait for 300 ns;
switches <= "11110000";
wait for 50 ns;
switches <= "11100000"; -- bounce
wait for 50 ns;
switches <= "11110000";
wait for 1000 ns;
switches <= "00000000";

• Test it in hardware

Challenges

• Can you make the LEDs flash off and on for a few seconds when an error occurs?
• Can you make the board flash the LEDs in a pattern stored in BRAM when it reaches the "OPEN"