What is a Finite State Machine?

FSMs are used to model systems that transit between a finite number of internal states. The transitions between different states depend on the current state and the external input. Hence FSMs are sequential circuits. Practically, FSMs are used as controllers of a larger digital system, examining the external input and current status to activate the appropriate control signals for rest of the system.

FSMs can also be part of an Analog system, helping calibrate analog components to improve performance in certain use cases.

Sequential Circuits

A sequential circuit is essentially a circuit with memory. While in combinational circuits the output depends merely on the input, in sequential circuits the output is a function of both the input and the internal memory of the circuit. In practice, all the storage elements are synchronized to a single clock and the data is sampled with respect to this global clock. This is known as the synchronized design methodology.

Basic block diagram of a sequential circuit looks something like this.

Code development follows separating the memory element (state register) and then the rest of the circuit is purely combinational similar to what we covered in the last blog.

Mealy and Moore

FSMs can further be classified into Mealy and Moore Machines. Block diagram of an FSM that elucidates the difference between Mealy and Moore Machines shown below.

An FSM is a Mealy machine if the output is a function of the external input and the internal state. Compared to that output of a moore machine only depends on the internal state.

FSM Basics

State Diagram

There are a multitude of ways to describe FSMs, from state diagrams and tables to algorithmic state machine (ASM) charts. All methods however have the same goal, to capture the FSM’s inputs, output and conditions for transitions between different states.

FSM Code Development

Similar to a sequential circuit we first try to separate the memory element and then write the combinational next state logic. The memory element in an FSM is nothing but the state register, to have symbolic state names we use the enumerated data type.

typedef enum {s0, s1, s2} state_type;
state_type state_reg, state_next;

localparam [1:0] s0 = 2'b00, s1 = 2'b01, s2 = 2'b10;

When an FSM is realized on hardware, the symbolic state names get mapped to binary representations. This process is called state encoding. By default System Verilog maps the enumerated data type to 32 bit Integers. The unused bits are discarded by the software during synthesis.

Your First FSM - Rising Edge Detector

State Diagram

The figure below shows a state diagram of an edge detector based on a Moore machine.

The zero and one states indicate the signal level, the edg state indicates movement from zero to one.

System Verilog Code

module moore_rising_edge
(
    input logic clk, reset,
    input logic level,
    output logic tick
);

typedef enum {zero, edg, one} state_type;
state_type state_reg, state_next;

always_ff @( posedge clk, posedge reset )
    if (reset)
        state_reg <= 0;
    else
        state_reg <= state_next;

always_comb 
begin
    state_next = state_reg;
    tick = 1'b0;
    case (state_reg)
        zero:
            if (level)
                state_next = edg;
        edg :
        begin
            tick = 1'b1;
            if (level)
                state_next = one;
            else
                state_next = zero;
        end

        one:
            if(~level)
                state_next = zero;
        default: state_next = zero;
    endcase
end


initial begin
    $dumpfile("fsm.vcd");
    $dumpvars;
end

endmodule

Python Test bench

As is with the rest of my blogs so far, we will use cocotb to get some quick results.

import cocotb
from cocotb.clock import Clock
from cocotb.triggers import RisingEdge
from cocotb.types import LogicArray
from cocotb.triggers import Timer, RisingEdge, ReadOnly, NextTimeStep, FallingEdge

@cocotb.test()
async def test_rising_edge(dut):

    clock = Clock(dut.clk, 1, units="ns")
    cocotb.start_soon(clock.start(start_high=False))
    dut.reset = 0
    dut.level = 0
    await Timer(10,'ns')
    # Assert initial output is unknown
    dut.level = 1
    await Timer(10,'ns')

Waveform

A Look Inside

I am a big fan of visualizing the circuit resulting from RTL synthesis. Yosys is a tool I used in my last blog but it has limited System Verilog support. The solution is synlig : a kind of plugin that extends the capabilities of Yosys. Assuming you already have Yosys installed (refer to the previous blog if you don’t), installation is pretty simple.

apt install -y jq curl wget tk
curl https://api.github.com/repos/chipsalliance/synlig/releases/latest | jq -r '.assets | .[] | select(.name | startswith("synlig")) | .browser_download_url' | xargs wget -O - | tar -xz
export PATH=`pwd`/synlig:$PATH

Usage is similar to Yosys.

synlig
# read input file
read_systemverilog filename.sv
# convert to DFFs and muxes
proc
# perform some optimization
opt
# visualize the design
show

We have a case statement and some if statements inside the case statement. So we should have some kind of priority routing network inside of a multiplexing network along with something to store our state in.

And that is what we get!

Parting Thoughts

This was a slightly more complicated blog as compared to my usual blogs but I feel that is the nature of hardware design, it gets really hard before getting really easy. The exponential charging curve is not just for capacitors. As usual, appreciate any feedback you guys can send my way and all the code is on GitHub.

In the next blog, we will be synthesize some design for an FPGA and actually get it running on the FPGA so stay tuned for that!