10. Finite State Machines

A finite state machine (FSM) is the formal model for any sequential circuit. It is also one of the most useful abstractions in computer science. Entire programming languages (regular expressions, compilers, parsers, network protocols) are described in FSM terms.

10.1 Definition

An FSM has:

• A finite set of states.
• A set of input symbols.
• A transition function $\delta: \text{states} \times \text{inputs} \to \text{states}$ that, given current state and current input, gives the next state.
• An output function: either tied to states alone (Moore machine) or to (state, input) pairs (Mealy machine).
• An initial state to start in.

10.2 Moore vs Mealy

Moore machine. Output depends only on the current state. Outputs are tied to states. The output is "registered" (delayed by one clock relative to the input that caused the transition), and it is glitch-free because outputs only change at clock edges.

Mealy machine. Output depends on the current state and the current input. Outputs can react in the same clock cycle as the input change, but they can glitch if the input glitches.

Designers usually prefer Moore for clean signal output and easier timing analysis. Mealy can give smaller designs (fewer states needed) and faster reaction (output reacts in the same cycle), but glitch-cleanliness is lost.

10.3 The FSM design flow

1. Read the spec carefully. Identify the inputs, outputs, and the behavior you want.
2. Draw the state diagram. Circles for states (label with the state name and, for Moore, the output). Arrows for transitions, labeled with the input that triggers them (and, for Mealy, the resulting output).
3. Build the state table. Each row: current state, input, next state, (Mealy) output. For Moore, list outputs per state in a separate column.
4. State assignment. Choose binary codes for each state. Different codings change the size and speed of next-state logic.
5. Choose flip-flop type. D is the default; J, K, T sometimes useful.
6. Derive next-state and output equations. Either by K-map or, in HDL, by writing the case statement and letting synthesis do the work.
7. Build / write the HDL.
8. Verify with simulation, ideally with formal property verification on the state machine.

10.4 State assignment

If you have $S$ states, you need at least $\lceil \log_2 S \rceil$ flip-flops. Common encodings:

• Binary: minimum flip-flops. 8 states use 3 flip-flops. Next-state logic can be complex because every flip-flop input is a function of all current state bits.
• Gray code: minimum flip-flops, with the property that adjacent states differ in one bit. Reduces switching activity (and thus power and side-channel leakage) when the FSM tends to walk through adjacent states.
• One-hot: one flip-flop per state, exactly one high at any time. 8 states use 8 flip-flops. Next-state logic is dramatically simpler because each transition only needs to look at the current state's flip-flop, not decode a binary code. FPGAs love one-hot because they have abundant flip-flops and limited LUTs; ASICs often prefer binary.
• Output-based: pick the state code so the outputs fall out of the state bits directly, eliminating output-decode logic.

10.5 State minimization

Some FSMs can have equivalent states (states that produce the same outputs for every input sequence). Merging them gives a smaller FSM. The classical algorithm: build a state-equivalence table by iterating "two states are equivalent if for every input, they go to equivalent states and produce the same output." Iterate to fixed point.

In modern HDL flows you rarely do this by hand. Tools like Synopsys Design Compiler and Vivado have FSM optimization passes that fold equivalent states.

10.6 Worked example: vending-machine controller

A soda machine accepts only 10¢ and 25¢ coins, and dispenses when total deposit reaches 30¢ or more. (Older example, but the controller structure is universal.)

States represent how much money has been deposited:

• $S_0$: nothing yet.
• $S_{10}$: 10¢ deposited.
• $S_{20}$: 20¢ deposited.
• $S_{25}$: 25¢ deposited.

Transitions are labeled by which coin was inserted:

Convert states to bits (4 states need 2 bits in binary, or 4 bits in one-hot). Derive the next-state equations. Implement in flip-flops + combinational logic, or in 15 lines of Verilog:

module vending_fsm (
    input            clk, rst,
    input            coin_10, coin_25,
    output reg       dispense
);
    typedef enum logic [1:0] {S0=2'd0, S10=2'd1, S20=2'd2, S25=2'd3} state_t;
    state_t state, next_state;
 
    always_ff @(posedge clk or posedge rst)
        if (rst) state <= S0;
        else     state <= next_state;
 
    always_comb begin
        next_state = state;
        dispense = 1'b0;
        case (state)
            S0:  if (coin_10) next_state = S10;
                 else if (coin_25) next_state = S25;
            S10: if (coin_10) next_state = S20;
                 else if (coin_25) begin
                    next_state = S0; dispense = 1'b1;
                 end
            S20: if (coin_10 || coin_25) begin
                    next_state = S0; dispense = 1'b1;
                 end
            S25: if (coin_10 || coin_25) begin
                    next_state = S0; dispense = 1'b1;
                 end
        endcase
    end
