How Do You Design a Finite State Machine?

Detailed Explanation

The finite state machine is one of the most useful and universally applicable design patterns in embedded firmware and digital hardware. Once you learn to recognise FSM problems, you see them everywhere: parsing a serial data stream, debouncing a button press, managing a network connection lifecycle, controlling a motor sequence, or implementing a menu system. The formal FSM model gives you a structured way to enumerate all states and transitions before writing a single line of code.

Moore vs Mealy Machines

Both are finite state machines; they differ in how outputs are produced.

Moore machine: outputs depend only on the current state. The output changes only when the state changes.

       Input      Input
         ↓          ↓
[State] ──→ [State] ──→ [State]
  ↓            ↓           ↓
Output       Output      Output

Output = f(current state)

Mealy machine: outputs depend on both the current state and the current inputs. The output can change when inputs change, even without a state transition.

          Input / Output
[State] ─────────────────→ [State]

Output = f(current state, current inputs)

Example: A traffic light controller:

• Moore: each state (RED, YELLOW, GREEN) directly determines the light output. Simple and natural.
• Mealy: the output is produced on the transition: RED → GREEN / turn_green_on. Equivalent, but the output logic is attached to the transition rather than the state.

For most embedded firmware, Moore machines are preferred — they are easier to reason about, debug, and test, because the system's output is fully determined by its state at any instant.

The Design Process

Step 1: Enumerate All States

Write down every distinguishable condition the system can be in. Be exhaustive — missing a state is a common source of FSM bugs. Give each state a descriptive name.

Example: a simple UART byte receiver:

• IDLE — waiting for start bit
• START — start bit detected, sampling
• DATA — receiving data bits (with a bit counter)
• STOP — checking stop bit
• ERROR — framing error detected

Step 2: Draw the State Diagram

A state diagram shows:

• States as circles (nodes).
• Transitions as directed arrows between states.
• On each transition arrow: the condition that triggers it (and, for Mealy, the output).
• Inside/below each state node: the outputs (for Moore).

            RX falling edge
                  │
               ┌──▼──┐
          ┌───►│IDLE │◄──────────────────────────────────┐
          │    └──┬──┘                                   │
          │       │ start bit period elapsed             │
          │    ┌──▼──────┐                               │
          │    │  START  │                               │
          │    └──┬──────┘                               │
          │       │ sample point                         │
          │    ┌──▼──────┐  bit_count < 8               │
          │    │  DATA   │──────────────────────────┐   │
          │    └──┬──────┘◄─────────────────────────┘   │
          │       │ bit_count == 8                       │
          │    ┌──▼──────┐                               │
          │    │  STOP   │─── stop bit = 1 ─────────────┘
          │    └──┬──────┘
          │       │ stop bit = 0
          │    ┌──▼──────┐
          └────│  ERROR  │
               └─────────┘

Review the diagram before writing code — it is much easier to identify missing transitions or incorrect behaviour on paper than in code.

Step 3: Choose an Encoding

In embedded C firmware:

Use a C enum for state variables. Binary encoding is implicit and efficient:

typedef enum {
    STATE_IDLE = 0,
    STATE_START,
    STATE_DATA,
    STATE_STOP,
    STATE_ERROR,
    STATE_COUNT   /* useful: number of states */
} uart_state_t;

In FPGA HDL:

The synthesis tool typically chooses the encoding automatically (and often optimises to one-hot for large FSMs). You can override explicitly:

// Binary encoding (2 bits for 4 states):
localparam IDLE  = 2'b00;
localparam START = 2'b01;
localparam DATA  = 2'b10;
localparam STOP  = 2'b11;

// One-hot encoding (4 bits for 4 states):
localparam IDLE  = 4'b0001;
localparam START = 4'b0010;
localparam DATA  = 4'b0100;
localparam STOP  = 4'b1000;

One-hot encoding is recommended for FPGAs with many states because it reduces the combinational logic depth of the next-state decoder — each state transition only checks a single bit. See combinational vs sequential logic for why reducing combinational depth increases maximum clock frequency.

Implementing an FSM in Embedded C

The standard pattern is a switch statement on the current state, executed once per event (polling or ISR-driven):

#include <stdint.h>
#include <stdbool.h>

typedef enum {
    STATE_IDLE,
    STATE_RUNNING,
    STATE_PAUSED,
    STATE_ERROR
} motor_state_t;

typedef enum {
    EVENT_START,
    EVENT_STOP,
    EVENT_PAUSE,
    EVENT_FAULT,
    EVENT_RESUME
} motor_event_t;

static motor_state_t state = STATE_IDLE;

