Finite State Machine (FSM) in Digital Design

A finite state machine (FSM) is one of the most fundamental building blocks in digital design. Whenever a circuit needs to remember where it is in a sequence of events and decide what to do next, an FSM is almost always the right abstraction. Traffic-light controllers, UART transmitters, bus arbiters, memory controllers, and protocol handshakes are all built on top of finite state machines. For anyone learning RTL design or preparing for a VLSI interview, a clear and correct mental model of the FSM is non-negotiable. This article explains the concept from first principles, contrasts the Moore and Mealy styles, walks through state tables and state encoding, and shows a clean three-always-block Verilog implementation.

What Is a Finite State Machine?

A finite state machine is a sequential logic model consisting of a finite number of states, transitions between those states, and outputs. At any instant the machine occupies exactly one state. On each active clock edge it evaluates its current state together with its inputs and moves to a next state determined by its transition function. Because the set of states is finite and the behaviour is deterministic, the whole machine can be fully described by a state diagram or a state table.

Formally, a synchronous FSM is defined by five elements:

• S — a finite set of states.
• S₀ — the initial (reset) state.
• I — the set of input values.
• O — the set of output values.
• Two functions: the next-state function (current state + input → next state) and the output function.

The physical implementation maps directly onto this definition. A bank of flip-flops holds the current state (the “state register”). A block of combinational logic computes the next state from the current state and inputs. A second block of combinational logic computes the outputs. How that output block is wired determines whether the machine is a Moore or a Mealy machine.

Moore vs Mealy Machines

The distinction between Moore and Mealy machines is the single most common FSM question in interviews, so it deserves precision.

In a Moore machine, the outputs are a function of the current state only. The inputs influence outputs only indirectly, by steering which state the machine enters. Because outputs depend solely on the registered state, Moore outputs are synchronous and glitch-free, changing only after a clock edge.

In a Mealy machine, the outputs are a function of both the current state and the current inputs. This makes Mealy machines respond to input changes within the same cycle, so they often need fewer states to achieve the same behaviour. The trade-off is that outputs can change asynchronously with the inputs and may contain combinational glitches if the inputs are not clean.

Comparison Table

State Diagram Description

A state diagram represents the FSM graphically. Each state is drawn as a labelled circle (a “bubble”), and each legal transition is an arrow from one bubble to another, annotated with the input condition that triggers it. The reset state is marked with an incoming arrow from nowhere.

In a Moore diagram, the output value is written inside each bubble, because it belongs to the state. For example, a sequence detector that asserts y only in its final accepting state would show y=1 inside that one bubble and y=0 in all others. In a Mealy diagram, outputs are written on the arcs in the form input / output, because the output is produced during the transition itself rather than resident in a state. This placement difference is the quickest visual way to tell the two styles apart.

State Table

A state table (or state-transition table) is the tabular equivalent of the state diagram. It enumerates, for every combination of current state and input, the resulting next state and output. It is the bridge between the abstract diagram and the Boolean equations the synthesis tool will eventually build.

Consider a simple “1011” overlapping sequence detector built as a Moore machine. It has states S0 (idle / no match), S1 (saw “1”), S2 (saw “10”), S3 (saw “101”), and S4 (saw “1011”, accepting). The output y is 1 only in S4.

Note how overlapping matches are handled: from the accepting state S4, a subsequent 1 returns to S1 (that 1 could begin a new pattern), and a 0 goes to S2 (because the trailing “…11” followed by “0” yields “110”, whose longest usable suffix “10” corresponds to S2). Getting these “fall-back” transitions right is exactly what a careful state table forces you to verify.

State Encoding

State encoding is the choice of how each symbolic state name maps to a concrete binary pattern stored in the flip-flops. The encoding does not change the machine’s behaviour, but it strongly affects area, timing, and power. Three encodings dominate practical RTL design.

Binary Encoding

Binary (sequential) encoding assigns consecutive binary numbers to states. For N states it needs only ⌈log₂N⌉ flip-flops, so it is the most register-efficient. The cost is wider, more complex next-state and output logic, since many state bits may change on a single transition.

One-Hot Encoding

One-hot encoding uses one flip-flop per state, with exactly one bit set high at any time. It consumes the most registers (N flip-flops for N states) but produces very simple, fast decode logic because each state is identified by a single bit. One-hot is often the preferred style on FPGAs, which are rich in flip-flops, and it eases timing closure in high-speed designs.

Gray Encoding

Gray encoding orders the codes so that adjacent states differ by only a single bit. When transitions mostly follow that adjacency, only one flip-flop toggles per step, which can reduce switching activity and therefore dynamic power. It is especially valuable for pointers that cross clock domains, such as those in asynchronous FIFOs, where single-bit changes avoid metastable multi-bit glitches.

Encoding Comparison

In modern flows you usually describe states with parameter or enum symbols and let the synthesis tool choose or override the encoding. This keeps the RTL readable while still allowing the tool to optimise. For a deeper look at how combinational blocks like the next-state logic are formed, see our guide on how combinational circuits work in digital logic.

FSM in Verilog / SystemVerilog