endmodule

This kind of FSM appears in:

• Vending and ticket machines.
• Traffic-light controllers, which sequence green/yellow/red across multiple lanes.
• USB protocol engines: each command (control transfer, bulk transfer) is an FSM walking through SETUP, DATA, STATUS phases.
• Network protocol stacks: TCP's state machine has 11 states (LISTEN, SYN_SENT, ESTABLISHED, FIN_WAIT_1, …) and is instantly recognizable to any networking engineer.
• Game logic: player walking → jumping → falling → idle is a tiny FSM in every platformer.
• Cryptographic protocol implementations: TLS handshakes, secure-boot sequences, key-exchange phases all run as FSMs in dedicated hardware on smartcards and HSMs.

10.7 ASM charts

An algorithmic state machine (ASM) chart is a flowchart-like diagram for FSMs. It mixes state boxes (rectangles, like flowchart blocks), decision diamonds (for inputs that branch transitions), and conditional output boxes. Sometimes easier to read than a state diagram for control-heavy FSMs (e.g., a CPU's microcode controller).

Modern HDL design rarely starts from ASM charts; the Verilog case statement is itself an ASM chart in textual form. But ASM remains useful for documentation and for designs where the natural description is "do X, then if Y go here else there."

10.8 Hazards, races, and metastability

Even synchronous designs have subtle issues:

• Static hazards. A glitch where the output should be stable but momentarily flips because two paths through different gates do not arrive simultaneously. Solved by adding redundant logic terms (the consensus theorem's redundant terms are exactly hazard-cover terms!) or by registering the output through a flip-flop.
• Dynamic hazards. Multiple glitches during what should be a single transition. Caused by paths of different lengths through the combinational logic. Cleaned up by careful logic restructuring or by registering outputs.
• Race conditions (in async designs). Two flip-flops trying to change "at the same time"; the order is undefined; you get the wrong result. Synchronous design eliminates these by tying everything to a clock.
• Metastability. Already covered in 7.10. Real, physical, unavoidable; manage it with synchronizers.

10.9 Hardware security implications of FSMs

FSMs are security-critical because the state often encodes the security level of the system. The bootloader's state (UNINITIALIZED → MEASURING → VERIFIED → BOOTING) is the trust state of the entire chip. The TLS state is whether you have authenticated. The smartcard's state is whether you have the right PIN. Compromise the FSM and you compromise the security.

Key threats:

• Glitch attacks on FSM transitions. A power or clock glitch at the precise moment the next-state logic is sampled can cause the FSM to land in an unintended state, possibly a "succeeded" state without going through the verification step. Countermeasures: redundant FSM encoding (each state encoded by multiple bits with parity, so glitches show up as "illegal" states), duplicate FSM with comparator, or one-hot encoding with stricter checking.
• Hardware Trojans hidden in FSMs. A malicious FSM with a tiny "trigger" state path that activates only on a specific rare input pattern. Since the trojan may have only a handful of states inside a chip with millions, "covering all states" verification cannot find it without the trigger. Detection requires statistical-anomaly tests on power/timing or formal equivalence checks against a golden netlist.
• Side-channel leakage from state transitions. Different state transitions toggle different sets of flip-flops and combinational gates. Power and EM signatures of FSM steps are observable. AES and other algorithms running in dedicated hardware as FSMs are routinely attacked through these signatures.
• PUFs from flip-flop initial states. Power-up state of a flip-flop is partly random (which gate wins the metastability race depends on tiny manufacturing variations). An array of flip-flops sampled at power-up gives a unique "fingerprint" that can serve as a chip-specific key without storing it in NVRAM. SRAM PUFs are commercial reality (Intrinsic ID, Microsemi).
• Anti-rollback FSMs. The monotonic-counter pattern from Section 8.7 is itself a tiny FSM whose only transitions are increments, with no decrement path. Implemented carefully in fuses, it survives even if the rest of the chip is compromised.