Description

Finite State Machines
1 Learning Objectives
The purpose of this lab is to learn how to create FSMs as well as use them to control a datapath over multiple clock cycles.
2 Marking Scheme
This lab worth 4% of your final grade, but you will be graded out of 8 marks for this lab, as follows:
• Prelab – Simulations: 3 marks
• Part I (in-lab): 2 marks
• Part II (in-lab): 3 marks
• Part III (bonus): 2 marks (1 for prelab, 1 for in-lab demo)
3 Preparation Before the Lab
You are required to complete Parts I and II of the lab by writing and testing Verilog code with Modelsim (using reasonable test vectors that you can justify). Part III is optional, but has a prelab component, should you choose to do it. You should hand-in your prelab preparations (schematics, Verilog, and simulation outputs) for Parts I to II to the TAs (and Part III, if you choose to do it).
In-lab Work
You are required to implement and test all of Parts I and II of the lab (and Part III, if you choose to do it). You should demonstrate them to the teaching assistants when you finished testing them.
4 Part I
We aim to implement a finite state machine (FSM) that recognizes two specific sequences of applied input symbols: four consecutive 1s or the sequence 1101. There is an input w and an output z. Whenever w = 1 for four consecutive clock pulses, or when the sequence 1101 appears on w across four consecutive clock pulses, the value of z has to be 1; otherwise, z = 0. Overlapping sequences are allowed, so that if w = 1 for five consecutive clock pulses the output z will be equal to 1 after the fourth and fifth pulses. Figure 1 illustrates the required relationship between w and z. A state diagram for this FSM is shown in Figure 2.
Figure 3 shows a starter Verilog code for the required state machine. Study and understand this code as it provides a model for how to clearly describe a finite state machine that will both simulate and synthesize properly. It has missing parts that you should complete yourself.
The toggle switch SW 0 on the DE1-SoC board is the reset signal input for the FSM, SW 1 is the w input, and the pushbutton KEY 0 is the clock input that is applied manually. The LED LEDR9 shows the output z, and the state of system is shown on LEDR2−0.
For this part, you should follow the following steps:

Figure 1: Required timing for the output z.

