Electronic – From a state transition table, how to determine if I’m dealing with a Mealy or Moore machine

Moore to Mealy conversion is easy. Here are the steps:

• Let S(i) be current state and O(i) be output in this state
• Attach O(i) output to all state transitions coming into the S(i) state
• Delete O(i) output from the state S(i)
• Goto next state
• Repeat steps of the above procedure until all states are handled

Note that for the for start state S(0), the procedure remains nearly the same except that O(0) will be assigned on reset. Also, the number of states remain unchanged in moore to mealy conversion.

Mealy to Moore conversion is much more complicated. It is basically the reverse process except that sometimes a state needs to be split(or copied) when there is a conflict of distinct outputs on the transitions coming into that state. The distinct outputs on the incoming edges are then assigned to the respective copy of the state. Also, each copy retains all the original outgoing edges. This procedure is repeated for subsequent states until remaining states are handled. The number of states in resulting Moore machine is much higher than original mealy machine. There are specific algorithms used in EDA tools to do this.

From a discrete logic & HDL perspective:

-Mealy machines (generally) have less states. Mealy machines change their output based on their current input and present state, rather than just the present state. However, less states doesn't always mean simpler to implement.

-Moore machines may be safer to use, because they change states on the clock edge (if you are using DFF logic for present and next state), whereas Mealy machines are faster, because the state is dependent on the input. Thus, the state can change asynchronously. This comes down to predictability vs raw speed. When it comes down to it, it's difficult to draw hard lines where one machine would always be better than the other.

It really comes down to the specific task at hand. Does one want to have a synchronous or asynchronous machine? Is speed paramount? Will there be potential unstable (bouncing) signals? Are both the inputs and present state readily available? The answer to each of these questions determines the type of machine that would work best.

It's worth mentioning that for a hardware implementation, Mealy machines require less hardware in their circuits, but when working with an HDL and RTL scenario, the actual amount of discrete hardware may not be terribly important.