Part 4: FSM Sequential Circuit

Objective

This tutorial contains information about FSM sequential circuit and several design examples of FSM sequential circuit.

Source Code

This repository contains all of the code required in order to follow this tutorial.

zybo_tutorial/part_4 at main · weenslab/zybo_tutorialGitHub

References

• Pong P. Chu, FPGA Prototyping by Verilog Examples, https://onlinelibrary.wiley.com/doi/book/10.1002/9780470374283

1. Finite State Machine

An FSM (finite state machine) is used to model a system that transits among a finite number of internal states. The transitions depend on the current state and external input. Unlike a regular sequential circuit, the state transitions of an FSM do not exhibit a simple, repetitive pattern.

1.1. Mealy and Moore Outputs

The basic block diagram of synchronous FSM is similar to the regular sequential circuit, as shown in the following figure. It consists of a state register, next-state logic, and output logic. An FSM is known as a Moore machine if the output is only a function of state and is known as a Mealy machine if the output is a function of state and external input.

Figure 1. Synchronous FSM

1.2. FSM Representation

An FSM is usually specified by an abstract state diagram or algorithmic state machine (ASM) chart.

The following figure shows an example of a state diagram that consists of a single node and its transition arcs. The arc is taken when the corresponding expression is evaluated true. The Moore output value is placed inside the circle. The Mealy output is placed with the transition arcs.

Figure 2. State diagram node

The following figure shows an example of a ASM chart that consists of a single block. An ASM block consists of one state box and an optional network of decision boxes and conditional output boxes. A state box represents a state in an FSM, and the asserted Moore output values are listed inside the box.

A decision box tests the input condition and determines which exit path to take, true (T) or false (F). A conditional output box lists asserted Mealy output values and is usually placed after a decision box. It indicates that the listed output signal can be activated only when the corresponding condition in the decision box is met.

Figure 3. ASM chart block

2. Finite State Machine with Data Path

An FSMD (finite state machine with data path) combines an FSM and regular sequential circuits. The FSM, which is sometimes known as a control path, examines the external commands and status and generates control signals to specify operation of the regular sequential circuits, which are known collectively as a data path.

2.1. Single RT Operation

An RT operation specifies data manipulation and transfer for a single destination register. It is represented by the notation

$$r_{dest}\leftarrow f(r_{src1}, r_{src2}, ...,r_{srcn})$$

where $r_{dest}$ is the destination register, $r_{src1}$, $r_{src2}$, and $r_{srcn}$ are the source registers, and $f(.)$ specifies operation to be performed. The notation indicates that the contents of the source registers are fed to the $f(.)$ function, which is realized by a combinational circuit, and the result is passed to the input of the destination register and stored in the destination register at the next rising edge of the clock.

Following are several representative RT operations:

• $r_1\leftarrow 0$. A constant 0 is stored in $r_1$ register.

• $r_1\leftarrow r_1+r_2$. The summation of the $r_1$ and $r_2$ registers is written to the $r_1$ register.

• $r_1\leftarrow r_1<<2$. The $r_1$ register is shifted left two positions and then written back to itself.

• $r_1\leftarrow r_1$. The content of the $r_1$ register is written back to itself.

A single RT operation can be implemented by constructing a combinational circuit for the $f(.)$ function and connecting the input and output of the registers. The following figure shows an example circuit of RT operations. For clarity, we use the _reg and _next suffixes to represent the output and input of a register, respectively. For example, $r_1\leftarrow r_1<<2$ operation actually means that:

• r_next = r_reg << 2;

• r_reg <= r_next at the rising edge of the clock.

Figure 4. An example circuit of RT operations

In this circuit, the previous RT operations are implemented using a combinational circuit that consists of a 4-to-1 multiplexer, adder, and shifter. The state register state_reg of the FSM controls the selection signal of the multiplexer and thus chooses the result of the desired RT operation.

2.2. ASMD Chart

The ASM chart can be extended to incorporate RT operations and call it an ASMD (ASM with data path) chart. The following figure shows an example of a ASMD chart that consists of a single block.

