- Moore machine: The outputs depend only on the present state.
See the block diagram in Figure 8.23. A combinational logic block maps the
inputs and the current state into the necessary flip-flop inputs to store
the appropriate next state. The outputs are computed by a combinational
logic block whose only inputs are the flip-flops' state outputs. The outputs
change synchronously with the state transition and the clock edge.
The finite state machines you have seen so far are all Moore machines.
- Mealy machine: The outputs depend on the present state and
the present value of the inputs.
See Figure 8.24. The outputs can change immediately after a change at the inputs, independent of the clock. A Mealy machine constructed in this fashion has asynchronous -outputs.
8.4.1 State Diagram and ASM Chart RepresentationsAn ASM chart intended for Moore implementation would have no conditional output boxes. The necessary outputs are simply listed in the state box. Conditional output boxes in the ASM chart usually imply a Mealy implementation.
The state diagrams in this figure are labeled more completely than our previous examples. For example, we make explicit the transitions that cause the machine to stay in the same state. We usually eliminate such transitions to simplify the state diagram. We also associate explicit output values with each transition in the Mealy state diagram and each state in the Moore state diagram. A common simplification places the output on the transition or in the state only when it is asserted. You should clarify your assumptions whenever you draw state diagrams.
8.4.2 Comparison of the Two Machine TypesBecause it can associate outputs with transitions, a Mealy machine can often generate the same output sequence in fewer states than a Moore machine.
8.4.3 Examples of Moore and Mealy Machines
Moore Machine DescriptionTo better understand the timing behavior of Moore and Mealy machines, let's begin by reverse engineering some finite state machines. We will work backward from a circuit-level implementation of the finite state machine to derive an ASM chart or state diagram that describes the machine's behavior.
(in this case a trivial one
)of the state alone. The state register is implemented by two master/slave J-K flip-flops, named A and B, respectively. The machine can be in any one of up to four valid states. The output Z and the state bit B are the same.
Signal Trace Method There are two systematic approaches to determining the state transitions: exhaustive signal tracing and extraction of the next state/output functions. We examine the former here and the latter in the next subsection.
Signal tracing uses a collection of input sequences to exercise the various state transitions of the machine. To see how it works, let's start by generating a sample input sequence.
=0. Figure 8.29 contains the timing waveform you would see after presenting the input sequence 1 0 1 0 1 0 to the machine. Because the FSM is implemented with master/slave flip-flops, the state time begins with the falling edge of the clock. Input X must be stable throughout the high time of the clock to guard against ones catching problems.
The sequence of events in Figure 8.29 is as follows. The asserted reset signal places the FSM in state 00. After the falling edge, input X goes high just after time step 20. At the next rising edge, the input is sampled and the next state is determined, but this is not presented to the outputs until the falling edge at time step 40. After a short propagation delay, the state becomes 11. We express the transition as "a 1 input in state 00 leads to state 11."
During the next state time, X is 0, and the FSM stays in state 11 as seen at time step 60. X now changes to 1, and at the next falling edge the state changes to 10.
The input next changes to 0, causing the state machine to remain in state 10 at time step 100. A transition to 1 causes it to change to state 01 after time step 120. The final transition to 0 leaves the machine in state 00.
Next State/Output Function Analysis Signal tracing is acceptable for a small FSM, but it becomes intractable for more complex finite state machines. With a single input and 2 bits of state, the example FSM has eight different transitions, two from each of four states. And the number of combinations doubles for each additional input bit and doubles again for each state bit.
Our alternative method derives the next-state functions directly from the combinational logic equations at the flip-flop inputs and the output function from the flip-flop outputs. For the mystery machine, these are
We can now express the flip-flop outputs, A
+, in terms of the excitation equations for the J-K flip-flop. We simply substitute the logic functions at the inputs into the excitation equations:
+, are now expressed in terms of the current state, A and B, and the input X. We show the K-maps that correspond to these functions in Figure 8.31.
=0 and B
=0. In state 01 with input 1, the next state is A
=1. With its behavior no longer a mystery, we show the ASM chart for this finite state machine in Figure 8.32.
Mealy Machine DescriptionContinuing with our reverse engineering exercise, consider the circuit of Figure 8.33.
(to avoid ones catching
)and must be valid a setup time before the falling edge.
Negative edge-triggered systems require that the inputs be stable before the falling edge that delineates the state times. This means that the outputs cannot be determined until just before the falling edge. The output remains valid only as long as it takes to compute a new output in the new state.
Similarly, for positive edge-triggered systems the outputs are valid at the rising edge. Again, the output is considered valid just before the clock edge that causes the machine to enter its new state.
(time step 40
(time step 60
). The waveform for output Z has a glitch. The valid output is determined only at the end of the state time. In this case, the output is 0.
A 1 in state 01 leads to state 11
(time step 80
). Again, the output in this state is the value of Z at the falling edge and thus is 1.
Reading a 0 in state 11 moves us to state 10
(time step 100
), with the output continuing to be asserted despite the momentary glitch.
A 1 in state 10 leads us to state 01
(time step 120
). The output goes low and will stay that way as long as the input X stays high.
Alternatively, we can discover the complete set of transitions by analyzing the next-state and output functions directly, just as we did in the Moore machine:
Since A is a D flip-flop, the function for A
+B X B
+B X Z
+is exactly the combinational logic function at its input. B is a J-K flip-flop, so we determine the function for B
+by substituting the logic functions at the J and K inputs into the J-K excitation function.
States, Transitions, and Outputs in Mealy and Moore Machines Suppose that a given state machine has M inputs and N outputs and is being implemented using L flip-flops. You might ask a number of questions to bound the complexity of this state machine. For example, what are the minimum and maximum numbers of states that such a machine might have? With L flip-flops, the implementation has the power to represent 2L states. But for a specific FSM as few as 1 and as many as 2L of these might be valid states.
What are the minimum and maximum numbers of state transitions that can begin in a given state? Since there must be an exit transition for each possible input combination, the minimum and the maximum are the same: 2M transitions.
A similar question involves the minimum and maximum numbers of state transitions that can end in a given state. Because we can have start-up states reachable only on reset, the minimum number of input transitions is 0. Since a single state could conceivably be the target of all the transitions of the finite state machine, the maximum number of input transitions is 2M * 2L, the number of possible input combinations multiplied by the number of states.
The maximum number depends on the kind of machine. For a Mealy machine, the maximum number of output patterns is the smaller of the number of transitions, 2M * 2L, or the number of possible output patterns, 2N. If the number of transitions exceeds the number of possible output patterns, then some must be repeated. In the Moore machine, the maximum is the smaller of the number of states, 2L, and the number of possible output patterns, 2N. If the number of states exceeds the number of output patterns, then some patterns will also need to be repeated.
As an example, consider a Moore machine with two inputs, one flip-flop, and three outputs. The state, transition, and output bounds are:
- Minimum number of states: 1
- Maximum number of states: 2
- Minimum number of output transitions
- Maximum number of output transitions
- Minimum number of input transitions
- Maximum number of input transitions
- Minimum number of observed output patterns: 1 Maximum number of observed output patterns: 2
Synchronous Mealy Machines The glitches in the output in Figure 8.34 are inherent in the asynchronous nature of the Mealy machine. As you have already seen, glitches are undesirable in real hardware controllers. But because Mealy machines encode control in fewer states, saving on state register flip-flops, it is still desirable to use them.
This leads to alternative synchronous design styles for Mealy machines. Simply stated, the way to construct a synchronous Mealy machine is to break the direct connection between inputs and outputs by introducing storage elements.
(can you figure out why?
). We will have more to say about synchronous Mealy machines in Chapter 10.
Synchronous Mealy machines can be constructed in TTL logic, but the designer must be careful. The approach leads to more complex designs that may affect the input/output timing of the FSM. You should use asynchronous Mealy machines only after very careful analysis of the input/output timing behavior of the finite state machine.