State Machine Design Guide
Mealy vs Moore, Timing Diagrams & Glitch-Free Outputs
1. Introduction — Thinking in States
Nearly every digital system of any complexity is a state machine in disguise: a UART’s shift-and-frame controller, a DDR memory controller’s command scheduler, a protocol decoder, or an elevator’s door logic. Designing it as an explicit finite state machine (FSM) — rather than as ad-hoc counters and if-chains — is what separates reliable digital design from intermittent, untraceable bugs. This guide covers the complete FSM design flow: conceptual modeling, the Mealy vs Moore decision, state encoding, timing diagrams, metastability and clock-domain crossing, glitch elimination, and synthesizable Verilog/VHDL implementations — with worked examples throughout.
A finite state machine has three parts: a state register holding the current state, a next-state (transition) logic computing the next state from the current state and inputs, and output logic. The two canonical architectures differ only in where the output logic samples its inputs.
2. FSM Fundamentals — States, Inputs and Outputs
2.1 Formal Model
S = set of states, I = input alphabet, O = output alphabet
δ: S × I → S (next-state function)
λ: S × I → O (output function — Mealy: depends on state and input)
λ: S → O (output function — Moore: depends on state only)
For finite hardware: |S| = 2N with N flip-flops. The machine advances on each clock edge.
2.2 Why Design with an Explicit FSM
| Approach | Clarity | Verifiability | Maintenance | Logic Cost |
|---|---|---|---|---|
| Ad-hoc flags + counters | Poor — behavior scattered | Hard — no explicit state space | Fragile | Often small |
| Explicit FSM | Excellent — diagram is the spec | Easy — enumerate states/transitions | Add/remove states cleanly | Slightly more, but predictable |
3. Mealy vs Moore — The Core Decision
3.1 Output Timing Difference
The defining difference is when outputs change. A Moore machine’s outputs depend only on state, so outputs change only on clock edges (synchronous, glitch-free by construction, one full clock later than the transition that caused them). A Mealy machine’s outputs depend on state and inputs, so outputs can change asynchronously with the inputs, within the clock period — faster response but at the cost of glitch risk and input dependency.
| Aspect | Mealy | Moore |
|---|---|---|
| Output depends on | State AND input | State only |
| Output timing | Can change mid-cycle with input | Changes only on clock edge |
| Response latency | Fast — responds in same cycle | One clock delayed vs Mealy |
| Glitch risk | Higher — combinational inputs propagate | Fundamentally glitch-free |
| # of states for same function | Usually fewer (factored into transitions) | Often more (output states duplicated) |
| HDL style | Outputs in combinational block | Outputs in synchronous / registered block |
| Best for | Protocols needing fast data gating (data valid on input) | Safety controllers, outputs shared, FSM-driven datapath |
3.2 Timing Diagram — Sequence Detector 101 (Overlapping)
State set (Moore): S0 (idle, out=0), S1 (got ‘1’, out=0), S2 (got ’10’, out=0), S3 (got ‘101’, out=1).
State set (Mealy, 3 states): S0 (out=0), S1 (after ‘1’, out=0), S2 (after ’10’, out=0; on ‘1’ → out=1).
Timeline (clk 0..5, input 1 0 1 1 0):
clk: 0 1 2 3 4 5
in: 1 0 1 1 0 —
Moore out: 0→…→ 0 0 1(samples at clk3 edge) 1 0
Mealy out: 0 → 0 1(appears as soon as 3rd ‘1’ & state S2 in clk3 period) 1 0
Key takeaway: the Mealy output for the third bit goes high within the clock period when the input arrives (combinational), while the Moore output only becomes 1 after the next clock edge. Overlapping detection: Moore returns to S2 after S3 on ‘0’, Mealy returns to S2 on ‘0’ and to S0 on ‘1’.
3.3 Mealy and Moore State Diagrams (ASCII)
Drawing the diagram first is the cheapest way to find missing transitions and unreachable corners. Below are the same “101” detector drawn both ways. In the Mealy diagram the output is written on the arrow (input/output); in the Moore diagram the output lives inside each bubble, so states that differ only in output value must be duplicated.
MOORE (5 states, out stored in state): MEALY (3 states, out on arrows):
1/0 0/0 1/0 1/1 0/0
S0 ----> S1 ----> S2 ----> S3 0/0 S1 1)
S3 --1/0--> S1 (overlap) S0 --------> S1 (on '1')
S3 --0/0--> S2 (overlap)
Moore needs S3 to produce out=1; Mealy "folds" that behavior
into the S2 --1/1--> S2 arrow (out fires immediately when din='1').
A useful rule of thumb: when the same output value must be emitted during several consecutive cycles regardless of the input, Moore is natural (the state repeats the output). When an output must coincide exactly with a specific input event arriving mid-cycle, Mealy matches the protocol handshake better and needs fewer states.
4. State Encoding — Binary, Gray, One-Hot
How you assign the bit patterns to states strongly influences logic size, speed, and power.
| Encoding | Bits for N states | Logic Size | Speed | Power/Glitches | Use When |
|---|---|---|---|---|---|
| Binary | ⌈log₂N⌉ | Minimal FF count | Depends on decode logic | Multiple bits toggle per transition | Default; tools optimize |
| Gray | ⌈log₂N⌉ | Similar | Good for adjacent transitions | 1 bit toggles/transition — low power, low glitch | Counters, async FIFO pointers, sequential state chains |
| One-hot | N (N FFs) | FF-expensive | Fastest decode — state bit IS the decode | Only 2 bits toggle → low power at high speed | FPGA FSMs (many FFs free), high-speed controllers |
| Johnson (twisted ring) | N/2 | Simple shift structure | High, regular | 2 toggles per transition | Sequencers, dividers |
– 4–8 states: let the synthesizer choose (usually binary/Optimal).
– FPGAs: prefer one-hot — extra flip-flops are free, decode logic shrinks dramatically.
– Clock-domain-crossing FIFO pointers: must use Gray — only 1 bit changes, eliminating multi-bit race at the synchronizer.
– Sequential chains (e.g., 0→1→2→3→4 always forward): Gray minimizes toggling and power.
5. From State Diagram to State Table to Logic
5.1 The Flow
- Draw the state diagram: bubbles = states, arrows = transitions labeled input/output (Mealy) or input only (Moore, output inside the bubble).
- Build the state table: rows = current state, columns = input combinations; cells give next state and output.
- Derive next-state/output equations (K-maps or directly) from the table.
- Assign codes (§4) and implement in HDL.
5.2 Worked Example — JK-Free FSM with Explicit Table
States (one-hot): G=100, Y=010, R=001. Moore outputs: light = G/Y/R directly.
State table:
Current | g=0 | g=1
G(100) | G | Y
Y(010) | Y | R
R(001) | R | G
Derived next-state (Q2Q1Q0, one-hot):
Q2′ = Q0·g + Q1·g (next G)
Q1′ = Q2·g + Q1·!g
Q0′ = Q2·!g + Q0·!g + Q1·g
This is exactly the “decoded” FSM: output = state bits directly (Moore guarantees no glitch on the lamp outputs).
6. Synchronous Design, Metastability and Clock Domains
6.1 Synchronous Discipline
All state changes must be clocked by the same clock (or a single properly-buffered clock tree). Asynchronous resets are allowed but must be synchronized against the clock before release (“reset synchronizer”). The corollary: never use combinational logic output as a clock — a glitch there clocks the FSM unpredictably.
Tclk_q + Tnext_logic + Tsetup ≤ Tclk
Slack = Tclk − (Tclk_q + Tnext_logic + Tsetup − Tskew)
For a one-hot FSM the next-state fan-in is just “state bit AND input mux” — critical paths are short. For a binary FSM, the decode of many state bits into a dense next-state equation is where the critical path hides; break wide muxes into pipelines or re-encode to one-hot when slack turns negative.
6.2 Metastability and MTBF
When a flip-flop’s input changes within its setup/hold window, it can enter a metastable state (indeterminate voltage between thresholds) that may resolve to either logic level after an unbounded resolution time τ. The mean time between failures grows exponentially with settling time:
where tres = resolving time available (time before the value is sampled downstream), fdata = async input toggle rate.
Two-flip-flop synchronizer: adds one clock of latency; the first FF may go metastable, but the second FF almost certainly resolves — MTBF typically from years to centuries. Three FFs for ultra-reliable async interfaces.
6.3 Clock Domain Crossing (CDC) Rules
| Crossing Type | Safe Method | Latency | Caveat |
|---|---|---|---|
| Single-bit control | 2-FF synchronizer | 2 clk | Pulse must be wider than 1 dest clk + slack (pulse synchronizer) |
| Multi-bit data (slow→fast) | Gray code + 2-FF sync, or handshake | 2 clk + handshake | Never sync raw multi-bit bus directly |
| Multi-bit FIFO | Async FIFO with Gray pointers | ~2 clk | Full/empty via Gray comparison |
| Fast→slow | Handshake / FIFO w/ backpressure | 2–3 clk | Must handle data loss by protocol |
7. Glitch-Free Outputs
7.1 Sources of Glitches
- Mealy combinational outputs: any input change ripples through output logic → narrow false pulses.
- Multi-bit state transitions: binary code with racing bits (e.g., 011→100 momentarily 111) glitches decoded output logic.
- Decoding full next state concurrently with changing inputs.
7.2 Remedies
| Technique | Method | Cost |
|---|---|---|
| Register the outputs | Add output D flip-flops clocked same clk; outputs change only on edges — move to Moore-like timing | +1 clk latency, +N FFs |
| Use Moore architecture | Outputs from state only → never combinatorial | More states sometimes |
| Gray / one-hot encoding | 1 bit (or 2 for one-hot) toggles per transition → no intermediate decode hazards | FF count |
| Qualify output with clk enable | AND combinational output with a strobe only when stable | Timing analysis |
| Double-register the decode | Register the decoded values before they reach output PADs | +1 clk latency |
8. Verilog and VHDL Implementation
8.1 Verilog — 101 Overlapping Detector (Moore, two-process style)
// Moore FSM: detect "101" overlapping
module seq101 (
input wire clk, rst_n,
input wire din,
output reg det
);
localparam S0=2'd0, S1=2'd1, S2=2'd2, S3=2'd3;
reg [1:0] state, next;
// Next-state logic (combinational, default to S0)
always @(*) begin
next = S0;
case (state)
S0: next = din ? S1 : S0;
S1: next = din ? S1 : S2;
S2: next = din ? S3 : S0;
S3: next = din ? S1 : S2; // overlapping
default: next = S0;
endcase
end
// State + output registers (synchronous, glitch-free Moore output)
always @(posedge clk or negedge rst_n) begin
if (!rst_n) begin state <= S0; det <= 1'b0; end
else begin
state <= next;
det <= (next == S3); // registered output → no glitch
end
end
endmodule
8.2 VHDL — Same Detector (Mealy, output depends on input)
-- Mealy FSM: detect "101" overlapping, output combinational
library ieee; use ieee.std_logic_1164.all;
entity seq101 is
port (clk, rst_n, din : in std_logic;
det : out std_logic);
end entity;
architecture rtl of seq101 is
type state_t is (S0, S1, S2);
signal state : state_t;
begin
process(clk, rst_n) begin
if rst_n = '0' then
state state state state <= S1 when din='1' else S0; -- Mealy: same-cycle detect
end case;
end if;
end process;
-- Mealy output: asserted within the same cycle din='1' in state S2
det <= '1' when (state = S2 and din = '1') else '0';
end architecture;
Danger note: the Mealy `det` fanout here is combinational — if `det` drives a clock or a synchronous handshake, register it or switch to Moore.
8.3 Synthesis Guidance
- Use
always @(posedge clk)blocks for state and outputs; keep next-state logic in a separate combinational block. - Define explicit, non-overlapping default states to avoid latches; never leave a case without default.
- For FPGAs, let the tool apply one-hot (or set
syn_encoding/FSM_ENCODINGattribute). - Assert a single, globally synchronized reset; verify with static timing analysis across corners.
9. Power and Low-Energy FSM Design
In battery-powered and thermal-constrained systems the FSM’s switching activity is often a hidden power hog: every flip-flop toggle consumes dynamic energy C·V²·f, and the decoded combinational glitches multiply the switching count. A few structural choices reduce energy without hurting performance.
9.1 Activity and Switching Reduction
| Technique | Mechanism | Trade-off |
|---|---|---|
| Gray encoding | 1 bit flips per transition instead of many | Slightly larger decode logic |
| One-hot + clock gating | Only the active state branch toggles | More FFs, needs CG cells |
| Output register gating | Disable output FFs when value unchanged | Extra enable logic |
| State minimization | Fewer FFs, fewer decoded gates | Requires reachability analysis |
| Sleep modes | State machine parks in SLEEP, clocks gated off | Wake-up latency |
9.2 Clock Gating Example
// Clock-gate the data-path when the FSM is idle
wire gclk;
assign gclk = clk & (state != S_IDLE); // simple gate,
// use ICG cells in ASIC flow
always @(posedge gclk)
data_path_reg <= compute(...); // no toggling while idle
Power-aware ordering: profile which states are active 99% of the time (e.g., an IDLE waiting for an interrupt). Encode that state so its decode fan-out is minimal, gate its output registers, and clock-gate the domains it does not touch. For an always-on MCU, an FSM that spends most cycles in a one-hot IDLE with gated data-path can cut dynamic power by 30–50% compared to a binary-coded machine that toggles several bits every clock.
10. Worked Example — Full Design: UART RX Byte Framer
State set (Moore): IDLE → START → D0..D7 → STOP → (back to IDLE)
Encoding: Gray-ish sequential 4-bit: 0000(IDLE),0001(START),0010(D0),0110(D1),0111(D2),0101(D3),0100(D4),1100(D5),1101(D6),1111(D7),1110(STOP). Consecutive states differ by 1 bit → glitch-free decode (Gray chain).
Timing: sample each bit at oversample counter = 8 (mid-sample), 16 clocks per bit; use a majority-of-3 voter at mid-bit to reject glitches.
Outputs (Moore, registered): rx_byte on STOP entry, frame_done pulse 1 clk in STOP, framing_error if stop sampled ‘0’.
Verification: simulate: 0x55, 0xAA, start bit only, noise on start. Checker: byte matches sent, done pulse width = 1, no lost sync for 10 frames.
Result: 11 states × 5 FFs one-hot → decode is trivial (state bit = meaning), Fmax comfortably above 100 MHz with 50 MHz UART clk.
11. Common Mistakes
- Mealy output into a clock enable or async reset path — the glitch races the circuit.
- Multi-bit bus crossing clock domains un-Grayed — corrupted values sampled (two synchronizers see different bits).
- Missing default in next-state case — synthesizer infers a latch or enables illegal-state entry.
- Sampling an async input directly without a 2-FF synchronizer — rare metastable failures field-visible years later.
- Outputting from `next` within the same always block in Verilog without registering — pairs me at gate level to a glitch source.
- Binary state count including illegal codes — one-hot FSM left untrained for unused patterns returns to a random reachable state; always route illegal states back to a safe state or a trap state that asserts an error (good for functional safety).
- Relying on reset polarity assumptions without checking the tool’s default (async vs sync) — mismatched reset trees.
12. Frequently Asked Questions
Q1. Mealy or Moore for my design?
If outputs must react within the same clock cycle to an input (data gating, fast protocols) → Mealy, but register critical outputs if possible. If glitch-free, single-clock outputs matter more (lights, enables, memory control) → Moore.
Q2. Does Moore always cost more states?
Not always, but commonly: outputs that depend on the current input need one state per output value vs Mealy’s single transition. When output sets are small, the extra states are trivial.
Q3. Is one-hot always the FPGA best choice?
For FSMs with >8 states on FPGAs, yes typically — FFs are cheap, logic shrinks, and timing closes easier. For ASICs with >100 states, binary/Optimal wins to conserve area.
Q4. How do I make a Mealy design glitch-free anyway?
Register the outputs (making them effectively synchronous), or gate the combinational output with a well-timed strobe, or convert to Moore.
Q5. What’s a safe way to cross a pulse into another clock domain?
Use a pulse synchronizer: stretch the pulse to ≥ 2 destination clocks, sync with 2-FFs, detect a rising edge, re-pulse. Never send a one-cycle single-domain pulse directly unless destination is much faster and you accept drop risk.
Q6. How do I verify an FSM for illegal-state recovery?
Simulate full-reachability (random input sequences) and run formal/reachability checks; implement a safe (default) or error/trap state and route all unassigned codes there. In hardware test, force-switch state bits to each illegal code and verify recovery.
Q7. What is the best reset strategy for an FSM?
Use a single asynchronous assert / synchronous deassert reset synchronizer so the FSM starts in one deterministic state and does not sample mid-toggle during release. Avoid long reset trees gated by combinational logic; if you need multiple resets, keep them in one well-defined domain or synchronize each into its own clock domain independently.
13. Design Checklist
- Write a one-sentence specification: what event(s) cause each state transition, and what each output must do (Mealy, Moore, or registered-both).
- Draw the state diagram first (paper or digital); mark illegal arrows you deliberately exclude, and prove every state is reachable and every reachable state is recoverable.
- Choose encoding from §4 by target (FPGA one-hot, ASIC binary/Optimal, GCD counters Gray) — record the choice in a comment.
- Keep next-state logic and output logic in separate blocks; register outputs for glitch-free signals; never feed a Mealy output into a clock or async reset.
- Add a 2-FF synchronizer for every external input; Gray-encode any multi-bit CDC; budget the latency in the protocol.
- Add a default/safe state and cover all illegal codes; assert a properly synchronized reset.
- Run lint and synthesis; review the synthesized netlist for inferred latches (missing default) and unmasked combinational loops.
- Simulate with directed test cases (each transition once), random stimulus for reachability, and a timeout watchdog in the testbench.
- Estimate power with toggle-rate-aware analysis if the FSM dominates dynamic power; apply clock gating where cheap.