Finite State Machines

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.

Leave a Reply

Your email address will not be published. Required fields are marked *