Figure 5. An example of ASMD chart block

Depending on the a > b condition, the FSMD performs either r2 ← r2 + a or r2 ← r2 + b. Note that all operations are done in parallel inside an ASMD block, so that wee need to use multiplexer to route the desired value to r2 as shown in the following figure.

Figure 6. An example circuit of the ASMD chart block

2.3. FSMD System

The conceptual block diagram of an FSMD is divided into a data path and a control path, as shown in the following figure. The data path performs the required RT operations. It consists of:

• Data registers: store the intermediate computation results.

• Functional units: perform the functions specified by the RT operations.

• Routing network: routes data between the storage registers and the functional units.

The data path follows the control signal to perform the desired RT operations and generates the internal status signal.

Figure 7. Conceptual block diagram of an FSMD

The control path is an FSM. As a regular FSM, it contains a state register, next-state logic, and output logic. It uses the external command signal and the data path's status signal as the input and generates the control signal to control the data path operation. The FSM also generates the external status signal to indicate the status of the FSMD operation.

3. Design Examples

3.1. FSM

In this example, we consider a simple FSM example. The FSM is represented both using a state diagram and an ASM chart as in the following figure. It consists of three states and both Mealy output x, and Moore output y. The inputs to the FSM are a and b.

Figure 8. State diagram of a simple FSM example

Figure 9. ASM chart of a simple FSM example

The procedure of developing code for an FSM is similar to that of a regular sequential circuit. We first separate the state register and then derive the code for the combinational next-state logic and output logic.

In the following code, the output logic is separated as a continuous assignment, so the code has four segments (state register, next state logic, Mealy output, and Moore output). The key part is the next state logic. It uses a case statement. The code for each state basically follows state diagram and ASM chart.

fsm_eg_4seg.v