void motor_fsm_process(motor_event_t event) {
    switch (state) {
        case STATE_IDLE:
            if (event == EVENT_START) {
                motor_start_drive();
                state = STATE_RUNNING;
            }
            break;

        case STATE_RUNNING:
            switch (event) {
                case EVENT_STOP:
                    motor_stop_drive();
                    state = STATE_IDLE;
                    break;
                case EVENT_PAUSE:
                    motor_hold_drive();
                    state = STATE_PAUSED;
                    break;
                case EVENT_FAULT:
                    motor_emergency_stop();
                    state = STATE_ERROR;
                    break;
                default:
                    break;
            }
            break;

        case STATE_PAUSED:
            switch (event) {
                case EVENT_RESUME:
                    motor_start_drive();
                    state = STATE_RUNNING;
                    break;
                case EVENT_STOP:
                    motor_stop_drive();
                    state = STATE_IDLE;
                    break;
                case EVENT_FAULT:
                    motor_emergency_stop();
                    state = STATE_ERROR;
                    break;
                default:
                    break;
            }
            break;

        case STATE_ERROR:
            if (event == EVENT_STOP) {
                motor_reset();
                state = STATE_IDLE;
            }
            break;
    }
}

Key design choices:

• The state variable is the single source of truth for where the machine is.
• Each case handles exactly the events relevant to that state; all other events are ignored in the default branch — this prevents undefined behaviour from unexpected events.
• State transitions happen at the end of the event handler, after actions are performed.
• Entry and exit actions (initialising a counter when entering STATE_DATA, for example) are placed at the transition point — either at the end of the outgoing state's case, or at the start of the incoming state's case, depending on which is cleaner for the specific action.

Implementing an FSM in Verilog (FPGA)

The standard two-always-block pattern separates state registers (sequential) from next-state/output logic (combinational):

module traffic_light_fsm (
    input  wire clk,
    input  wire rst_n,
    input  wire timer_expired,
    output reg  red, yellow, green
);
    // State encoding
    localparam RED_STATE    = 2'd0;
    localparam GREEN_STATE  = 2'd1;
    localparam YELLOW_STATE = 2'd2;

    reg [1:0] state, next_state;

    // Sequential block: state register
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            state <= RED_STATE;
        else
            state <= next_state;
    end

    // Combinational block: next-state logic
    always @(*) begin
        next_state = state;  // default: stay in current state
        case (state)
            RED_STATE:    if (timer_expired) next_state = GREEN_STATE;
            GREEN_STATE:  if (timer_expired) next_state = YELLOW_STATE;
            YELLOW_STATE: if (timer_expired) next_state = RED_STATE;
            default:      next_state = RED_STATE;
        endcase
    end

    // Combinational block: Moore output logic
    always @(*) begin
        red    = (state == RED_STATE);
        yellow = (state == YELLOW_STATE);
        green  = (state == GREEN_STATE);
    end
endmodule

The default: next_state = RED_STATE in the case statement is critical — it handles undefined states (e.g. after power-up corruption or a glitch) by forcing the FSM back to a known state. Always include a default case in HDL FSMs.

For larger embedded firmware systems, state machines integrate naturally with RTOS designs — see bare-metal vs RTOS firmware for how event queues and task structures map to FSM event processing.

Zeus Design's firmware team designs protocol decoders, motor controllers, and communication state machines for embedded products from initial architecture through to production implementation.

Design Considerations

• Define entry and exit actions explicitly. Many FSM bugs come from initialisation actions that run when the FSM is already in a state (they should run on entry) or cleanup actions that don't run when a state is exited via an unexpected path. Clearly separate "do once on entering this state" from "do continuously while in this state" from "do once when leaving this state."
• Handle the default transition explicitly. Every state must have a defined behaviour for every event — even if that behaviour is "ignore this event." Missing event handling in one state leads to undefined behaviour when that event unexpectedly arrives.
• Keep action code short. State machine actions (the code run on each transition) should not block. Long computations in a state handler delay event processing. In RTOS designs, post a message to a processing task rather than doing the work inline in the FSM event handler.
• Test every transition, not just the happy path. The most common FSM bugs are not in the expected sequence but in edge cases: what happens if EVENT_STOP arrives while in STATE_IDLE? What if a fault event arrives during an already-faulted state? Enumerate every state × event combination during testing.

Common Mistakes

• Global variables as a substitute for state. A common embedded anti-pattern: using a collection of boolean flags (is_running, has_started, is_paused) instead of a single state variable. With N flags, the system can theoretically be in 2^N combinations, many of which are invalid. An explicit state enum with defined transitions eliminates invalid combinations by construction.
• Missing the default transition in Verilog. An FPGA FSM without a default case in the Verilog case statement will infer latches or leave the FSM stuck in an unrecoverable state if a power glitch or partial initialisation places it in an undefined state. Always include default: next_state = RESET_STATE or equivalent.
• Outputs in the sequential always block. In a Verilog FSM, placing output logic in the sequential (clocked) block adds one clock cycle of output latency and makes the code harder to read. Combinational output logic (in always @(*)) for Moore machines is cleaner and avoids unintended output registration.
• Encoding too many conditions in one state. If a state has more than 5–6 outgoing transitions, it is often a sign that the state is too coarsely defined — it is doing the work of multiple states. Break it into finer-grained states; the diagram and code will both be cleaner.
• Forgetting to reset the state variable on system reset. An FSM in an ISR or RTOS task may persist state across a system error condition. Always initialise the state variable to the idle/reset state explicitly; do not rely on compiler zero-initialisation for global variables in embedded targets (though the startup code does zero BSS — see what does embedded startup code do before main()).