Figure 2: A state diagram for the FSM.
// SW[ 0 ] : reset signal
// SW[ 1 ] : input signal (w)
// KEY[ 0 ] : clock
// LEDR[ 2 : 0 ] : current state // LEDR[ 9 ] : output ( z )
module sequence detector (SW, KEY, LEDR); input [9 :0 ] SW; input [3 :0 ] KEY; output [9 :0 ] LEDR; wire w, clock , resetn , z ; reg [2 :0 ] y Q , Y D; // y Q represents current state , Y D represents next state localparam A = 3 ’b000 , B = 3 ’b001 , C = 3 ’b010 , D = 3 ’b011 , E = 3 ’b100 , F = 3 ’b101 , G = 3 ’b110 ;
// Connect inputs and outputs to internal wires assign w = SW[ 1 ] ; assign clock = ˜KEY[ 0 ] ; assign resetn = SW[ 0 ] ; assign LEDR[9] = z ; assign LEDR[2 :0 ] = y Q ;
// State table
// The state table should only contain the logic for state transitions // Do not mix in any output logic . The output logic should be handled separately . // This w i l l make i t easier to read , modify and debug the code .
always @(∗) begin // Start of s t a t e t a b l e case (y Q)
A: begin if (!w) Y D = A; else Y D = B; end
B: begin if (!w) Y D = A; else Y D = C; end
C: . . . // To be completed by you !
D: . . . // To be completed by you !
E: . . . // To be completed by you !
F: . . . // To be completed by you !
G: . . . // To be completed by you !
default : Y D = A; endcase
end // End of s t a t e t a b l e
// State Register ( i . e . , FFs) always @(posedge clock ) begin // Start of state FFs ( state register ) if ( resetn == 1 ’b0) yQ <= A;
else
yQ <= Y D;
end // End of state FFs ( state register )
// Output logic
// Set z to 1 to turn on LED when in relevant states assign z = ((y Q == ???) | | (y Q == ???)); // To be completed by you !
endmodule
Figure 3: Starter Verilog code for the FSM (sequence detector.v)
1. Begin with the starter code sequence_detector.v (Figure 3) that we provided to you (on Quercus, as well as in the appendices of this handout).
2. Answer the following questions in your prelab: given the starter code, is the resetn signal is an synchronous or asynchronous reset? Is it active high, or active low? Given this, what do you have to do in simulation to reset the FSM to the starting state? (PRELAB)
3. Complete the state table showing how the present state and input value determine the next state and the output value. Fill in all the missing parts of the template code to implement the FSM based on the state table you derived. Include completed code in your prelab. (PRELAB)
4. Simulate your circuit using ModelSim for a variety of input settings, ensuring the output waveforms are correct. Include a few screenshots that shows the simulation output. (PRELAB)
5. Create a new Quartus Prime project for your circuit. Make sure to store it in your W: drive; select the correct FPGA device (5CSEMA5F31C6); and import the pin assignments. Compile the project. (IN-LAB)
6. Download the compiled circuit into the FPGA. Test the functionality of the circuit on your board. When you are sure that it is working correctly, show it to TAs. (IN-LAB)
5 Part II
Most non-trivial digital circuits can be separated into two main functions. One is the datapath where the data flows and the other is the control path that manipulates the signals in the datapath to control the operations performed and how the data flows through the datapath. In previous labs, you learned how to construct a simple ALU, which is a common datapath component. In Part I of this lab you constructed a simple finite state machine (FSM), which is the most common component used to implement a control path. Now you will see how to implement an FSM to control a datapath so to perform a useful operation. This is an important step towards building a microprocessor as well as any other computing circuit.
In this part, you are given a datapath and a FSM that controls it to compute A2 + C. Using the given datapath, you should implement a different FSM that controls the datapath to perform the following computation:
Cx2 + Bx + A
The values of x, A, B and C will be preloaded by the user on the switches before the computation begins.
Figure 4 shows the block diagram of the datapath you will build. There are a few things to note about this diagram:
• Reset signals are not shown to reduce clutter, but do not forget to include them when writing your Verilog code.
• The datapath will operate on 8-bit unsigned values. Assume that the input values are small enough to not cause any overflows at any point in the computation, i.e., no results will exceed 28−1 = 255. • The ALU needs to perform only addition and multiplication, but you could use a variation of the ALU you built previously to have more operations available for solving other equations if you wish to try some things on your own.
• There are four registers Rx, RA, RB and RC used at the start to store the values of x, A, B and C, respectively. The registers RA and RB can be overwritten during the computation.
• There is one output register, RR, that captures the output of the ALU and displays the value in binary on the LEDs and in hexadecimal on the HEX displays.
• Two 8-bit-wide, 4-to-1 multiplexers at the inputs to the ALU are used to select which register values are input to the ALU.
• All registers have enable signals to determine when they are to load new values and an active low synchronous reset.

