Designs based on Finite State Machines - Digital Design of Signal Processing Systems: A Practical Approach - page 392

inputs

Current
state

Combinational
Logic I

outputs

Next state

Combinational
Logic II

Current state

Figure 9.12 Composition of a Moore machine implementation of an FSM

combinational cloud computes the next state and the output is based on the current state and the
input. The state register has an asynchronous reset to initialize the FSM at any time if desired.
In a Moore machine implementation, outputs are only a function of the current state. As the
current sate is registered, output signals are stable for one complete clock cyclewithout any glitches.
In contrast to the Mealy machine implementation, the output will be delayed by one clock cycle.
The Moore machine may also result in more states as compared to the Mealy machine.
The choice between Mealy and Moore machine implementations is the designer's and is
independent of the design problem. In many design instances it is a fairly simple decision to
select one of the two options. In instances where some of the inputs are expected to glitch and
outputs are required to be stable for one complete cycle, the designer should always use the Moore
machine.
AMoore machine implementation is shown in Figure 9.12. The combinational logic-I of the FSM
computes the next state based on inputs and the current state, and the combinational logic-II of the
FSM computes the outputs based on the current state.

9.3.4 Mathematical Formulations

Mathematically an FSM can be formulated as a sextuple, (X, Y, S, s 0 , d, l), where X and Yare sets of
inputs and outputs, S is set of states, s 0 is the initial state, and d and l are the functions for computing
the next state and output, respectively. The expression for next state computation can be written as:

s k þ 1 ¼ d x k ; s k ð Þ; where x k 2 X and s k 2 S

Subscript k is the time index for specifying the current input and current state, so using this
notation sk þ 1 identifies the next state. For Mealy and Moore machines the expressions for
computing output can be written as:

Mealy machine : y k ¼ l s k ; x k ð Þ

Moore machine : y k ¼ l sðÞ

9.3.5 Coding Guidelines for Finite State Machines
Efficient hardware implementation of a finite state machine necessitates adhering to some coding
guidelines [10, 11].