module fsm_eg_4seg
    (
        input wire        clk,
        input wire        rst_n,
        input wire        a,
        input wire        b,
        output wire [7:0] x,
        output wire [7:0] y
    );
    
    // Symbolic state declaration
    localparam [1:0] S0 = 2'b00,
                     S1 = 2'b01,
                     S2 = 2'b10;
    // Signal declaration
    reg [1:0] state_reg, state_next;

    // Segment 1: State register
    always @(posedge clk)
    begin
        if (!rst_n)
            state_reg <= S0;
        else
            state_reg <= state_next;
    end
    
    // Segment 2: Next state logic
    always @(*)
    begin
        state_next = state_reg;
        case (state_reg)
            S0: begin
                if (a == 1'b1)
                    if (b == 1'b1)
                        state_next = S2;
                    else
                        state_next = S1;
                else
                    state_next = S0;
            end
            S1: begin
                if (a == 1'b1)
                    state_next = S0;
                else
                    state_next = S1;
            end
            S2: begin
                state_next = S0;
            end
        endcase
    end

    // Segment 3: Mealy output logic
    assign x = ( ((state_reg == S0) || (state_reg == S2)) && a && b ) ?
               8'd168 : 8'd0;
    
    // Segment 4: Moore output logic
    assign y = (state_reg == S1) ? 8'd168 : 8'd0;
    
endmodule

An alternative code is to merge the output logic with the next state logic, so the code has only two segments (state register, next state logic and output logic). Both of the codes should produce the same results.

fsm_eg_2seg.v

module fsm_eg_2seg
    (
        input wire       clk,
        input wire       rst_n,
        input wire       a,
        input wire       b,
        output reg [7:0] x,
        output reg [7:0] y
    );
    
    // Symbolic state declaration
    localparam [1:0] S0 = 2'b00,
                     S1 = 2'b01,
                     S2 = 2'b10;
    // Signal declaration
    reg [1:0] state_reg, state_next;

    // Segment 1: State register
    always @(posedge clk)
    begin
        if (!rst_n)
            state_reg <= S0;
        else
            state_reg <= state_next;
    end
    
    // Segment 2: Next state logic and output logic
    always @(*)
    begin
        state_next = state_reg;
        x = 8'd0;
        y = 8'd0;
        case (state_reg)
            S0: begin
                if (a == 1'b1)
                    if (b == 1'b1)
                    begin
                        x = 8'd168;
                        state_next = S2;
                    end
                    else
                        state_next = S1;
                else
                    state_next = S0;
            end
            S1: begin
                y = 8'd168;
                if (a == 1'b1)
                    state_next = S0;
                else
                    state_next = S1;
            end
            S2: begin
                if (a && b)
                    x = 8'd168;
                state_next = S0;
            end
        endcase
    end
    
endmodule

The following code is the testbench for the FSM example.

fsm_eg_4seg_tb.v

`timescale 1ns / 1ps

module fsm_eg_4seg_tb();
    localparam T = 10;
    
    reg clk, rst_n;
    reg a, b;
    wire [7:0] x, y;

    fsm_eg_4seg dut(.clk(clk), .rst_n(rst_n), .a(a), .b(b), .x(x), .y(y));
    
    always
    begin
        clk = 0;
        #(T/2);
        clk = 1;
        #(T/2);
    end
    
    initial
    begin
        a = 0; b = 0;
    
        rst_n = 0; #T;
        rst_n = 1; #T;
        
        a = 1; b = 0; // Go to state S1
        #T;
        a = 1; b = 0; // Go back to state S0
        #T;    
        a = 1; b = 1; // Go to state S2
        #T;           
        a = 0; b = 0;        
    end
    
endmodule

This is the simulation result of the four segments FSM example. The Moore output y changes when the FSM enters state S1. It follows the rising edge of the clock. But the Mealy output x changes when a and b are both one. It doesn't follow the rising edge of the clock. It follows external signals. This is the difference between Moore and Mealy outputs.

Figure 10. Simulation waveform of the four segments FSM

This is the simulation result of the two segments FSM example. The result is similar to the four segment FSM example.

Figure 11. Simulation waveform of the 2 segments FSM

3.2. Fibonacci

In this example, we consider a Fibonacci example for an FSMD system. The Fibonacci numbers constitute a sequence defined as

$$fib(i) = \begin{cases} 0 & \text{if $i$ = $0$}\\ 1 & \text{if $i$ = $1$}\\ fib(i-1)+fib(i-2) & \text{if $i$ > $1$} \end{cases}$$

The Fibonacci number can be calculated iteratively, from 0 to desired $i$. This approach requires two temporary registers to store the two most recently calculated values i.e., $fib(i-1)$ and $fib(i-2)$ and one index register to keep track of the number of iterations.

In the following figure, t0 and t1 are the temporary storage registers and n is the index register. There are additional signals, which are the start signal that signals the beginning of operation and two status signals: ready, which indicates that the circuit is idle and ready to take new input, and done_tick, which is asserted for one clock cycle when the operation is completed.

Figure 12. ASM chart of Fibonacci

This is the implementation of the Fibonacci module in Verilog.

fibonacci.v

module fibonacci
    (
        input wire         clk,
        input wire         rst_n,
        input wire         start,
        input wire [4:0]   i,
        output wire        ready,
        output reg         done_tick,
        output wire [19:0] f
    );
    
    // Symbolic state declaration
    localparam [1:0] IDLE = 2'b00,
                     OP   = 2'b01,
                     DONE = 2'b10;
    
    // Signal declaration
    reg start_reg;
    wire start_tick;
    reg [1:0] state_reg, state_next;
    reg [19:0] t0_reg, t0_next;
    reg [19:0] t1_reg, t1_next;
    reg [19:0] n_reg, n_next;

    // Rising edge detector
    always @(posedge clk)
    begin
        if (!rst_n)
            start_reg <= 0;
        else
            start_reg <= start;
    end
    assign start_tick = start & ~start_reg; 
    
    // FSMD state and data registers
    always @(posedge clk)
    begin
        if (!rst_n)
        begin
            state_reg <= IDLE;
            t0_reg <= 0;
            t1_reg <= 0;
            n_reg <= 0;
        end
        else
        begin
            state_reg <= state_next;
            t0_reg <= t0_next;
            t1_reg <= t1_next;
            n_reg <= n_next;  
        end
    end
    
    // FSMD next state logic
    always @(*)
    begin
        state_next = state_reg;
        t0_next = t0_reg;
        t1_next = t1_reg;
        n_next = n_reg;      
        done_tick = 1'b0;
        case (state_reg)
            IDLE:
            begin
                if (start_tick)
                begin
                    t0_next = 0;
                    t1_next = 20'd1;
                    n_next = i;
                    state_next = OP;
                end
            end
            OP:
            begin
                if (n_reg == 0)
                begin
                    t1_next = 0;
                    state_next = DONE;
                end
                else if (n_reg == 1)
                begin
                    state_next = DONE;
                end
                else
                begin
                    t0_next = t1_reg;
                    t1_next = t0_reg + t1_reg;
                    n_next = n_reg - 1;                    
                end
            end
            DONE:
            begin
                done_tick = 1'b1;
                state_next = IDLE;
            end
        endcase
    end
    
    // Output
    assign f = t1_reg;
    assign ready = (state_reg == 0) ? 1 : 0;
    
endmodule

The following code is the testbench for the Fibonacci module.

fibonacci_tb.v

`timescale 1ns / 1ps

module fibonacci_tb();
    localparam T = 10;
    
    reg clk, rst_n, start;
    reg [4:0] i;
    wire ready, done_tick;
    wire [19:0] f;

    fibonacci dut(.clk(clk), .rst_n(rst_n), .start(start), .i(i),
                  .ready(ready), .done_tick(done_tick), .f(f));
    
    always
    begin
        clk = 0;
        #(T/2);
        clk = 1;
        #(T/2);
    end
    
    initial
    begin
        start = 0; i = 0;
    
        rst_n = 0; #T;
        rst_n = 1; #T;
        
        // Calculate fib(10)
        start = 1; i = 10; #T;     
    end
endmodule

This is the simulation result of the Fibonacci module.

Figure 13. Simulation waveform of the Fibonacci module

Then, we can add the Fibonacci module to the Vivado block design, add a virtual input/output (VIO) IP, and also add an integrated logic analyzer (ILA) IP.

Figure 14. Vivado block design for Fibonacci module

This is the constraints for this block design. We only use clock signal that has a period of 8.0 ns (125 Mhz).

#Clock signal
set_property -dict { PACKAGE_PIN L16   IOSTANDARD LVCMOS33 } [get_ports { clk }]; #IO_L11P_T1_SRCC_35 Sch=sysclk
create_clock -add -name sys_clk_pin -period 8.00 -waveform {0 4} [get_ports { clk }];

The following figure shows the synthesis result.

Figure 15. Summary of resource utilization after synthesis

We can view the detailed resource utilization. The Fibonacci module only uses 83 LUTs and 64 registers. Most of the resources are for the VIO and ILA IP.

Figure 16. The details of resource utilization after synthesis

From the result, we can see that the timing requirements are met for this 125 MHz clock. There is setup WNS value which is 1.223 ns. This means that we could have asked for a clock period that is shorter by 1.223 ns, and it would still be OK. So the requested clock period could have been 8.0 - 1.223 ns = 6.777 ns, which is about 147 MHz.

Figure 17. Timing constraint of the Fibonacci module

The following figure shows how we can control the Fibonacci module using the VIO interface in Vivado (after programming the FPGA). First, we have to set the reset to 1, and then set the value i; in this example, we set it to 10. Then the result of fib(10) is 55, which will be updated as shown in the output.

Figure 18. Testing the Fibonacci module using the VIO interface in Vivado

The following figure shows how we can observe the waveform of the counter module using the ILA interface in Vivado (after programming the FPGA). First, we have to set up the trigger signal for this ILA, which is the start signal. Then, on the VIO, we toggle the start to 1. Then the result of fib(10) is 55, which will be produced as shown in the output.

Figure 19. Testing the Fibonacci module using the ILA interface in Vivado

4. Conclusion

In this tutorial, we covered the FSM sequential circuit and several design examples of FSM sequential circuit.