Finite-State Machines: Mealy vs. Moore

Most electronic devices have multiple finite-state machines (FSM) inside them. Basically, a FSM has multiple states. Each state has a set of outputs that achieve whatever the goal of that state is. An input (such as a clock pulse or the press of a button) leads to the FSM changing state.

A diagram for a FSM that I designed for my digital logic design class is below. It is a controller for a gumball machine that keeps track of how much money has been inserted (gumballs cost 20cents) and indicates what to output (gumball and how much change). The possible inputs are nickels, dimes, and quarters. The boxes represent the four states (which keep track of the total amount of change). The lines between the states are the instructions for which path to follow for any input. Each state has three arrows leaving it – one arrow for each possible coin inserted. The FSM stays in the current state if no coin is inserted. The blue describes the coin inputted and the red describes what the output of the gumball machine is. 

Of course, this state diagram is just a big picture that would need to be translated into electrical components. But it gets the idea across of what a FSM is. Now, there are two kinds of FSMs: Mealy and Moore. The output from a Mealy FSM depends on the current input. The output from a Moore FSM does not. To translate, when a FSM is changing state (generally on the high part of a clock pulse) it can venture out on the arrow without fully going into the next state until the clock is low again. So while the clock remains high, the FSM (if we anthropomorphize it) can look into its different options by seeing where the arrows lead but it can’t quite step onto the next stepping stone.

In a Mealy machine, the outputs occur on the arrows. In a Moore machine, the outputs occur on the stepping stone. Therefore, when a Mealy FSM “explores multiple pathways” during a single cycle of the clock (there are many different inputs in a short time), the output changes. If you could put in a nickel then a dime really quickly while the above (Mealy) FSM was in the 15cent stage, then you’d get two gumballs and 5cents change before the gumball machine controller actually transitioned into the 0cent (start) state. The clock would probably be set fast enough to not allow that but if it weren’t, you’d get a lot of free gumballs.

Mealy FSMs are nicer because they have fewer states than Moore FSMs. But, often the behavior of having multiple outputs during a single cycle can be a problem. So, if you can use a Mealy FSM then you’ll save some components. But a Moore FSM is easier to design in some ways and can be used for more applications.