Finite State Machines: Moore vs Mealy with a 101 Sequence Detector

A finite state machine (FSM) is a sequential circuit that moves between a fixed number of states on each clock edge, based on its inputs. Counters are simple FSMs. Traffic light controllers, UART receivers, vending machines, bus protocol handlers and the control unit of a CPU are more interesting ones. This tutorial explains the two classic FSM models, Moore and Mealy, and designs the same circuit, an overlapping 101 sequence detector, both ways. You will go from state diagram to state table to flip-flop equations and finally to synthesisable Verilog.

Structure of an FSM

Every synchronous FSM has three parts: a state register made of flip-flops, next-state logic that computes the next state from the present state and the inputs, and output logic. The difference between the two models lies only in the output logic.

Feature	Moore machine	Mealy machine
Output depends on	Present state only	Present state and present inputs
Output written	Inside the state circle	On the transition arrow, as input/output
Number of states	Usually more	Usually fewer
Output timing	Changes only after a clock edge	Can change as soon as an input changes
Glitch risk on outputs	Low, outputs follow registered state	Higher, input glitches pass through

Moore Design: 101 Detector with Overlap

The input x arrives one bit per clock. Output Z must be 1 whenever the last three bits received were 1, 0, 1. Overlap is allowed, so the input 10101 produces two detections. In a Moore machine the output belongs to a state, so we need a state that means the full sequence has been seen.

States
S0 : nothing useful received        Z = 0
S1 : last bit was 1                  Z = 0
S2 : last bits were 1 0              Z = 0
S3 : last bits were 1 0 1 (detect)   Z = 1

Transitions
S0 --0--> S0    S0 --1--> S1
S1 --0--> S2    S1 --1--> S1
S2 --0--> S0    S2 --1--> S3
S3 --0--> S2    S3 --1--> S1

The transition from S3 on input 0 goes to S2, not S0, because the final 1 of the detected sequence can start a new one. That is what overlap means. With binary state assignment S0 = 00, S1 = 01, S2 = 10 and S3 = 11, the state table becomes:

Q1 Q0 | x=0 next | x=1 next | Z
------+----------+----------+---
 0  0 |   0 0    |   0 1    | 0
 0  1 |   1 0    |   0 1    | 0
 1  0 |   0 0    |   1 1    | 0
 1  1 |   1 0    |   0 1    | 1

With D flip-flops, D equals the next state. From K-maps:
D1 = Q0.x' + Q1.Q0'.x
D0 = x
Z  = Q1.Q0

Check one transition: in S2 (10) with x = 1, D1 = 0 + 1 = 1 and D0 = 1, giving S3 (11), and Z becomes 1 during the following clock period. The circuit needs two flip-flops, two AND terms for D1 and one AND gate for Z.

Mealy Design: Same Detector, One Fewer State

In a Mealy machine the output can be produced on the transition that completes the sequence, so the separate detect state disappears.

S0 --0/0--> S0    S0 --1/0--> S1
S1 --0/0--> S2    S1 --1/0--> S1
S2 --0/0--> S0    S2 --1/1--> S1

Assignment S0 = 00, S1 = 01, S2 = 10, 11 unused (don't care)
D1 = Q0.x'
D0 = x
Z  = Q1.x

The Mealy version asserts Z in the same clock cycle that the final 1 is present on the input, one cycle earlier than the Moore version. The price is that Z depends directly on x, so any glitch on x between clock edges also appears on Z. If Z feeds another synchronous block that samples it at the clock edge, this is harmless. If Z drives something asynchronous, such as an interrupt line or an LED latch, register it or prefer the Moore form.

Moore Detector in Verilog

In hardware description languages, FSMs are written with one sequential block for the state register and combinational blocks for next state and output. Synthesis tools recognise this pattern and can choose the state encoding themselves.

Overlapping 101 sequence detector, Moore style, synchronous active-high reset

module seq101_moore (
    input  wire clk,
    input  wire rst,   // synchronous, active high
    input  wire x,     // serial input bit
    output wire z      // 1 when last three bits were 1,0,1
);
    // State encoding
    localparam S0 = 2'b00,  // idle
               S1 = 2'b01,  // got 1
               S2 = 2'b10,  // got 10
               S3 = 2'b11;  // got 101

    reg [1:0] state, next;

    // State register
    always @(posedge clk) begin
        if (rst) state <= S0;
        else     state <= next;
    end

    // Next-state logic
    always @(*) begin
        case (state)
            S0: next = x ? S1 : S0;
            S1: next = x ? S1 : S2;
            S2: next = x ? S3 : S0;
            S3: next = x ? S1 : S2;   // overlap: last 1 reused
            default: next = S0;
        endcase
    end

    // Moore output depends on state only
    assign z = (state == S3);
endmodule

Tracing a test input

Before simulating, trace a short input by hand. Starting in S0 and applying x = 1, 0, 1, 0, 1, the Moore machine moves S0 to S1, S2, S3, S2 and S3. Z is 1 in the clock periods after the third and fifth bits, which confirms two overlapping detections. The Mealy machine visits S1, S2, S1, S2, S1 and raises Z while the third and fifth bits are present on the input, one period earlier. Writing this trace as a table of clock number, input, state and output is also exactly what an examiner expects to see.

Choosing a state encoding

Binary encoding uses the minimum number of flip-flops, log2 of the number of states rounded up. Gray encoding assigns codes so that common transitions change only one bit, which can reduce next-state logic and switching power. One-hot encoding uses one flip-flop per state, so four states need four flip-flops, but each next-state equation becomes a simple OR of incoming transitions. Small ASIC controllers often use binary or Gray codes, while FPGA tools frequently pick one-hot automatically.

Converting this to Mealy form is a one-line change in concept: remove S3, send S2 on x = 1 to S1, and assign z = (state == S2) && x.

Design Tips and Common Mistakes

Decide on overlap or non-overlap first; it changes the return transitions.
Always include a reset state and a default branch so the machine recovers from illegal codes.
Use one-hot encoding (one flip-flop per state) on FPGAs, where flip-flops are plentiful and next-state logic becomes simpler.
Trace a test input such as 0101101 by hand and count detections before building hardware.
In Verilog, use non-blocking assignment in the clocked block and blocking assignment in combinational blocks.

Summary

Moore outputs depend only on state, so they are clean and registered but appear one cycle later and need more states. Mealy outputs depend on state and input, respond immediately and need fewer states, but can pass glitches. Both are designed by the same steps: state diagram, state table, state assignment, flip-flop equations from K-maps and an output equation. For the 101 detector, the Moore machine needs four states and the Mealy machine three, and both fit in two D flip-flops.