← Back to blogState machines

Mealy vs Moore State Machines: With Examples

Compare Mealy and Moore finite state machines with a worked 1011 detector, timing diagrams, output hazards, state encoding, and verification guidance.

DennyDenny
11 min read
Chalkboard feature illustration for “Mealy vs Moore State Machines: With Examples”

TL;DR: A Moore machine’s output is a function of current state; a Mealy machine’s output is a function of current state and current input. Mealy modeling can respond within a cycle and may need fewer states, but it adds a combinational path from input to output. Moore modeling isolates the output from direct input changes, but a decoded Moore output is not automatically glitch-free. Choose from the interface’s cycle-level behavior, then verify the synthesized implementation rather than relying on slogans about speed, state count, or safety.

Mealy and Moore machines are two ways to describe a finite-state machine’s output function. The distinction is small in notation and important in hardware: it determines whether an input can affect an output without first changing the stored state.

Neither style is universally better. A protocol event may be natural as a Mealy output, while an actuator mode may be clearer as a Moore state. Production controllers often contain both kinds of logic.

This guide builds the definitions precisely, works through an overlapping 1011 detector, and shows where common rules of thumb fail.

The Three Parts of a Synchronous FSM

A typical synchronous finite-state machine contains:

  1. a state register, which stores the current state
  2. next-state logic, which computes the state to load on the next active edge
  3. output logic, which computes externally visible controls or status

Let:

  • q[n]q[n] be the state during cycle nn
  • x[n]x[n] be the input considered during that cycle
  • δ\delta be the next-state function
  • λ\lambda be the output function

Both styles use:

q[n+1]=δ(q[n],x[n])q[n+1] = \delta(q[n], x[n])

The difference is the output function.

Moore machine

y[n]=λ(q[n])y[n] = \lambda(q[n])

The output depends only on the stored state.

Mealy machine

y[n]=λ(q[n],x[n])y[n] = \lambda(q[n], x[n])

The current input can affect the output while the state remains unchanged.

That definition—not where labels happen to be drawn—is the reliable test. On a conventional state diagram, Moore outputs appear inside state nodes and Mealy outputs appear on transitions, often as input / output.

The state register is built from flip-flops; the D flip-flop guide develops that storage element, and counters and state machines is a useful introduction to next-state logic.

What “Responds One Cycle Earlier” Really Means

A common summary says “Mealy is immediate; Moore is one cycle late.” That can be useful, but only after the sampling convention is clear.

Assume the state is q[n]q[n] just after a clock edge:

edge n                                      edge n+1
  │<--------------- cycle n ------------------>│
  │ state = q[n]                               │ state = q[n+1]
  │ input x[n] may affect Mealy output         │

A combinational Mealy output can change after x[n]x[n] changes and its logic propagates. A Moore output cannot respond to that input until the input causes a state transition. After the next edge changes the state, the Moore decode changes.

In a real interface, however:

  • inputs may themselves be registered
  • outputs may be registered before leaving the block
  • a receiver may sample only at clock edges
  • a handshake may define acceptance as an edge event

Registering a Mealy result can make its externally visible latency match a Moore implementation. Conversely, a Moore state reached at an edge can drive a useful output immediately after that edge. Specify behavior as a cycle-by-cycle contract before declaring either version “faster.”

Worked Example: Overlapping 1011 Detector

The detector consumes one input bit per clock and asserts found whenever the most recent bits complete 1011. Overlap is allowed, so the trailing 1 of one match can begin another.

Each state records the longest suffix seen so far that is also a prefix of 1011:

  • AA: no useful suffix
  • BB: 1
  • CC: 10
  • DD: 101

Mealy version

The Mealy machine asserts found on the transition from DD when the current input is 1:

Current stateMeaningInputNext statefound
AAnone0AA0
AAnone1BB0
BB10CC0
BB11BB0
CC100AA0
CC101DD0
DD1010CC0
DD1011BB1

The return to BB after a match preserves overlap: the final 1 is also the first bit of a possible next match.

This machine needs four abstract states. With binary encoding, two state bits are sufficient.

Moore version

A Moore output cannot depend on the input that completes the pattern, so add a fifth state:

  • EE: a complete 1011 has just been recognized; found = 1
Current stateMeaningfoundInput 0 →Input 1 →
AAnone0AABB
BB10CCBB
CC100AADD
DD1010CCEE
EEmatched 10111CCBB

From EE, input 0 leaves the useful suffix 10, and input 1 leaves the useful suffix 1. That is what preserves overlapping detection.

The Moore machine uses five abstract states, so a compact binary encoding needs at least three state bits. In this example, the Mealy form is smaller at the state-diagram level. That is common for transition-associated events, but it is not a theorem that every Mealy machine uses fewer hardware resources.

Compare the waveforms

