What Distinguishes a Moore Machine from a Mealy Machine?
Moore and Mealy finite state machines are two fundamental models of sequential logic in classical computing, distinguished primarily by how they generate their outputs. While a Moore machine determines its output solely from its current internal state, a Mealy machine determines its output from both its current state and its current external inputs. This structural difference leads to distinct behaviors in timing, state count, and hardware implementation.
Output Dependency and Formal Definitions
In sequential classical computing, a finite state machine (FSM) is formally defined by a set of states \(S\), an initial state \(s_0 \in S\), an input alphabet \(I\), an output alphabet \(O\), and a state transition function \(\delta: S \times I \to S\). The divergence between the two models lies in the output function \(\lambda\).
For a Moore machine, the output function maps only the current state to an output symbol:
\[\lambda_{\text{Moore}}: S \to O\]
Because the output depends exclusively on the state, it remains stable for the entire clock cycle until a state transition occurs.
For a Mealy machine, the output function maps both the current state and the current input to an output symbol:
\[\lambda_{\text{Mealy}}: S \times I \to O\]
Consequently, any change in the input can immediately alter the output, even before the next clock edge triggers a state transition.
Timing and Synchronization Behavior
The difference in output dependency directly affects how each machine responds to inputs over time:
- Moore Machines: Outputs are synchronous with the clock. When an input changes, the machine must first transition to a new state on the next active clock edge before the output reflects that change. This introduces a one-clock-cycle delay in the output response, which helps prevent glitches and makes timing analysis more predictable.
- Mealy Machines: Outputs can change asynchronously with respect to the clock if the inputs are not synchronized. Because the output reacts immediately to input changes, a Mealy machine can respond one clock cycle faster than an equivalent Moore machine. However, this also means that noise or momentary glitches on the input lines can propagate directly to the outputs.
State Count and Hardware Complexity
Mealy machines typically require fewer states than Moore machines to perform the same task. In a Moore machine, if a single state needs to produce two different outputs depending on the preceding input, that state must be split into two separate states—one for each output. A Mealy machine avoids this duplication because it can remain in a single state and vary its output based on the incoming input.
Fewer states often translate to fewer flip-flops in a hardware implementation. However, the combinational logic required to compute the outputs in a Mealy machine can be more complex because it must evaluate both state bits and input signals, whereas a Moore machine's output logic only evaluates state bits.
Choosing Between Moore and Mealy Machines
Engineers select between the two models based on the requirements of the digital system:
- Choose a Moore machine when glitch-free, synchronous outputs are critical, such as in control units or interfaces where timing stability is prioritized over immediate response.
- Choose a Mealy machine when minimizing latency or reducing the number of states (and therefore flip-flops) is the primary goal, provided the inputs are properly synchronized to avoid output glitches.