A Finite State Machine (FSM), or just state machine, is a model of behavior composed of a finite number of states. We use these in computer engineering to model a “machine” with primitive memory. Based on the signals we recieve, we go to a certain state where information is processed, and then we wait for the signal that indicates we move to the next state. There are two types of FSMs we will talk about: Moore machines and Mealy machines.
Moore Machines
Moore machines are state machines where the output is determined by only the current state, not the inputs. For example, if we had designed a system where the state table looks like this:
Current State | Next State | Input |
00 | 01 | XX |
01 | 10 | XX |
10 | 11 | XX |
11 | 00 | XX |
we can see that it doesn’t even matter what the input and outputs are, the next state only depends on the current state. A typical example of Moore style state machines is a synchronous circuit composed of flip-flops connected to a clock. The state can only change when the clock pulses, and for flip-flops, the output(next state) is a function of the input(current state).
Mealy Machines
By contrast there are FSMs called Mealy machines where the next state is a function of both the current state, and the input.
Consider the truth table we discussed earler. In our Moore state machine design, we didn’t care what the input was. Now, however, we have decided that if the current state is 00 and the input is 0 , the next state is 01 .
Current State | Next State | Input |
00 | 01 | 0 |
00 | 01 | 1 |
01 | 10 | 0 |
01 | 10 | 1 |
10 | 11 | 0 |
10 | 11 | 1 |
11 | 00 | 0 |
11 | 00 | 1 |
We can see above that the next state is a function of the current state, and the input. A real world example of a Mealy machine is a mathematical cypher machine.
Mealy machines are typically sequential logic, whereas Moore machines are combinatorial logic.