Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #28758

Re: FSM - Mealy vs. Moore

Show all headers | View raw

On 8/13/19 1:27 AM, Rick C wrote:
> On Monday, August 12, 2019 at 10:19:28 PM UTC-4, Richard Damon wrote:
>> On 8/12/19 10:05 AM, Rick C wrote:
>>> I'm not sure why you say it is hard to code FSMs in programming languages.  It's actually easy.  It only requires that you keep track of the present state and calculate the next state before updating the present state.  In effect your present state is your state holding variable and next state is your calculation workspace. 
>>>
>>> Then 
>>>
>>> run_state_update (inputs)
>>>   next_state = f(inputs, present_state);
>>>   present_state = next_state;
>>>   outputs = g(inputs, present_state); // omit inputs if Moore
>>>   end; 
>>>
>>> Define the functions f and g and you are done.  
>>>
>>> This is why I say in most cases there is no real difference in Mealy vs. Moore machines.  In a hardware implementation the outputs could change in a Mealy machine when the inputs change between clocks, but in most hardware or software implementations this is not important because the FSM logic is synchronous as are the circuits it feeds. 
>>>
>>> -
>>
>> First, your definition is wrong. outputs needs to be computed BEFORE you
>> update the present_state, for both Mealy and Moore, the output is a
>> function of the CURRENT state (and possible the input for Mealy).
> 
> I believe you are not correct.  The inputs are always current.  The issue is which state is used, the current or the previous.  You would NOT update the outputs BEFORE the state has changed or they would in essence be registered and be a cycle late.  

I suppose the problem is trying to use the same computational model for
Mealy and Moore. There is also a bit of an issue of what is 'current'. I
am used to the computational model where you compute the 'next' state
from the current conditions (thus effectively doing the calculations
during the cycle) and then the clock edge event happens which copies all
the next states into current state.

For a Mealy machine, we need to call the update function on the clock
edge, and compute the next state based on the values of the input and
the state just before the clock, but then shortly after that, and other
state machines change, the inputs will change, and we need to update the
output (but just the outputs) to respond to those changes, and then
those changes may create another round of updates to propogate those
changes, and so on, until the system becomes stable, or until we exceed
our 'clock period' and then we can let the clock transition again and
repeat the whole cycle.

The Moore model is much simpler as everything is clock, so we never need
the extra cycle to propagate the changes.

> 
> I don't know if you know VHDL, but it has the concept of a sensitivity list.  Any time an input to a non-clocked function is updated, that function is evaluated to calculate the output.  In the case of a Moore machine the outputs would only be calculated when the present state changes, meaning AFTER being updated.  

Yes, I am quite familiar with VHDL and sensitivitiy lists (though I use
Verilog more). The issue is that when you write a software state
machine, you don't do it that way.

> 
> For a clocked process it is evaluated on the appropriate clock edge.  So the next state is calculated and passed onto the present state at that time.  
> 
> If you want to utilize the Mealy model, then the software need to accommodate updating the output when the inputs change as well as when the state changes.  However, in most uses in software it won't matter since the module is not run other than when a state change is considered - equivalent to the clocked process in VHDL. 

> 
> If you want to produce the same effect of a Mealy machine in software, you need to evaluate the output function separate from the state changes... essentially any time an input might change.  A bit esoteric for most applications.  The reality is that a true Mealy FSM model is virtually never used in software. 

