Digital Design / Module 6: Finite state machines
33. Moore and Mealy machines
Know the timing difference, not just the definition.
See it move
The idea
The difference lies in what the output depends on.
| Moore | Mealy | |
|---|---|---|
| Output depends on | State only | State and current input |
| Response | Next cycle, after the state changes | Same cycle as the input |
| States needed | Often more | Often fewer |
| Output glitches | Depends only on state logic | Input glitches can pass through |
What this means for timing
A Mealy output reacts in the same cycle as the input, which saves a cycle. The cost is a combinational path from input to output. This path joins with logic in the neighbouring blocks, and it can make timing harder. Inputs that wiggle also pass directly to the output.
A Moore output changes only after a state change, so it is steady for the whole cycle and easy to time, but it responds a cycle later.
Registered outputs
A common professional choice is a Mealy-style calculation with a register on the output. This is clean and -free, with Moore-like timing. Many teams require registered outputs at block boundaries.
Compare them directly
In the animation above, both machines detect the pattern 11. They watch identical inputs, but the Mealy machine responds one cycle sooner and uses only two states. The Moore machine needs a third state, whose whole purpose is to say "I have seen it".
Common mistake
Reciting only the definition. Interviewers follow up with: which is faster, which is safer, and how would each look on a waveform? Be ready to sketch the one-cycle difference and mention the combinational input-to-output path.
Key ideas
- Moore output depends on state; Mealy on state and input.
- Mealy can respond one cycle sooner, often with fewer states.
- Registered outputs avoid glitches.
Lab: your code, animated
Your exercise
Interview questions
coreWhich responds sooner?
Mealy, in the same cycle as the input. Moore waits until the next state.
basicWhat is the difference between a Moore and a Mealy machine, and what does that mean for when the output responds?
A Moore output depends only on the current state, while a Mealy output depends on the state and the current input. So a Mealy output can respond in the same cycle as the input, while a Moore output changes only after the state register has been updated, one cycle later.
basicA machine detects two 1s in a row on a serial input. How many states does the Moore version need, and how many does the Mealy version need?
The Moore version needs three: nothing seen, one 1 seen, and two 1s seen, where the third state exists to drive the output. The Mealy version needs two: nothing seen and one 1 seen, because the output is produced by the transition when the second 1 arrives. Mealy often needs fewer states for this reason.
coreOn the 11 detector, the input over five cycles is 0, 1, 1, 1, 0, changing just after each clock edge. In which cycles is each output high?
Mealy is high in cycles 3 and 4, during the second and third 1, because each time the previous bit was 1 and the current bit is 1. Moore is high in cycles 4 and 5, one cycle later, because it must first register that two 1s have been seen. Both are high for 2 cycles, since the overlapping run of three 1s contains two matches.
coreA Mealy output's input arrives 6.0 ns after the clock edge from another block. The Mealy logic takes 1.5 ns, the logic in the receiving block 2.0 ns, and the capture flop's setup is 0.3 ns, on a 10 ns clock. Does it meet timing?
The path from edge to capture is 6.0 + 1.5 + 2.0 + 0.3 = 9.8 ns, within the 10 ns period, so it passes with 0.2 ns of slack. The point is that a Mealy output joins its source and destination logic into one long combinational path across block boundaries. A registered output would split it into two short paths at the cost of a cycle.
coreThis registers the Mealy output of the 11 detector. How does mealy_r's timing compare with the Moore machine?
assign mealy = seen & din; always @(posedge clk) begin seen <= din; mealy_r <= seen & din; end
mealy_r is the Mealy output delayed by one clock, so it rises in the cycle after the second 1, exactly when the Moore output does. In simulation the two matched on every cycle. It keeps the Mealy machine's fewer states but gives a glitch-free output with Moore-like timing, which is why many teams register outputs at block boundaries.
coreThe input to a Mealy machine has a brief glitch in the middle of a cycle. What happens to the Mealy and Moore outputs?
The Mealy output can follow the glitch, because there is a combinational path from input to output. The Moore output does not change, because it only changes when the state register updates at an edge. Whether the Mealy glitch matters depends on the receiver: logic that samples it at the next edge is fine once it settles, but anything that reacts at any instant, such as a reset, a clock or an output pin, is not.
advancedA Moore machine with binary state encoding decodes an output from two state bits. Can that output still glitch, and how do you avoid it?
Yes. If both state bits change at the same edge, they never switch at exactly the same instant, so the decode can briefly see an intermediate pattern and produce a short false pulse. It settles within the cycle, so synchronous receivers are fine, but a glitch-sensitive receiver is not. Driving the output straight from a flop avoids it: register the output, use a one-hot bit as the output, or choose an encoding where the output is itself a state bit.
advancedBlock A has a Mealy output that feeds block B, and B has a Mealy output that feeds back into A. What can go wrong?
Each Mealy output is a combinational function of its inputs, so the path from A's input, through A, through B and back into A can form a combinational loop with no flop in it. That can oscillate or latch up and is very hard to time. Even without a loop, the chain makes long combinational paths across blocks. Registering outputs at block boundaries prevents both.