For input bits sampled as 1 0 1 1:

CycleSampled bitMealy state before sampleMealy foundMoore state after sampleMoore found
11AA0BB0
20BB0CC0
31CC0DD0
41DD1EE1

This table aligns the Mealy transition result with the Moore state entered at the sampling edge. Depending on whether a waveform labels values before or after that edge—and whether found is registered—the two pulses may appear offset. State the convention in a testbench so a correct design is not mistaken for a one-cycle bug.

A Sensor-Controlled Transition Is Not Automatically Mealy

Consider a traffic-light controller with phase states such as:

  • north/south green
  • north/south yellow
  • all red
  • east/west green
  • east/west yellow
  • all red

A vehicle sensor may influence when the controller leaves a green state. That alone does not make the controller Mealy: next-state logic depends on inputs in both styles.

If the lamp outputs are fixed by the phase state, the output function is Moore:

lamps=λ(phase)\text{lamps} = \lambda(\text{phase})

If a current sensor input directly changes a lamp or an acknowledgment output without a state change, that particular output is Mealy:

ack=waiting_state∧request\text{ack} = \text{waiting\_state} \land \text{request}

For a safety-relevant controller, the real requirements extend far beyond choosing an FSM label: fail-safe outputs, interlocks, timing supervision, reset behavior, electrical drivers, diagnostics, and applicable standards all matter. “Use Moore” is not a safety case.

Output Stability: The Important Nuance

Mealy outputs have an explicit combinational path from input to output. If the input changes or glitches, the output can respond after the path delay. That matters when the output drives:

  • an asynchronous control
  • a clock or reset pin
  • a bus ownership signal
  • logic that treats a short pulse as an event

But “Moore outputs are glitch-free” is too broad.

A Moore output can be implemented as combinational decode of several state bits. During a binary state transition, those flip-flops do not change at exactly the same physical instant. The decoder can briefly see an intermediate code and glitch. One-hot state transitions can also have a short gap or overlap at the electrical level.

Ways to obtain a clean interface include:

  • register the output
  • choose an encoding and decode appropriate to the required hazard behavior
  • avoid using combinational FSM outputs as clocks or asynchronous controls
  • ensure any downstream synchronous receiver samples only after setup and hold are met
  • verify the synthesized and routed design, not only the abstract state diagram

A combinational glitch that settles before the receiving clock edge may be harmless to a synchronous receiver. The same glitch can be dangerous if it reaches an edge-sensitive or asynchronous destination. Context determines severity.

The static and dynamic hazards guide explains why unequal path delays can create these pulses.

Asynchronous Inputs Are a Separate Problem

Neither Mealy nor Moore modeling makes an asynchronous input safe. An asynchronous signal can violate setup or hold at the state register or at an input register and cause metastability.

Choose the crossing circuit based on the signal:

  • a stable single-bit level can often use a multistage synchronizer
  • a mechanical switch also needs debouncing
  • a short pulse may need stretching, toggle encoding, or a handshake
  • a multibit value needs a coherency-preserving handshake or FIFO

Feeding an asynchronous input only into Moore next-state logic does not remove the crossing. Feeding it directly into a Mealy output may additionally expose output logic to within-cycle changes.

The setup, hold, and metastability guide covers the analog failure mechanism and the limits of synchronizers.

State Encoding Is an Implementation Choice

The state diagram uses symbolic states. Synthesis maps those symbols to bits.

Compact or binary encoding

Compact encoding uses approximately:

⌈log⁡2N⌉\lceil \log_2 N \rceil

state bits for NN states.

It minimizes the state-register bit count, but next-state and output decoding may require more combinational logic. That does not automatically make it smaller or slower after technology mapping.

One-hot encoding

One-hot encoding uses one state bit per state, with exactly one bit asserted in every legal state. It can simplify decode and transition logic, especially on an FPGA with abundant registers, but it uses more state bits and still requires analysis of illegal encodings and transition behavior.

Gray or custom encoding

Gray-style assignments make selected adjacent states differ by one bit. They can reduce simultaneous state-bit switching for those transitions. An arbitrary state graph may not permit every transition to have Hamming distance one with a simple assignment, and a custom encoding should be justified by measured timing, power, or hazard requirements.

Let results decide

Modern synthesis tools can select an encoding automatically or accept an explicit directive. The best result depends on:

  • target architecture
  • number and connectivity of states
  • output decode
  • fanout
  • timing constraints
  • area and power goals
  • safe-state requirements

Do not force one-hot because of a fixed state-count rule. Compare post-synthesis utilization and post-implementation timing. AMD’s current FSM_ENCODING documentation explicitly describes automatic, one-hot, sequential, Johnson, and Gray choices rather than declaring one universal winner.

Illegal States and Recovery