Figure 4: Block diagram of datapath.
The provided circuit should operate in the following manner:
• After an active low synchronous reset on KEY 0, you will input the value for RA on switches SW[7 : 0].
• When KEY 1 is pushed and released, RA will be loaded. Then you will input the next value on the switches that will be loaded into RB, and press and release KEY 1. You repeat this to load RC and RX.
• Computation will start after KEY 1 is pressed and released for loading RX.
• When computation is finished, the final result will be loaded into RR.
• This final result should be displayed on LEDR7−0 in binary and HEX0 and HEX1 in hex.
Note that KEY 1 is NOT your clock! You will use the 50 MHz clock available through input CLOCK 50 as your clock.
Perform the following steps for this part:
1. Examine the provided starter Verilog code for this part (poly_function.v, which is available on Quercus, as well as in the appendices of this handout). This is a major step in this part of the lab. You will not need to write much Verilog yourself, but you will need to fully understand the circuitry described by the provided Verilog to be able to make your modifications. (PRELAB)
2. Determine a sequence of steps similar to the datapath example shown in lecture that controls your datapath to perform the required computation. You should draw a table that shows the state of the Registers and control signals for each cycle of your computation. Include this table in your prelab. (PRELAB)
3. Draw a state diagram for your controller starting with the register load states provided in the example FSM. Include the state diagram in your prelab. (PRELAB)
4. Modify the provided FSM code to implement your controller and synthesize it. You should only modify the control module. Include your modified code in the prelab. (PRELAB)
5. To examine the circuit produced by Quartus Prime open the RTL Viewer tool (Tools > Netlist
Viewers > RTL Viewer). Find (on the left panel) and double-click on the box shown in the circuit
that represents the finite state machine, and determine whether the state diagram that it shows properly corresponds to the one you have drawn. To see the state codes used for your FSM, open the Compilation Report, select the Analysis and Synthesis section of the report, and click on State Machines. Include a screenshot of the generated FSM in your prelab. (PRELAB)
6. Simulate your circuit with ModelSim for a variety of input settings, ensuring the output waveforms are correct. It is recommended that you start by simulating the datapath and controller modules separately. Only when you are satisfied that they are working individually should you combine them into the full design. Why is this approach better? (Hint: Consider the case when your design has 20 different modules.) Include few screenshots of simulation output in your prelab.
(PRELAB)
7. Compile your project in Quartus, program the FPGA in DE1 board, and test it with various inputs. After you are satisfied that your circuit is working properly, show it to TAs. (IN-LAB)the functionality of the circuit on the FPGA board.
6 Part III (Optional)
Note: Only start working on this part if you already completed other parts. This is an optional part that provides a more challenging exercise for you to further test your knowledge.
Addition, subtraction and multiplication are much easier to build in hardware than division. So division is the most complex operation in hardware. For this part, you will design a 4-bit restoring divider using a finite state machine.
Figure 5 shows an example of how the restoring divider works. This mimics what you do when you do long division by hand. In this specific example, number 7 (Dividend) is divided by number 3 (Divisor). The restoring divider starts with Register A set to 0. The Dividend is shifted left and the bit shifted out of the left most bit of the Dividend (called the most significant bit or MSB) is shifted into the least significant bit (LSB) of Register A as shown in Figure 6.
The Divisor is then subtracted from Register A. This is equivalent to adding the 2’s complement of the Divisor (11101 for the example in Figure 5) to Register A. If the MSB of Register A is a 1, then we restore Register A back to its original value by adding the Divisor back to Register A, and set the LSB of the Dividend to 0. Else, we do not perform the restoring addition and immediately set the LSB of the Dividend to 1.
This cycle is performed until all the bits of the Dividend have been shifted out. Once the process is complete, the new value of the Dividend register is the Quotient, and Register A will hold the value of the Remainder.
To implement this part, you will use SW 3−0 for the divisor value and SW 7−4 for the dividend value. Use CLOCK 50 as the clock signal, KEY 0 as a synchronous active high reset, and KEY 1 as the Go signal to start computation. The output of the Divisor will be displayed on HEX0, the Dividend will be displayed on HEX2, the Quotient on HEX4, and the Remainder on HEX5. Set the remaining HEX displays to 0. Also display the Quotient on LEDR.
Structure your code in the same way as you were shown in Part II and follow these steps for this part:
1. Draw a schematic for the datapath of your circuit. It will be similar to Figure 6. You should show how you will initialize the registers, where the outputs are connected to, and include all the control signals that you require.
2. Draw the state diagram that controls your datapath.

Figure 5: An example of how a restoring divider works.

Figure 6: Block diagram of restoring divider.
3. Draw the schematic for your controller module.
4. Draw the top-level schematic showing how the datapath and controller are connected as well as the inputs and outputs to your top-level circuit.
5. Write the Verilog code that implements your circuit.
6. Simulate your circuit in ModelSim for a variety of input settings.
7. After you are satisfied with your simulations, download and test it on the FPGA board.

