State Machines: Moore and Mealy

Read a state diagram and its table, build a machine from three blocks, and say when a Moore or Mealy output changes.

You Will Be Able To

  • Name the state, input, next state and output of a machine, and read its diagram and table.
  • Draw the three blocks: next-state logic, state register and output logic.
  • Explain why a Mealy machine reacts one cycle sooner and can need one state fewer.
  • Spot a missing or a doubled arc, and say why a Mealy output can pass a glitch.
Lesson
G7.1
Time
30 min
Runs on
Your browser
Check
5 questions

A link controller had to flag the last bit of a 1011 header in the same cycle the bit arrived. The designer drew a Moore machine. Every flag came one cycle late, and the block after it missed one word per header. Here are both kinds of machine on one stream.

The Same Detector, Two Kinds of OutputOne column per clock cycle, from the lab run. The bit arrives on x during the cycle; the state changes at the edge that ends it.
01234567clkxz_mealyz_moore1011 completeoverlapping match
Scroll horizontally ↔
  1. Cycle 3

    The fourth bit, a 1, completes 1011 in cycle 3. z_mealy is 1 at once: it looks at x.

  2. Cycle 4

    z_moore rises one cycle later. Its machine had to enter the match state first.

  3. Cycle 6

    The last 1 of the first match starts the second. Both machines find two matches.

Measured: the lab below, on Icarus Verilog 12.

State, Input, Next State, Output

A state machine remembers where it is. That memory is its state. At each clock edge it reads its input and moves to a next state. Its output depends on the state, and for some machines on the input too.

The state diagram draws each state as a circle and each move as an arc labelled with the input that takes it. The state table lists the same arcs as rows. Reset names the state the machine starts in.

A Junction Light That Waits for Its Timer
A Junction Light That Waits for Its Timer01010101R100RedRA110Red and amberG001GreenA010Amber
  1. Red · R100
    • ↓0 → R
    • ↓1 → RA
  2. Red and amber · RA110
    • ↓0 → RA
    • ↓1 → G
  3. Green · G001
    • ↓0 → G
    • ↓1 → A
  4. Amber · A010
    • ↓0 → A
    • ↓1 → R
StateInputNextOutput in state
R0R100
R1RA100
RA0RA110
RA1G110
G0G001
G1A001
A0A010
A1R010

Current state: R · Output: 100

Sampled input, state and output waveformStepState0R1R2R3RA4RA5RA6G7A8A9A10Rt—0010011001red11111100001amber00011101110green00000010000
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step012345678910
Input—0010011001
StateRRRRARARAGAAAR
Output100100100110110110001010010010100

  1. Step 0. Reset puts the machine in R. A Moore machine shows its output in the state: red only, 100.
  2. Step 2. t was 0 twice, so both arcs taken were self-loops. The light stays red.
  3. Step 3. t = 1: the arc R to RA is taken at the clock edge. The output becomes 110.
  4. Step 6. Each 1 on t moves one state on. RA, then G after two more cycles.
  5. Step 10. Ten inputs, four of them 1, take the light once around and back to red.

Step it. Every state has one arc for t = 0 and one for t = 1. Edit the stream and step again.

Three Blocks

Every synchronous state machine is three blocks. The next-state logic computes the next state from the state and the input. The state register, a row of flip-flops, stores it at the edge. The output logic computes the output.

Next-State Logic, State Register, Output LogicArrows show signals. The state feeds back into the next-state logic. The arrow from the input to the output logic exists only in a Mealy machine.
  • I/O
  • Control / FSM
  • Storage
  • Control
Next-state logic, state register, output logicArrows show signals. The state feeds back into the next-state logic. The arrow from the input to the output logic exists only in a Mealy machine. io Input x from outside control Next-state logic combinational storage State register flip-flops, one clock control Output logic combinational io Output z to the next block next statestatestateMealy only
  1. io Input xfrom outside
    • Next-state logic
    • Mealy only → Output logic
  2. control Next-state logiccombinational
    • next state → State register
  3. storage State registerflip-flops, one clock
    • state → Next-state logic
    • state → Output logic
  4. control Output logiccombinational
    • Output z
  5. io Output zto the next block
  1. Next state

    Between edges, the next-state logic settles to the state the machine will take.

  2. The edge

    At the rising edge the register stores the next state. Nothing else in the machine has memory.

  3. Moore output

    A Moore output is computed from the state alone, so it changes only just after an edge.

  4. Mealy output

    A Mealy output also reads the input. It can change whenever x changes.

