fsm-verilog.md

A finite state machine is a way of representing the logic of a system that has some kind of internal state. It defines a set of distinct states which a system can be in, as well as which states can transition to which other states and which inputs make the state change from one to another. For example, a simple finite state machine might represent a train with three states: Boarding, InTransit, and Disembarking. The train starts out in the Boarding state, and from the Boarding state can only go to InTransit (since people don't get on a train just to get off again). Once the train is InTransit, it can only either stay that way, or go to Disembarking. Only when it is in the Disembarking state can it go to the Boarding state again, since you can't board a train before it's empty. The transitions between these states would happen according to some input to the machine from somewhere else in your program --- maybe a "next" button, for instance.

There are two kinds of finite state machines: Mealy machines, and Moore machines. A Mealy finite state machine determines its output as a function of both the current state and the current input, while a Moore machine determines its output only as a function of the current state. Thus for a Moore machine, as long as the state is constant, the output is constant, while a Mealy machine only gives you an output when you give it an input, and then it varies depending on the input you give it and the current state. When you draw or graph these, you represent each state as a bubble with a label in it, with the valid transitions as lines (labelled with the input that causes that state transition) with arrows connecting those bubbles; for a Moore machine you write the output associated with a state alongside the state bubble, whereas for a Mealy machine you write the outputs on the state transition arrows themselves, alongside the input that causes that transition.

To design a finite state machine, all you have to do is think about all the different states your program can be in, and then what inputs you want to do to each state. Then, you need to look at that graph and think about the most natural way to get the outputs you want from that graph. Sometimes you'll want a Mealy machine, and sometimes a Moore machine.

The primary way that you design finite state machines in Verilog is with behavioral switch-case statements, a state register, and localparams to name the different states. If your finite state machine has more than two states, your state register is going to have to be multiple bits, so to figure out the size your state register needs to be, you need to count how many states you have and choose a binary number that'll fit that many states. For our simple train example, that might look something like this:

module FSM
(
    input clk,
    input reset
);

    reg [1:0] state; // Two bits can represent four different states, which is enough for our three states.
    localparam Boarding = 2'b00;
    localparam InTransit = 2'b01;
    localparam Disembarking = 2'b10;
    
    always @(posedge clk) begin
        if (reset)
            state = Boarding;
        else begin
            case (state)
            Boarding: begin
                state = InTransit;
            end
            InTransit: begin
                state = Disembarking;
            end
            Disembarking: begin
                state = Boarding;
            end
            endcase
        end
    end
endmodule

You can also have much more complex logic in the state transitions as well, as well as additional state registers. Here is an example of what it might look like if we wanted the state machine to stay in the "InTransit" stage for a particular amount of time:

module FSM
(
    input clk,
    input reset,
    output reg [1:0] out
);

    reg [1:0] state;
    reg [8:0] counter;
    localparam Boarding = 2'b00;
    localparam InTransit = 2'b01;
    localparam Disembarking = 2'b10;
    
    always @(posedge clk) begin
        if (reset) begin
            state = Boarding;
            out = 2'b00;
        end else begin
            case (state)
            Boarding: begin
                state = InTransit;
                counter = 0;
            end
            InTransit: begin
                if (counter < 2)
                    counter = counter + 1;
                else
                    state = Disembarking;
            end
            Disembarking: begin
                state = Boarding;
                counter = 0;
            end
            endcase
            
            // This is a Moore machine
            out = state;
        end
    end
endmodule

Anyway, I hope that was helpful!

Correction: finite state machines are a way of representing the internal logic of a system that has a finite number of internal states! That was a key bit of information that was missing lol.