Appendices: Source Codes
A sequence detector.v
// SW[ 0 ] : reset signal
// SW[ 1 ] : input signal (w)
// KEY[ 0 ] : clock
// LEDR[ 2 : 0 ] : current state // LEDR[ 9 ] : output ( z )
module sequence detector (SW, KEY, LEDR); input [9 :0 ] SW; input [3 :0 ] KEY; output [9 :0 ] LEDR; wire w, clock , resetn , z ; reg [2 :0 ] y Q , Y D; // y Q represents current state , Y D represents next state localparam A = 3 ’b000 , B = 3 ’b001 , C = 3 ’b010 , D = 3 ’b011 , E = 3 ’b100 , F = 3 ’b101 , G =
// Connect inputs and outputs to internal wires assign w = SW[ 1 ] ; assign clock = ˜KEY[ 0 ] ; assign resetn = SW[ 0 ] ; assign LEDR[9] = z ; assign LEDR[2 :0 ] = y Q ;
// State table
// The state table should only contain the logic for state transitions
// Do not mix in any output logic . The output logic should be handled separately .
// This w i l l make i t easier to read , modify and debug the code .
always @(∗) begin // Start of s t a t e t a b l e case (y Q)
A: begin if (!w) Y D = A;
else Y D = B; end
B: begin if (!w) Y D = A;
else Y D = C;
end
C: . . . // To be completed by you !
D: . . . // To be completed by you !
E: . . . // To be completed by you !
F: . . . // To be completed by you !
G: . . . // To be completed by you !
default : Y D = A;
endcase
end // End of s t a t e t a b l e
// State Register ( i . e . , FFs) always @(posedge clock ) begin // Start of state FFs ( state register ) if ( resetn == 1 ’b0) yQ <= A;
else
yQ <= Y D;
end // End of state FFs ( state register )
// Output logic
// Set z to 1 to turn on LED when in relevant states assign z = ((y Q == ???) | | (y Q == ???)); // To be completed by you !
endmodule
B poly function.v
//Sw[7:0] data in
//KEY[0] synchronous reset when pressed
//KEY[1] go signal
//LEDR displays result
//HEX0 & HEX1 also displays result
module fpga top (SW, KEY, CLOCK 50, LEDR, HEX0, HEX1); input [9 :0 ] SW; input [3 :0 ] KEY; input CLOCK 50; output [9 :0 ] LEDR; output [6 :0 ] HEX0, HEX1;
wire resetn ; wire go ;
wire [7 :0 ] data result ; assign go = ˜KEY[ 1 ] ; assign resetn = KEY[ 0 ] ;
part2 u0(
. clk (CLOCK 50) ,
. resetn ( resetn ) ,
. go(go ) ,
. datain (SW[7:0]) ,
. data result ( data result )
);
assign LEDR[9 :0 ] = {2 ’b00 , data result };
hex decoder H0(
. hex digit ( data result [3:0]) ,
. segments (HEX0)
);
hex decoder H1(
. hex digit ( data result [7:4]) ,
. segments (HEX1)
);
endmodule
module part2 ( input clk , input resetn , input go , input [7 :0 ] data in , output [7 :0 ] data result
);
// lo ts of wires to connect our datapath and control wire ld a , ld b , ld c , ld x , ld r ; wire ld alu out ; wire [1 :0 ] alu select a , alu select b ; wire alu op ;
control C0(
. clk ( clk ) ,
. resetn ( resetn ) ,
. go(go ) ,
. ld alu out ( ld alu out ) ,
. ld x ( ld x ) , . ld a ( ld a ) ,
. ld b ( ld b ) , . ld c ( ld c ) , . ld r ( ld r ) ,
. alu select a ( aluselecta ) , . alu select b ( alu select b ) ,
. alu op ( alu op )
);
datapath D0(
. clk ( clk ) ,
. resetn ( resetn ) ,
. ld alu out ( ld alu out ) ,
. ld x ( ld x ) , . ld a ( ld a ) ,
. ld b ( ld b ) , . ld c ( ld c ) , . ld r ( ld r ) ,
. alu select a ( aluselecta ) , . alu select b ( alu select b ) ,
. alu op ( alu op ) ,
. data in ( data in ) ,
. data result ( data result )
);
endmodule
module control ( input clk , input resetn , input go ,
output reg ld a , ld b , ld c , ld x , ld r , output reg ld alu out , output reg [1 :0 ] alu select a , alu select b , output reg alu op
);
reg [3 :0 ] current state , next state ;
localparam S LOAD A = 4 ’d0 ,
S LOAD A WAIT = 4 ’d1 ,
S LOAD B = 4 ’d2 ,
S LOAD B WAIT = 4 ’d3 ,
S LOAD C = 4 ’d4 ,
S LOAD C WAIT = 4 ’d5 ,
S LOAD X = 4 ’d6 ,
S LOAD X WAIT = 4 ’d7 ,
S CYCLE 0 = 4 ’d8 ,
SCYCLE1 = 4 ’d9 ,
SCYCLE2 = 4 ’d10 ;
// Next state logic aka our state table always@(∗) begin : state table case ( current state )
S LOAD A: next state = go ? S LOAD A WAIT : S LOAD A; // Loop in current
S LOAD A WAIT: next state = go ? S LOAD A WAIT : S LOAD B; // Loop in cur S LOAD B: next state = go ? S LOAD B WAIT : S LOAD B; // Loop in current
S LOAD B WAIT: next state = go ? S LOAD B WAIT : S LOAD C; // Loop in cur S LOAD C: next state = go ? S LOAD C WAIT : S LOAD C; // Loop in current
S LOAD C WAIT: next state = go ? S LOAD C WAIT : S LOAD X; // Loop in cur
S LOAD X: next state = go ? S LOAD X WAIT : S LOAD X; // Loop in current
S LOAD X WAIT: next state = go ? S LOAD X WAIT : S CYCLE 0; // Loop in cu
SCYCLE0: next state = S CYCLE 1;
S CYCLE 1: next state = S LOAD A; // we w i l l be done our two operations , default : next state = S LOAD A; endcase
end // s t a t e t a b l e
// Output logic aka a l l of our datapath control signals always @(∗)
begin : enable signals
// By default make a l l our signals 0 ld alu out = 1 ’b0 ; ld a = 1 ’b0 ; ld b = 1 ’b0 ; ld c = 1 ’b0 ; ld x = 1 ’b0 ; ld r = 1 ’b0 ;
aluselecta = 2 ’b00 ; alu select b = 2 ’b00 ;
aluop = 1 ’b0 ;
case ( current state )
S LOAD A: begin ld a = 1 ’b1 ;
end
S LOAD B: begin ld b = 1 ’b1 ;
end
S LOAD C: begin ld c = 1 ’b1 ;
end
S LOAD X: begin ld x = 1 ’b1 ;
end
S CYCLE 0: begin // Do A <− A ∗ A ld alu out = 1 ’b1 ; ld a = 1 ’b1 ; // store result back into A alu select a = 2 ’b00 ; // Select register A alu select b = 2 ’b00 ; // Also select register A
alu op = 1 ’b1 ; // Do multiply operation
end
S CYCLE 1: begin ld r = 1 ’b1 ; // store result in result register alu selecta = 2 ’b00 ; // Select register A alu select b = 2 ’b10 ; // Select register C alu op = 1 ’b0 ; // Do Add operation end
// default : // don ’ t need default since we already made sure a l l of our output endcase
end // enable signals
// current state registers always@(posedge clk ) begin : state FFs if (! resetn )
current state <= S LOAD A;
else
current state <= next state ;
end // state FFS endmodule
module datapath ( input clk , input resetn , input [7 :0 ] data in , input ld alu out , input ld x , ld a , ld b , ld c , input ld r , input alu op , input [1 :0 ] alu selecta , alu select b , output reg [7 :0 ] data result
);
// input registers reg [7 :0 ] a , b, c , x ;
// output of the alu reg [7 :0 ] aluout ; // alu inputmuxes reg [7 :0 ] alu a , alu b ;
// Registers a , b , c , x with respective input logic always @ (posedge clk ) begin if (! resetn ) begin a <= 8 ’d0 ; b <= 8 ’d0 ; c <= 8 ’d0 ; x <= 8 ’d0 ;
end
else begin if ( ld a ) a <= ld alu out ? aluout : datain ; // load aluout i f load alu out sign
if ( ld b ) b <= ld alu out ? aluout : datain ; // load aluout i f load alu out sign
if ( ld x ) x <= data in ;
if ( ld c ) c <= data in ; end
end
// Output result register always @ (posedge clk ) begin if (! resetn ) begin data result <= 8 ’d0 ;
end
else if ( ld r ) data result <= alu out ;
end
// The ALU input multiplexers always @(∗) begin case ( alu select a )
2 ’d0 :
alu a = a ;
2 ’d1 :
alu a = b;
2 ’d2 :
alu a = c ;
2 ’d3 :
alu a = x ;
default : alu a = 8 ’d0 ; endcase case ( alu select b )
2 ’d0 :
alu b = a ;
2 ’d1 :
alu b = b;
2 ’d2 :
alu b = c ;
2 ’d3 :
alu b = x ;
default : alu b = 8 ’d0 ;
endcase
end
// The ALU always @(∗) begin : ALU // alu case ( alu op )
0: begin
alu out = alu a + alu b ;
end
1: begin //performs addition
alu out = alu a ∗ alu b ; //performs multiplication
end
default : alu out = 8 ’d0 ;
endcase end endmodule
module hex decoder ( hex digit , segments ); input [3 :0 ] hex digit ; output reg [6 :0 ] segments ;
always @(∗) case ( hex digit )
4 ’h0 : segments = 7 ’ b1000000 ;
4 ’h1 : segments = 7 ’ b1111001 ;
4 ’h2 : segments = 7 ’ b0100100 ;
4 ’h3 : segments = 7 ’ b0110000 ;
4 ’h4 : segments = 7 ’ b0011001 ;
4 ’h5 : segments = 7 ’ b0010010 ;
4 ’h6 : segments = 7 ’ b0000010 ;
4 ’h7 : segments = 7 ’ b1111000 ;
4 ’h8 : segments = 7 ’ b0000000 ;
4 ’h9 : segments = 7 ’ b0011000 ;
4 ’hA: segments = 7 ’ b0001000 ;
4 ’hB: segments = 7 ’ b0000011 ;
4 ’hC: segments = 7 ’ b1000110 ;
4 ’hD: segments = 7 ’ b0100001 ;
4 ’hE: segments = 7 ’ b0000110 ;
4 ’hF: segments = 7 ’ b0001110 ; default : segments = 7 ’ h7f ;
endcase endmodule