If an encoding has unused bit patterns, decide what the circuit should do if one appears. Recovery is not as simple as adding a source-level default branch and assuming it will survive every optimization.

A professional review asks:

  • Is recovery required by the system’s fault model?
  • Can the synthesis tool prove the state unreachable and optimize recovery logic?
  • Does a vendor safe-state option change encoding, area, or timing?
  • Should outputs go immediately safe or recover on the next clock?
  • How is the recovery mechanism verified and fault-injected?

Vendor tools provide explicit options for this purpose. For example, AMD documents an FSM_SAFE_STATE property and notes that added recovery logic can cost area and performance. Follow the target tool’s current behavior rather than assuming all HDL defaults produce identical hardware.

A Reliable FSM Design Workflow

1. Write the cycle contract

Define when inputs are sampled, when outputs may change, and what downstream logic observes. For a handshake, specify what constitutes transfer. For a detector, specify whether the result is combinational, registered, and overlapping.

2. Define state meaning

Each state should capture the minimum history needed to decide future behavior. Give it a semantic name such as WAIT_HEADER, READ_PAYLOAD, or REPORT_ERROR, not only S0, S1, and S2.

3. Build a complete transition table

Cover every state and relevant input combination. For wide inputs, group conditions carefully and state priority explicitly.

4. Choose output timing deliberately

Ask whether each output represents:

  • a persistent mode
  • a one-cycle event
  • a ready/valid condition
  • an asynchronous control

Different outputs in one controller may use different styles.

5. Define reset and exceptional behavior

Specify the reset state, output values during reset, timeout behavior, illegal input combinations, and error recovery.

6. Handle clock-domain crossings before the FSM

Synchronize or transfer inputs with the correct CDC protocol. Do not hide an asynchronous crossing inside state logic.

7. Code for complete combinational assignment

In HDL, give next-state and combinational outputs defaults before the state cases, then override them explicitly. This avoids unintended latches and makes priorities reviewable.

8. Verify the abstract machine and the implementation

Use simulation or formal properties to verify state behavior, then inspect synthesis reports, timing, encoding, reset implementation, and CDC analysis.

Verification Plan for the 1011 Detector

A useful testbench covers more than one happy-path word:

TestInputExpected matches
no match0000000
one match10111
leading noise0010111
overlapping opportunity10110112
repeated ones1110111
reset mid-prefix101, reset, 10 after reset

Useful assertions include:

  • found is asserted only when the accepted bit completes 1011
  • every completed 1011 produces exactly one found
  • reset returns the state and output to their specified values
  • all reachable states have defined transitions
  • any required illegal-state recovery reaches the safe state in the promised time

For a Mealy output, also toggle the input between clock edges and confirm whether within-cycle output changes are allowed by the interface. For a registered output, assert that it changes only on the active edge.

How Mealy and Moore Logic Mix in a CPU

A small processor controller illustrates why the distinction is rarely all-or-nothing.

  • A microstep or pipeline-control state can select a fixed bundle of register enables and multiplexer controls. That behavior is Moore-like.
  • A branch decision can combine the current control state, decoded instruction, and current condition flag. That decision is Mealy-like.
  • The final controls may be registered before driving the datapath, changing the externally visible timing without changing the underlying decision function.

The instruction-register and decode-stage guide shows how an instruction becomes control information, while the CPU flags-register guide explains the status inputs used by conditional control.

Decision Guide

Use the interface behavior—not a preference for one label—as the deciding factor:

QuestionDesign implication
Must an output describe a persistent mode?A Moore state is often natural.
Must an event respond to state and current input in the same cycle?A Mealy expression may be natural.
Can the input change asynchronously?Add the correct CDC handling first.
Must the output never pulse between edges?Register it or prove a hazard-safe implementation.
Is one cycle of interface latency acceptable?Registered outputs can simplify timing and verification.
Is state count or timing critical?Compare synthesized implementations and routed timing.
Is fault recovery required?Define the fault model and use verified safe-state behavior.

The strongest practical rule is simple: state what the output means in time. Once that contract is precise, Mealy or Moore usually becomes an implementation consequence rather than a philosophical choice.

Continue Learning

Build both 1011 detectors in DigiSim and use the same sampled input sequence for each. Observe state, input, and found together, and label whether values are interpreted before or after each edge. Then register the Mealy output and compare the new interface timing.

Continue with instruction decoding, CPU flags and conditional control, or static and dynamic hazards.

The formal models trace back to George H. Mealy’s 1955 paper, “A Method for Synthesizing Sequential Circuits”, and Edward F. Moore’s 1956 chapter, “Gedanken-Experiments on Sequential Machines”. Their definitions remain useful; the physical implementation still has to meet today’s reset, CDC, timing, and verification requirements.

Apply the concept in a simulator model.