Read the diagram as text
  • Input x: from outside
  • Next-state logic: combinational
  • State register: flip-flops, one clock
  • Output logic: combinational
  • Output z: to the next block
  • Input x → Next-state logic
  • Next-state logic → State register: next state
  • State register → Next-state logic: state
  • State register → Output logic: state
  • Input x → Output logic: Mealy only
  • Output logic → Output z

In the lab, each machine has one always_ff (the register), one always_comb case (next-state logic) and one assign (output logic).

Moore Against Mealy on One Stream

In a Moore machine the output is a function of the state only. In a Mealy machine it is a function of the state and the input. Same job, two shapes.

The 1011 Detector, Moore and Mealy
The 1011 Detector, Moore and Mealy0101010101S00nothingS10saw 1S100saw 10S1010saw 101S10111match
  1. nothing · S00
    • ↓0 → S0
    • ↓1 → S1
  2. saw 1 · S10
    • ↓0 → S10
    • ↓1 → S1
  3. saw 10 · S100
    • ↓0 → S0
    • ↓1 → S101
  4. saw 101 · S1010
    • ↓0 → S10
    • ↓1 → S1011
  5. match · S10111
    • ↓0 → S10
    • ↓1 → S1
StateInputNextOutput in state
S00S00
S01S10
S10S100
S11S10
S100S00
S101S1010
S1010S100
S1011S10110
S10110S101
S10111S11

Current state: S1011 · Output: 1

Sampled input, state and output waveformStepState0S01S12S103S1014S10115S106S1017S1011x—1011011z00001001
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step01234567
Input—1011011
StateS0S1S10S101S1011S10S101S1011
Output00001001

  1. Step 4. The fourth bit completes 1011. The Moore machine has just entered S1011, so z = 1 shows in the next cycle.
  2. Step 7. The last 1 of the first match starts the second one. Two matches in 1011011.

The Moore machine needs a state that means "a match". The Mealy machine puts the match on the arc A101 to A1. Switch machines on the same stream.

MooreMealy
Output depends onthe statethe state and the input
Drawn onthe state circlethe arc
States for 101154
Match flag for 1011011cycles 4 and 7cycles 3 and 6
Output changesjust after an edgewhenever x changes

Measured: the lab below. Both machines find two matches; the Mealy flag comes one cycle sooner.

The Moore machine needs a state that means "a match was just seen". The Mealy machine puts that fact on an arc instead. So it needs one state fewer.

A Mealy Output Follows the Input

A Mealy output is combinational from x. If x glitches between edges, the output can glitch with it. A Moore output cannot: it waits for an edge.

That is why many teams register every output that leaves a block. A Mealy output that feeds logic sampled at the same clock edge is fine. One that feeds a different clock, a latch or a pin is not.

One Arc for Every Input Value

Every state needs exactly one next state for each input value. Two arcs for one value leave the next state undecided. A missing arc leaves it unsaid, and in code it can become a latch.

Statex = 0x = 1Verdict
PPQcomplete
QR—missing arc for x = 1
RPQ and Rtwo arcs for x = 1

A hand-drawn machine with both faults. The fsm widget refuses to draw it.

Asked in interviews
  1. What is the difference between a Moore and a Mealy machine?

    A Moore output depends on the state only, so it changes just after a clock edge. A Mealy output depends on the state and the inputs, so it reacts in the same cycle and often needs fewer states. It can also pass input glitches.

  2. Draw a state machine as blocks.

    Next-state logic, combinational, from the state and the inputs. A state register of flip-flops. Output logic from the state (Moore) or from the state and the inputs (Mealy).

  3. Your Mealy machine needs 4 states. How many does the Moore version need?

    Usually one or more extra. Each different output value on arcs into one state needs its own Moore state. For a 1011 detector it is 5 against 4.

Try It

Each line is printed mid-cycle, before the edge. It shows the bit on x, both states and both outputs.

Cycle 3 completes 1011. z_mealy is 1 in that cycle; z_moore is 1 in cycle 4, in the match state.

