ENGN3213/6213 Semester 1, 2020
Lab Four
Finite State Machines
Overview
Finite state machines (FSMs) are used way to control the sequential execution of functions based
on a system’s state and inputs. In this lab you will learn to implement Moore and Mealy FSMs on
your FPGA boards to control the flow of your application.
In this lab you will
• Create a Moore FSM to mimic the operation of a Microwave oven’s control system.
• Create a Mealy Machine to control a pin comparator
In this lab you will learn to
• Implement a Moore and Mealy FSM in Verilog code
• Test the working of the FSM using inputs and outputs available on your FPGA board
• Design a Finite State Machine to control a pin comparator
Best of luck and Let’s have some fun!
2 | Finite State Machines © ANU 2020
Table of Contents
Lab Overview ..................................................................................................................... 3
Learning Outcomes ....................................................................................................... 3
What’s needed? ............................................................................................................ 3
Activity 1: Microwave Control System (Approx. 1hr) (10 Marks) .............................................. 4
Procedure .................................................................................................................... 5
Step 1: Create a Vivado project for this Activity ........................................................ 5
Step 2: Create a FSM module inside your project ...................................................... 6
Step 3: Declare state variables and assign values to each state .................................. 6
Step 4: Describe the Current State Register/ Transition block ..................................... 6
Step 5: Next state Logic .......................................................................................... 6
Step 6: Cook State logic .......................................................................................... 7
Step 7: Output Logic .............................................................................................. 7
Step 8: Module interconnect in TOP module ............................................................. 9
Step 9: Constraints file for your TOP module ............................................................ 9
Step 10: Synthesize – Implement – Generate Bitstream ........................................... 10
Activity 2: Design your own State Machine (Approx. 1-2 hrs - 10 Marks) ................................ 10
3 | Finite State Machines © ANU 2020
Lab Overview
Learning Outcomes
By completing this lab, you will learn to:
1. Instantiate modules in hierarchical designs
2. Use a combination of resets, enables and finite state machines to control complex
sequential logic processes
3. Design a finite state machine for a given set of inputs and outputs
What’s needed?
To complete this lab, you’ll require access to:
1. Vivado Design Suite running on Windows 10 or a supported Linux operating system
2. An FPGA-development board such as the Nexys4-DDR or Basys3
3. A micro-USB cable to program the FPGA board
4 | Finite State Machines © ANU 2020
Activity 1: Microwave Control System
(Approx. 1hr) (10 Marks)
A Finite State Machine is a tool used to control the flow and execution sequence of your system.
A Finite State Machine divides the control sequence of an application into discrete,
interconnected states. These states determine which stage of operation we are in, based on
which the same inputs may have different effects/outputs. A Finite State Machine is described
using a state diagram and a state transition table.
Figure 1: Example of a State Diagram for a Moore Machine (from the lecture slides)
FSMs can be of two main types, Moore and Mealy Machines. Both types have their own pros and
cons. An example of a Moore machine state diagram is shown in Figure 1. Moreover, the same
system may be described as both types. Which type we choose depends on the advantages and
disadvantages of the decision.
In the following Activity, you will design a State Machine to operate as the control system of a
microwave oven. Figure 2 shows the system control sequence overview.
Figure 2: System Diagram
5 | Finite State Machines © ANU 2020
We shall use the LEDs as the outputs and the switches and push buttons as inputs. The system
tries to mimic the working of a Microwave oven using the inputs and outputs available on our
FPGA board (I’m sorry if you had ideas of reheating your lunch ). Thus, the system may be
summed up as follows:
- IDLE: The system waits for user input. Press enter to start.
- SET_TIMER: Use the switches to set the timer by turning on the switch
number corresponding to the number of seconds. Eg. Set SW[7] to wait 7
seconds. Only the MSB of SW is used, all the rest are ignored. Press enter to
start cook.
- COOK: Wait until timer has elapsed
- ALARM: Blink LEDs to indicate cook complete. Press enter to restart.
Procedure
Here is how we will proceed.
Step 1: Create a Vivado project for this Activity
1. Create a new Project in Vivado. Call it ‘MicrowaveFSM’. We shall be using this project for
the first activity.
2. Create a top-level module called ‘MicrowaveFSM_top.v’. This module will be used to
connect all the different parts of the project. This module is important as it lets us pre-
process input signals (Debounce/SPOT etc.) before passing them to the FSM.
The project uses the usual inputs like clk, which accepts a 100Mhz external clk and reset
connected to a push button. I’m sure you are familiar with their operation by now.
This activity has 2 inputs, the Switch array and an Enter Key (called E in the state
diagram) which is connected to a push-button.
The output of this circuit drives the set of LED on board the Nexys/Basys Board.
module MicrowaveFSM_top (
input wire clk,
input wire reset,
input wire enter,
input wire [15:0] SW,
output wire [15:0] waveform
);
endmodule
3. We will use this module in the later stages but first lets start work on our Finite State
Machine.
6 | Finite State Machines © ANU 2020
Step 2: Create a FSM module inside your project
1. Create another source file called ‘FSM.v’. This module will have the same ports as our
top module.
2. In the FSM module, declare the output as a reg entity so we may drive this output inside
a procedural block.
3. Before you start writing the code for the FSM, look at the state diagram shown in Figure
2 and assign state names (IDLE, COOK, etc.) to the state encoding values using
parameters. This makes it easier to refer to the states in the Verilog code.
Step 3: Declare state variables and assign values to each state
1. Depending on the number of states calculate the number of bits required to represent all
states. In our case, we have 4 states. Therefore, we shall use 2 bits to represent each
state.
2. Assign bit values to each state and declare them as parameters inside your FSM module.
parameter IDLE=2'd0,COOK=2'd1,SET_TIMER=2'd2,ALARM=2'd3;
Step 4: Describe the Current State Register/ Transition block
1. A Finite State Machine consists of 3 main parts. The Nextstate Logic, the Output Logic
and the Current State Register/Transition block.
2. The Current State Register/Transition block is the simplest of the three. It simply stores
the current state of the system and loads the appropriate next state at every clock cycle.
As you would have noticed, we declared two registers of data-width large enough to
store our current and next state.
reg [1:0] state, nextstate;
3. Describe a procedural block that updates at every clock cycle and loads the contents of
nextstate in state. Make sure that the reset signal is able to return the system to a
known state/safe state.
Step 5: Next state Logic
1. The next state logic is crucial in controlling the sequence of events and states to match
the required output logic.
2. Next state logic depends on the inputs of the system and the current state.
3. Describe the next state logic as a different procedural block. Remember: The next state
logic need not be synchronised with clk.
7 | Finite State Machines © ANU 2020
4. The next state logic is best described using combinatorial logic through a case
statement.
always@(*)begin
case(state)
IDLE: begin
if(enter) nextstate=S1;
else nextstate=S0;
End
SET_TIMER: begin
...
...
endcase
5. The next state logic depends on the inputs and current state. Refer to the State diagram
for more information. If you get stuck on the COOK state, refer to Step 6.
Step 6: Cook State logic
As you will have noticed, the system waits during the cook state until a timer runs out before
proceeding to the next state, regardless of input. In this case we shall use a heartbeat
generator to count the number of seconds.
1. Add a source for the heartbeat generator. You may use your hearbeat module from
previous labs.
2. Instantiate this module to provide a beat every second by setting the right THRESHOLD
value.
3. Now we need a counter to count down the number of seconds. A very easy and sleek
way of doing this is to reuse the LED register to store the timer value set during S2:
SET_TIMER.
4. Instead of counting down the seconds using another module, we can simply right shift
the LED register by 1 at every beat signal.
if(beat) led <= led >> 1;
5. Once the MSB is removed the correct time will have elapsed and we can move to the
next state. Make sure you understand how we check if the LED register has all zeros. If
not, contact your tutor.
if((~led)) nextstate=S3;
Step 7: Output Logic
1. The output logic is the most important block in any FSM. This block dictates the
behaviour of the system that is controlled by the FSM.
2. Based on your knowledge of how the system works or should work, describe another
procedural block containing a case statement to drive your outputs.
8 | Finite State Machines © ANU 2020
always@(*)begin //should it be posedge clk?? read below
case(state)
IDLE: begin
//Outputs for State IDLE
end
SET_TIMER: begin
...
...
endcase
3. In our system, we can set all LEDs high to indicate READY/IDLE state. In state
SET_TIMER we can connect LED to SW input directly to show the time SET.
4. In State Cook we shift the LED right at every beat signal. Since the LEDs are also our
output, this serves to indicate the amount of time left. In other cases, e.g., using the
Seven Seg Displays, we may need additional statements in our output logic for this state.
5. In the last state, ALARM, we flash LEDs to indicate that the COOK is completed. Here,
we may either reuse the beat signal to toggle LED, or we could use a different clock
divider and set LED high for half the time and low the other half. You can control the
frequency of flashing by changing the THRESHOLD or TOPCOUNT of your clock
divider/heartbeat module.
Important thinking point: in class you have learned that a FSM’s output logic should be
coded as combinational. However, in this design LED (the output) behaves as a shift register
(or, if you like, a one-hot down-counter with enable and reset) and therefore must be a
sequential component. How can this be?
The answer is that, strictly speaking, the LED shift register is not part of the microwave
controller FSM as described in the state diagram of Figure 2 (the state diagram does not
describe the counting steps!). It is actually a separate module of its own, which the main
FSM controls.
To help you understand, compare the two snippets of code below, the first explicitly
identifies the external counter logic (a reg called ledcount is created for the purpose)
always@(*)begin // FSM combinational output logic
case(state) begin
...
SET_TIME: led = SW;
COOK: led = ledcount;
...
endcase
end
always@(posedge clk)begin //counter logic - sequential
if(state==SET_TIME) ledcount <= SW; //reset
else if(beat) ledcount <= ledcout >> 1; //o-h downcounter
9 | Finite State Machines © ANU 2020
end
the second bundles the counter in with the output logic
always@(posedge clk)begin //sequential “bundled” output logic
case(state) begin
...
SET_TIME: led <= SW
COOK: if(beat) led <= led >> 1;
...
endcase
Now, since the only purpose of this FSM is to run the LEDs, the first version of the code
– though formally “neater” – may be seen as unnecessarily laboured for this simple
design. The two code options are largely equivalent and the bundled option is acceptable
in this case where there is a very low risk of confusion in interpreting the structure of the
system.
You can use either style for your coding today. As an exercise, try to draw the schematic
for your Verilog in each case, and you might notice that the first one has a much more
intuitive translation. That’s why it is recommended that you keep to the template for
more complex designs!
Step 8: Module interconnect in TOP module
The top is module is very useful in assembling all the different blocks/components of the system
and connecting them appropriately. Here, we create instances of various modules that we have
described and join them together using wires.
We also use the top module to pre-process input signals to
- Reduce noise
- Sample inputs at the right sampling frequency
- Buffer values for bulk processing
- Sync various asynchronous inputs
In this case we shall use the top module to
1. Debounce the enter button
2. Use Single Pulse on Transition(SPOT) on the debounced signal
After this, we can pass the pre-processed enter signal and other raw inputs to the FSM.
Similarly, we can link the outputs from the FSM to the outputs of the TOP module.
Step 9: Constraints file for your TOP module
Write constraints for your system based on the ports in your TOP module.