Moore and Mealy Machines
Finite automata may have outputs corresponding to each transition. There are two types of finite state machines that generate output −
- Mealy Machine
- Moore machine
Mealy Machine
A Mealy Machine is an FSM whose output depends on the present state as well as the present input.
It can be described by a 6 tuple (Q, ∑, O, δ, X, q0) where −
Q is a finite set of states.
∑ is a finite set of symbols called the input alphabet.
O is a finite set of symbols called the output alphabet.
δ is the input transition function where δ: Q × ∑ → Q
X is the output transition function where X: Q × ∑ → O
q0 is the initial state from where any input is processed (q0 ∈ Q).
The state table of a Mealy Machine is shown below −
| Present state | Next state | |||
|---|---|---|---|---|
| input = 0 | input = 1 | |||
| State | Output | State | Output | |
| → a | b | x1 | c | x1 |
| b | b | x2 | d | x3 |
| c | d | x3 | c | x1 |
| d | d | x3 | d | x2 |
The state diagram of the above Mealy Machine is −
Moore Machine
Moore machine is an FSM whose outputs depend on only the present state.
A Moore machine can be described by a 6 tuple (Q, ∑, O, δ, X, q0) where −
Q is a finite set of states.
∑ is a finite set of symbols called the input alphabet.
O is a finite set of symbols called the output alphabet.
δ is the input transition function where δ: Q × ∑ → Q
X is the output transition function where X: Q → O
q0 is the initial state from where any input is processed (q0 ∈ Q).
The state table of a Moore Machine is shown below −
| Present state | Next State | Output | |
|---|---|---|---|
| Input = 0 | Input = 1 | ||
| → a | b | c | x2 |
| b | b | d | x1 |
| c | c | d | x2 |
| d | d | d | x3 |
The state diagram of the above Moore Machine is −
Mealy Machine vs. Moore Machine
The following table highlights the points that differentiate a Mealy Machine from a Moore Machine.
| Mealy Machine | Moore Machine |
|---|---|
| Output depends both upon the present state and the present input | Output depends only upon the present state. |
| Generally, it has fewer states than Moore Machine. | Generally, it has more states than Mealy Machine. |
| The value of the output function is a function of the transitions and the changes, when the input logic on the present state is done. | The value of the output function is a function of the current state and the changes at the clock edges, whenever state changes occur. |
| Mealy machines react faster to inputs. They generally react in the same clock cycle. | In Moore machines, more logic is required to decode the outputs resulting in more circuit delays. They generally react one clock cycle later. |