Yes, that is part of my point, that the combinatorial nature of the
Mealy model makes it hard to model in a software environment.
> 
> 
>> Second, since you often want to connect state machines to each other,
>> you run into an issue if two state machines depend on each others outputs.
>>
>> For example, write as two disjoint procedures with some external logic
>> to interconnect them the following machines.
>>
>> The first is a Moore machine whose output is its state as a 3 bit
>> number, and if the input is a 1 it increments, and if it is a 0 it
>> decrements.
>>
>> Second machine is a Mealy Machine which takes the first machines output
>> as its input. It has two states, It transitions to state 0 if the input
>> is 7 and to state 1 if the input is 0, and the first output is what the
>> next state will be, so a 1 if the input is 0 or the state is 1 and the
>> input is not 7, and the second output is the current state.
>>
>> IF we initial the system to state 0 for both machines, we should get the
>> following results
>>
>> S1  S2 O2
>> 000 0  1
>> 001 1  1
>> 010 1  1
>> 011 1  1
>> 100 1  1
>> 101 1  1
>> 110 1  1
>> 111 1  0
>> 110 0  0
>> 101 0  0
>> 100 0  0
>> 011 0  0
>> 010 0  0
>> 001 0  0
>> 000 0  1
>>
>> The external logic should not have any knowledge of the details of the
>> internals of the machines, but call the update function for each machine
>> once giving it the inputs, and taking (and storing) the outputs, and not
>> be have exposed the internal state (except as it happens to be an
>> output). It should be possible to update either (or both) of the update
>> functions to different logic and still have a working machine, without
>> needing to change the external logic.
> 
> I follow your example until the final conclusion.  I don't know what you mean by "It should be possible to update either (or both) of the update functions to different logic".  
> 
> What external logic???  Do you mean the software that invokes and connects the signals between the two machines? 
> 
> I'm not clear what issue you are trying to address. 
> 
You define state machines state1(input1) and state2(input1) both of
which return the output of the state machine.

Thus you can write something like

output1 = state1(input1)
output2 = state2(input2)

but the issue is that input2 may be defined in terms of output1 and
input1 in terms of output2.

This is the essential definition of a state machine, it is fully defined
by its input-state-output relationships, and nothing, other than through
its outputs, should otherwise depend on its state.

Software also has a difficulty dealing with multiple interconnected
state machines on the same clock domain, as you really need to first go
though and remember all the inputs, and then you can update the output
states, because the software will update the states sequentially, but
the definition is to do them simultaneously. This adds 'state' to the
system that wasn't there, as you now need to remember the input values.

What this really shows is that while we do write state machines in
software, and it is a very important concept and tool, it is a somewhat
different concept than in a hardware design, due to the very different
nature of timing and syncrony.

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

FSM - Mealy vs. Moore Rick C <gnuarm.deletethisbit@gmail.com> - 2019-08-10 15:21 -0700
  Re: FSM - Mealy vs. Moore Paul Rubin <no.email@nospam.invalid> - 2019-08-10 18:08 -0700
    Re: FSM - Mealy vs. Moore Rick C <gnuarm.deletethisbit@gmail.com> - 2019-08-10 19:00 -0700
  Re: FSM - Mealy vs. Moore "A.P.Richelieu" <aprichelieu@gmail.com> - 2019-08-11 08:10 +0200
    Re: FSM - Mealy vs. Moore Rick C <gnuarm.deletethisbit@gmail.com> - 2019-08-10 23:28 -0700
    Re: FSM - Mealy vs. Moore Richard Damon <Richard@Damon-Family.org> - 2019-08-12 08:04 -0400
      Re: FSM - Mealy vs. Moore Rick C <gnuarm.deletethisbit@gmail.com> - 2019-08-12 07:05 -0700
        Re: FSM - Mealy vs. Moore Richard Damon <Richard@Damon-Family.org> - 2019-08-12 22:19 -0400
          Re: FSM - Mealy vs. Moore Rick C <gnuarm.deletethisbit@gmail.com> - 2019-08-12 22:27 -0700
            Re: FSM - Mealy vs. Moore Richard Damon <Richard@Damon-Family.org> - 2019-08-14 23:13 -0400
              Re: FSM - Mealy vs. Moore Rick C <gnuarm.deletethisbit@gmail.com> - 2019-08-14 21:05 -0700
                Re: FSM - Mealy vs. Moore Richard Damon <Richard@Damon-Family.org> - 2019-08-16 21:22 -0400
                Re: FSM - Mealy vs. Moore Rick C <gnuarm.deletethisbit@gmail.com> - 2019-08-16 20:15 -0700
  Re: FSM - Mealy vs. Moore Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2019-08-12 10:12 -0400

csiph-web