conversion from Moore To Mealy

Question

Can somebody please explain how can I convert from Moore FSM to Mealy FSM and vice versa?

Answer 1

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.