The industry-standard way to code an FSM is the three-always-block style. It cleanly separates the three conceptual parts of the machine, which makes the intent obvious to both reviewers and synthesis tools:

1. A sequential block (always_ff) that updates the state register on the clock edge and handles reset.
2. A combinational block (always_comb) that computes the next state from the current state and inputs.
3. A combinational (or sequential) block that derives the outputs. For a Moore machine the output depends on the state only.

The example below implements the “1011” Moore sequence detector described in the state table above.

module seq_detect_1011 (
    input  logic clk,
    input  logic rst_n,     // active-low synchronous reset
    input  logic din,       // serial input bit
    output logic y          // asserted when 1011 detected
);

    // State encoding (tool may re-encode)
    typedef enum logic [2:0] {
        S0 = 3'd0,
        S1 = 3'd1,
        S2 = 3'd2,
        S3 = 3'd3,
        S4 = 3'd4
    } state_t;

    state_t current_state, next_state;

    // 1. Sequential block: state register
    always_ff @(posedge clk) begin
        if (!rst_n)
            current_state <= S0;
        else
            current_state <= next_state;
    end

    // 2. Combinational block: next-state logic
    always_comb begin
        next_state = current_state;   // default: hold
        case (current_state)
            S0: next_state = din ? S1 : S0;
            S1: next_state = din ? S1 : S2;
            S2: next_state = din ? S3 : S0;
            S3: next_state = din ? S4 : S2;
            S4: next_state = din ? S1 : S2;
            default: next_state = S0;
        endcase
    end

    // 3. Combinational block: Moore output (state only)
    always_comb begin
        y = (current_state == S4);
    end

endmodule

Several coding habits in this template are worth internalising:

• The next-state block assigns a default value first (next_state = current_state), which prevents accidental latches by guaranteeing every path is covered.
• Reset forces the machine into a known state S0; without a defined reset state the FSM could power up into an undefined or unreachable encoding.
• The output block reads only the state, confirming this is a Moore machine. To make it Mealy, you would include din in the output expression, for example asserting y on the arc from S3 when din == 1 rather than in S4.
• Using an enum (SystemVerilog) or parameter (Verilog-2001) keeps the state names symbolic and lets the synthesis tool apply binary, one-hot, or gray encoding as directed. If you are still deciding between the two languages for this style of coding, our comparison of Verilog vs SystemVerilog is a good companion read.

Relevance to RTL Design Interviews

FSMs appear in virtually every RTL interview because they test several skills at once: understanding of sequential logic, the discipline of clean coding, and the ability to reason about timing. Commonly asked questions include:

• Explain Moore vs Mealy and state when you would pick each. The expected nuance is the latency-versus-glitch trade-off, not just the definitions.
• Draw the state diagram and write RTL for a sequence detector (overlapping and non-overlapping variants are both popular).
• Why one-hot on FPGA? — tying encoding choice to the target technology shows practical awareness.
• How do you avoid inferred latches in the next-state logic? The default-assignment and full-case answer is what interviewers listen for.
• How do you reset safely and handle illegal states? A robust FSM defines a recovery path (often via the default case) so a glitch cannot strand the machine forever.

Mastering these questions requires both the theory above and hands-on RTL practice with real waveforms. Understanding the three-block template until you can reproduce it from memory is one of the highest-return exercises for anyone targeting a front-end design role.

If you want structured, mentor-led practice building finite state machines and the broader sequential-design skill set that front-end roles demand, explore the ChipXpert Advanced RTL Design course, where FSM design, coding style, and interview preparation are covered with lab-based projects.

Frequently Asked Questions

What is a finite state machine in digital design?

A finite state machine is a sequential circuit model with a finite number of states, where the machine occupies one state at a time and moves between states on clock edges according to its inputs. It is implemented with a state register (flip-flops) plus combinational next-state and output logic, and it is used to control sequenced behaviour such as protocols, controllers, and detectors.

What is the difference between Mealy vs Moore machines?

In a Moore machine the output depends on the current state only, so outputs are synchronous and glitch-free but the machine may use more states. In a Mealy machine the output depends on both the current state and the current inputs, so it reacts within the same cycle and typically needs fewer states, at the cost of outputs that can change asynchronously and may glitch.

Which FSM state encoding should I use?

Use binary encoding when you need the fewest flip-flops, one-hot encoding when you want simple, fast decode logic or are targeting an FPGA, and gray encoding when you want to minimise switching power or are passing pointers across clock domains. In most flows you write symbolic state names and let the synthesis tool apply the encoding you specify.

Why is the three-always-block style preferred for FSM coding?

The three-always-block style separates the state register, the next-state logic, and the output logic into distinct blocks. This makes the design intent explicit, maps cleanly to the hardware structure of an FSM, reduces the chance of inferred latches through default assignments, and is easy for reviewers and synthesis tools to interpret correctly.

How do you prevent latches in FSM next-state logic?

Assign a default value to the next-state variable at the top of the combinational block (for example, hold the current state), use a case statement that covers every state, and include a default branch. This guarantees that the next-state signal is assigned on every possible path, so no storage element is inferred for the combinational logic.

💻 Want the code? See the Verilog implementation with a verified testbench: Fsm Verilog code →