Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 ยท FSMs and Design

Moore and Mealy State Machines

Learn finite state machines in Verilog: states, transitions, Moore and Mealy outputs, state diagrams, and a 101 sequence detector written both ways.

A finite state machine (FSM) is the standard way to build control logic in hardware: a traffic light, a vending machine, a protocol decoder, a memory controller. It remembers which state it is in, looks at its inputs each clock cycle, and decides the next state and its outputs. Almost every non-trivial chip contains dozens of them.

This lesson explains the two classic types, Moore and Mealy, draws the state diagram of a sequence detector, shows both Verilog versions and compares timing. The next lesson, FSM coding styles, shows how to structure the code well.

Verilog cannot be simulated on this site, so the Verilog is read-only. The runnable C programs are labelled stand-ins: they model the same state machines as plain C so you can see the cycle-by-cycle outputs.

The model

An FSM has:

  • a finite set of states (stored in a state register of flip-flops),
  • inputs sampled at the clock edge,
  • a next-state function (combinational logic: current state and inputs give the next state),
  • an output function.

The type depends on what the output function reads:

  • Moore: output depends on the state only. The output changes only when the state changes, right after a clock edge.
  • Mealy: output depends on the state and the current input. The output can react to an input change immediately, in the middle of a clock cycle.
flowchart LR
  I["Inputs"] --> N["Next-state logic"]
  S["State register"] --> N
  N --> S
  S --> OM["Moore output logic"]
  S --> OY["Mealy output logic"]
  I --> OY

The next-state loop is the same for both. Mealy outputs also read the inputs.

The task: detect 101

We want a one-bit output found that goes high when the serial input has just delivered the pattern 1 0 1. Overlapping patterns count: the stream 10101 contains two matches (the final 1 of the first match is the first 1 of the second).

States record how much of the pattern we have seen:

State Meaning
S0 nothing useful yet
S1 seen 1
S2 seen 10
S3 (Moore only) seen 101: output high

Transitions for the Mealy machine (input in x, found after the slash):

stateDiagram-v2
  [*] --> S0
  S0 --> S0: 0 / 0
  S0 --> S1: 1 / 0
  S1 --> S1: 1 / 0
  S1 --> S2: 0 / 0
  S2 --> S0: 0 / 0
  S2 --> S1: 1 / 1

Mealy 101 detector: the output is on the arrow, so the match is reported in the same cycle in which the last 1 arrives.

The Moore machine needs an extra state because its output cannot be attached to an arrow: after the last 1 it moves into S3, and only there is found high.

Mealy in Verilog

VERILOG
module detect101_mealy (
  input  clk, rst_n, x,
  output found
);
  localparam S0 = 2'd0, S1 = 2'd1, S2 = 2'd2;
  reg [1:0] state, next;

  always @(posedge clk or negedge rst_n)
    if (!rst_n) state <= S0;
    else        state <= next;

  always @* begin
    next = state;
    case (state)
      S0: if (x)  next = S1;
      S1: if (!x) next = S2;
      S2: next = x ? S1 : S0;
      default: next = S0;
    endcase
  end

  assign found = (state == S2) && x;     // output reads state AND input
endmodule

Moore in Verilog

VERILOG
module detect101_moore (
  input  clk, rst_n, x,
  output found
);
  localparam S0 = 2'd0, S1 = 2'd1, S2 = 2'd2, S3 = 2'd3;
  reg [1:0] state, next;

  always @(posedge clk or negedge rst_n)
    if (!rst_n) state <= S0;
    else        state <= next;

  always @* begin
    next = state;
    case (state)
      S0: if (x)  next = S1;
      S1: if (!x) next = S2;
      S2: next = x ? S3 : S0;
      S3: next = x ? S1 : S2;          // overlap: 1 0 1 | 0 1
      default: next = S0;
    endcase
  end

  assign found = (state == S3);        // output reads the state only
endmodule

Look at S3 carefully. After 101 the last 1 can start a new match, so from S3 a 1 leads to S1 and a 0 leads to S2 (we have seen 10 again: the previous 1 plus this 0).

Comparing them in C

Both detectors run on the same bit stream in this program. For each clock cycle, the table shows the input, the Mealy output and the Moore output. Moore shows its result one cycle later, because it must first enter S3.

C Stand-in: Mealy and Moore 101 detectors side by side

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Compare the two output columns: every Mealy 1 has a Moore 1 in the next row. A Mealy output depends on the input that arrives in the same cycle, so it is faster by one cycle but also changes if the input glitches during the cycle.

Which one to use?

Moore Mealy
Output depends on state only state and inputs
Output timing registered-like, changes after the clock edge can change any time inputs change
Number of states usually more usually fewer
Glitches on output rare (state-driven) possible if inputs glitch
Typical use outputs that drive other synchronous logic or pins quick reactions, protocol responses

A practical rule: when the output goes off-chip or crosses into another clock domain, prefer Moore or a registered Mealy output. When the output feeds the same synchronous logic and speed matters, Mealy is fine. Many real designs mix both: some outputs from the state, a few from input-dependent decisions.

Table-driven view

Any FSM is a table: for each (state, input) pair, the next state and output. The second program stores the Mealy detector in a lookup table, a form that hardware designers also use (a ROM-based FSM) and that makes it easy to check every combination for completeness.

C Stand-in: the Mealy detector as a lookup table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What distinguishes a Mealy machine from a Moore machine?

    In a Moore machine the output is a function of the state alone. A Mealy output also reads the inputs.
  2. 2. In the 101 detector, why does the Moore version need a fourth state?

    A Moore output is attached to a state, so the match needs its own state S3. The Mealy output sits on the transition S2 --1--> S1.
  3. 3. Compared with the Mealy detector, when does the Moore detector raise found?

    The Moore machine must clock into S3 before the output is high, so it reports one cycle after the Mealy machine.
  4. 4. Which statement about the next-state logic is true?

    The state register is sequential; the next-state logic is a combinational function that feeds the register's input.

Summary

  • An FSM = state register + next-state logic + output logic.
  • Moore outputs read the state only; Mealy outputs read the state and the input.
  • Mealy machines use fewer states and react a cycle sooner; Moore outputs are cleaner and glitch-free.
  • A state diagram and a transition table describe the same machine; check that every (state, input) is covered.

Next: FSM Coding Styles and State Encoding