Finite state machines

Combinational logic computes and sequential logic remembers. A finite state machine puts the two together to make decisions over time. It holds a small amount of state that names where a process currently is, and each clock it looks at that state and the inputs to decide both what to do now and which state to move to next. Controllers are almost always state machines. They sequence a memory access, drive a protocol, wait for a handshake, or watch a stream for a pattern. This page builds one the disciplined way and uses it to introduce the two choices every state machine forces, the output style and the state encoding.

Moore and Mealy

A state machine comes in two flavors that differ only in where the outputs come from. In a Moore machine the outputs depend on the state alone, so they change only just after a clock edge and are naturally glitch-free and easy to reason about. In a Mealy machine the outputs depend on the state and the current inputs together, which lets it react one cycle sooner and often with fewer states, at the cost of outputs that can wiggle within a cycle as inputs move. A good default is Moore, because registered, state-only outputs are the calm ones to connect to the rest of a design. Reach for Mealy when a cycle of latency genuinely matters.

The three-block style

The coding style that keeps state machines readable and safe splits them into three separate blocks. One clocked block holds the state register and does nothing else. One combinational block computes the next state from the current state and inputs. A third piece, often a single assignment, derives the outputs. Keeping the state register apart from the next-state logic is what stops the accidental latches and the tangled code that a single monolithic block invites. The worked example is an overlapping sequence detector that raises found for one cycle every time the pattern 1011 completes on a serial input, where overlapping means the trailing 1 of one match can begin the next.

seq_detector.svmodule seq_detector (
    input  logic clk,
    input  logic rst,
    input  logic din,
    output logic found
);
    // one state per amount of the pattern matched so far
    localparam logic [2:0] IDLE = 3'd0, G1 = 3'd1, G10 = 3'd2,
                           G101 = 3'd3, DETECT = 3'd4;
    logic [2:0] state, next;

    // block 1: the state register, nothing else
    always_ff @(posedge clk)
        if (rst) state <= IDLE;
        else     state <= next;

    // block 2: next-state logic, pure combinational
    always_comb begin
        case (state)
            IDLE:   next = din ? G1     : IDLE;
            G1:     next = din ? G1      : G10;
            G10:    next = din ? G101    : IDLE;
            G101:   next = din ? DETECT  : G10;
            DETECT: next = din ? G1      : G10;   // overlap: trailing 1 is a prefix
            default: next = IDLE;
        endcase
    end

    // block 3: Moore output, a function of state only
    assign found = (state == DETECT);
endmodule

Each state names how much of the pattern has been matched. From G101, meaning 101 has been seen, a further 1 completes 1011 and enters DETECT, whose only job is to make found high for that one cycle. The interesting transition is out of DETECT. Because the pattern ended in a 1, and a single 1 is itself the start of a new match, DETECT moves on exactly as G1 would, which is what makes the detector overlapping rather than restarting from scratch. This is a Moore machine, so found is a clean function of the state and nothing else.

State encoding

The states above are written as plain binary numbers, and for a handful of states that is fine. The other common choice is one-hot, where each state gets its own flip-flop and exactly one is set at a time. One-hot spends more flip-flops but almost no logic to decode the current state, since testing a state is reading a single bit, and on an FPGA, where flip-flops sit next to every lookup table and are plentiful, that trade is often the faster one. Binary encoding uses the fewest flip-flops and suits a machine with many states. The reassuring part is that you rarely choose by hand. The synthesis tools pick an encoding for you and are good at it, and you can override the choice with an attribute when a specific machine wants a specific style. The value of knowing the two is reading the reports and understanding why a state-heavy design filled with flip-flops rather than logic.

Verifying it

Overlapping detection of 1011 has a clean independent reference. At every step, the pattern is present exactly when the last four input bits equal 1011, which is a four-bit sliding window. The testbench in the repository drives thousands of random bits, keeps that window beside the machine, and checks that found agrees with it on every cycle, which it does. The full module and its testbench live in the advanced-fpga-design repository, and make seq_detector runs the check.

State machines are the controllers. The next pages turn to the datapaths they steer, starting with arithmetic and the hardened multiply-accumulate that makes an FPGA good at signal processing and machine learning.

Next, arithmetic and the DSP slice.