Change stream to "11011000" and predict both flags before you run it. Then delete the S1011: arm and run Lint.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: cycle 0 x=1 moore=S0 mealy=A0 z_moore=0 z_mealy=0 cycle 1 x=0 moore=S1 mealy=A1 z_moore=0 z_mealy=0 cycle 2 x=1 moore=S10 mealy=A10 z_moore=0 z_mealy=0 cycle 3 x=1 moore=S101 mealy=A101 z_moore=0 z_mealy=1 cycle 4 x=0 moore=S1011 mealy=A1 z_moore=1 z_mealy=0 cycle 5 x=1 moore=S10 mealy=A10 z_moore=0 z_mealy=0 cycle 6 x=1 moore=S101 mealy=A101 z_moore=0 z_mealy=1 cycle 7 x=0 moore=S1011 mealy=A1 z_moore=1 z_mealy=0

Original design · 30 cells · 9 flip-flops · 0 latches · 3 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: the bench (read-only). It feeds 1011011 and then a 0, one bit per cycle.
module tb;
  logic clk = 0, rst = 1, x = 0;
  logic z_moore, z_mealy;
  det1011 dut (.clk(clk), .rst(rst), .x(x), .z_moore(z_moore), .z_mealy(z_mealy));
  string stream = "10110110";
  initial begin
    #1 clk = 1; #1 clk = 0; rst = 0;                // one reset edge: both machines start at the beginning
    for (int i = 0; i < stream.len(); i++) begin
      x = (stream[i] == "1");
      #1 $display("cycle %0d x=%b moore=%-5s mealy=%-4s z_moore=%b z_mealy=%b", i, x, dut.m.name(), dut.a.name(), z_moore, z_mealy);
      #1 clk = 1; #1 clk = 0;                       // the rising edge at the end of the cycle
    end
  end
endmodule

Check Yourself

ConceptA Moore machine and a Mealy machine do the same job. Which statement is true?
Read the waveformA Mealy detector for 01 raises z on the arc that completes 01. In which cycle is z first 1?
A 01 detector, Mealy
01234clkx
Scroll horizontally ↔

Each column is one clock cycle. The bit on x is held for the whole cycle.

ConceptWhere can a glitch on an input reach the output?
Predict the outputThe lab's Moore detector runs on 0101101 after reset. The program prints z_moore after each edge. Predict the exact line.
module tb;
  typedef enum logic [2:0] {S0, S1, S10, S101, S1011} moore_t;
  moore_t m = S0;
  string x = "0101101", z = "";
  initial begin
    for (int i = 0; i < x.len(); i++) begin
      case (m)
        S0:      if (x[i] == "1") m = S1;    else m = S0;
        S1:      if (x[i] == "1") m = S1;    else m = S10;
        S10:     if (x[i] == "1") m = S101;  else m = S0;
        S101:    if (x[i] == "1") m = S1011; else m = S10;
        default: if (x[i] == "1") m = S1;    else m = S10;
      endcase
      z = {z, (m == S1011) ? "1" : "0"};
    end
    $display("%s", z);
  end
endmodule
ConceptA designer must turn a 6-state Moore machine into a Mealy machine. How many states will the Mealy machine have?

Common Mistakes

Wrong Leave out an arc because "that input never comes in this state".

The register takes some next state anyway. With no arc, the code has no answer, and a case statement with no default can build a latch.

Fix Give every state a next state for every input value, self-loops included, and add a default arm.

Wrong Draw two arcs out of one state for the same input value.

A state machine must know its next state. Two arcs for x = 1 do not say which one wins.

Fix Check each state: one arc per input value, exactly. The widget refuses a machine that breaks this.

Wrong Expect a Moore output in the same cycle as the input that causes it.

A Moore output belongs to a state, and the state changes only at the next edge. In the lab z_moore came one cycle after z_mealy.

Fix Use a Mealy output when the answer is needed in the same cycle, or accept the one-cycle delay.

Wrong Send a Mealy output straight to another block that acts on its level at any time.

It follows the input between edges. A one-unit glitch on x made one pulse on z_mealy and none on z_moore.

Fix Register a Mealy output before it leaves the block, or make sure the receiver samples it only at the clock edge.

Remember

  • A state machine is next-state logic, a state register and output logic. Only the register remembers.
  • Every state has exactly one next state for every input value.
  • A Moore output depends on the state, a Mealy output on the state and the input.
  • A Mealy output reacts one cycle sooner and can need fewer states, but it follows input glitches.

Practice

Report a problem with this page