FSM - Mealy vs. Moore

I'm discussing Finite State Machine (FSM) design in logic with some hardware folks and I thought I'd ask what a software community thinks.  

Moore - outputs are only a function of the state. 

Mealy - outputs are a function of both inputs and state. 

So considering this issue, it seems it comes down to as Wikipedia says, "In Mealy machines, input change can cause output change as soon as logic is done" while Moore machines outputs don't change until the clock. 

In software, I was thinking this distinction is meaningless since the clock, for all practical purposes, is equivalent to entering the code for the FSM.  In this case one does not need to concern with the issue of an output changing immediately without being clocked...  

But then that really is not the distinction that this classification is intended to address.  The distinction is that the outputs of the Moore FSM are only dependent on the state while the Mealy outputs depend on the input as well and so effectively the outputs are part of the state even if the next state does not depend on them.  

I guess it is a bit different in software than hardware because effectively all inputs and outputs are clocked.  

As much as anything, I was thinking out loud here.  But feel free to comment. 

-- 

  Rick C.

  - Get 1,000 miles of free Supercharging
  - Tesla referral code - https://ts.la/richard11209

Rick C <gnuarm.deletethisbit@gmail.com> writes:
> I'm discussing Finite State Machine (FSM) design in logic with some
> hardware folks and I thought I'd ask what a software community thinks.

I think in software programming, this distinction doesn't really come
up.  We talk about FSM's where each state has a set of transitions for
given inputs.  I'm not sure whether you'd call that Mealy or Moore.
From a CS theory perspective there doesn't appear to be much difference
either.

On Saturday, August 10, 2019 at 9:08:15 PM UTC-4, Paul Rubin wrote:
> Rick C <gnuarm.deletethisbit@gmail.com> writes:
> > I'm discussing Finite State Machine (FSM) design in logic with some
> > hardware folks and I thought I'd ask what a software community thinks.
> 
> I think in software programming, this distinction doesn't really come
> up.  We talk about FSM's where each state has a set of transitions for
> given inputs.  I'm not sure whether you'd call that Mealy or Moore.
> From a CS theory perspective there doesn't appear to be much difference
> either.

That is just a FSM.  The Mealy/Moore distinction has to do with the outputs.  I was going to say since there is no evaluation of outputs other than at the "clock" meaning when the state machine module is run, everything is clocked.  But that's not what Mealy vs. Moore is about.  If there are outputs that depend on the inputs and not just the state, then it's Mealy, otherwise Moore.  

Example... state B can have two outputs depending on whether it came from state A or state C, that's Mealy.  A Moore machine will always have the same outputs for a given state regardless of how it got there.  

This is usually represented by code differences.  If your code evaluates the inputs and present state which will set the next state as well as the outputs, it is potentially a Mealy FSM.  If it evaluates the outputs after the next state has been written to the current state and inputs are not considered it is a Moore machine.  

That isn't even a good way to put it since these coding styles don't guarantee the distinction.  A Moore machine can be coded so the outputs are set at the same place in the code as the state.  The Mealy FSM will simply always set the same outputs for any next state regardless of which current state in the code is executing.  

Like I said, I'm just trying to work this out in my head.  I've done FSMs in hardware and software many times.  It seems like the theory of Mealy and Moore type machines is not really very representative in practice. 

-- 

  Rick C.

  + Get 1,000 miles of free Supercharging
  + Tesla referral code - https://ts.la/richard11209

Den 2019-08-11 kl. 00:21, skrev Rick C:
> I'm discussing Finite State Machine (FSM) design in logic with some hardware folks and I thought I'd ask what a software community thinks.
> 
> Moore - outputs are only a function of the state.
> 
> Mealy - outputs are a function of both inputs and state.
> 
> So considering this issue, it seems it comes down to as Wikipedia says, "In Mealy machines, input change can cause output change as soon as logic is done" while Moore machines outputs don't change until the clock.
> 
> In software, I was thinking this distinction is meaningless since the clock, for all practical purposes, is equivalent to entering the code for the FSM.  In this case one does not need to concern with the issue of an output changing immediately without being clocked...
> 
> But then that really is not the distinction that this classification is intended to address.  The distinction is that the outputs of the Moore FSM are only dependent on the state while the Mealy outputs depend on the input as well and so effectively the outputs are part of the state even if the next state does not depend on them.
> 
> I guess it is a bit different in software than hardware because effectively all inputs and outputs are clocked.
> 
> As much as anything, I was thinking out loud here.  But feel free to comment.
> 

There is no difference between S/W and H/W.
Most hardware today is described with software.

When you program in Verilog or VHDL you can implement both Moore and 
Mealy statemachines.

When you program in procedural languages, you can drive a statemachine 
with a clock tick or in a loop, but you can still change the output by 
taking an interrupt when an input is toggled.

AP

On Sunday, August 11, 2019 at 2:10:23 AM UTC-4, A.P.Richelieu wrote:
> Den 2019-08-11 kl. 00:21, skrev Rick C:
> > I'm discussing Finite State Machine (FSM) design in logic with some hardware folks and I thought I'd ask what a software community thinks.
> > 
> > Moore - outputs are only a function of the state.
> > 
> > Mealy - outputs are a function of both inputs and state.
> > 
> > So considering this issue, it seems it comes down to as Wikipedia says, "In Mealy machines, input change can cause output change as soon as logic is done" while Moore machines outputs don't change until the clock.
> > 
> > In software, I was thinking this distinction is meaningless since the clock, for all practical purposes, is equivalent to entering the code for the FSM.  In this case one does not need to concern with the issue of an output changing immediately without being clocked...
> > 
> > But then that really is not the distinction that this classification is intended to address.  The distinction is that the outputs of the Moore FSM are only dependent on the state while the Mealy outputs depend on the input as well and so effectively the outputs are part of the state even if the next state does not depend on them.
> > 
> > I guess it is a bit different in software than hardware because effectively all inputs and outputs are clocked.
> > 
> > As much as anything, I was thinking out loud here.  But feel free to comment.
> > 
> 
> There is no difference between S/W and H/W.
> Most hardware today is described with software.
> 
> When you program in Verilog or VHDL you can implement both Moore and 
> Mealy statemachines.
> 
> When you program in procedural languages, you can drive a statemachine 
> with a clock tick or in a loop, but you can still change the output by 
> taking an interrupt when an input is toggled.

In software there is no changes in inputs other than at evaluations when the code runs.  So all changes are at clock transitions.  In effect it is like having everything run through registers. 

So while an output in a Mealy machine can be a function of inputs and state, it will only change when the code is evaluated, so in effect it is no different from additional state variables.  In theory you could evaluate the outputs more often, but I seriously doubt anyone writes software that way.  Bottom line is the distinction between Mealy and Moore machines vanishes in software.  

It's a rather arbitrary distinction anyway.  Pieces of logic can be pulled off and separated turning Mealy into Moore or other logic can  be grouped with Moore turning it into Mealy.  The only utility to the distinction is in the tools you use to design and analyze the code.  

-- 

  Rick C.

  -- Get 1,000 miles of free Supercharging
  -- Tesla referral code - https://ts.la/richard11209

On 8/11/19 2:10 AM, A.P.Richelieu wrote:
> Den 2019-08-11 kl. 00:21, skrev Rick C:
>> I'm discussing Finite State Machine (FSM) design in logic with some
>> hardware folks and I thought I'd ask what a software community thinks.
>>
>> Moore - outputs are only a function of the state.
>>
>> Mealy - outputs are a function of both inputs and state.
>>
>> So considering this issue, it seems it comes down to as Wikipedia
>> says, "In Mealy machines, input change can cause output change as soon
>> as logic is done" while Moore machines outputs don't change until the
>> clock.
>>
>> In software, I was thinking this distinction is meaningless since the
>> clock, for all practical purposes, is equivalent to entering the code
>> for the FSM.  In this case one does not need to concern with the issue
>> of an output changing immediately without being clocked...
>>
>> But then that really is not the distinction that this classification
>> is intended to address.  The distinction is that the outputs of the
>> Moore FSM are only dependent on the state while the Mealy outputs
>> depend on the input as well and so effectively the outputs are part of
>> the state even if the next state does not depend on them.
>>
>> I guess it is a bit different in software than hardware because
>> effectively all inputs and outputs are clocked.
>>
>> As much as anything, I was thinking out loud here.  But feel free to
>> comment.
>>
> 
> There is no difference between S/W and H/W.
> Most hardware today is described with software.
> 
> When you program in Verilog or VHDL you can implement both Moore and
> Mealy statemachines.
> 
> When you program in procedural languages, you can drive a statemachine
> with a clock tick or in a loop, but you can still change the output by
> taking an interrupt when an input is toggled.
> 
> AP


Maybe in Theory there is no difference between Hardware and Software
(and I am not sure you can even really make that claim) but in Practice
there is a lot of difference.

Hardware is generally a HIGHLY PARALLEL environment, lots of stuff
happens at once. Software is highly serial, instructions act in
sequence, one after the other, with maybe a bit of parallelism if you
have a multi-core processor, at which point you will use software rules
to make sure those interactions happen in the right order.

It is VERY hard to make an accurate Mealy or Moore FSM model in software
(at least for multiple interacting FSM) as fundamental to the concept is
a master clock that all state gets updated on at once. The best you can
do in software is have all the state machines compute a 'next state' and
then generate a 'clock tick' and update all the machines at once to
their next state.

Verilog and VHDL are very different languages than a normal programing
language because they are parallel languages. In a normal computer
langauge the statements

  i := j;
  j := k;
  k := (some expression);

has a very different result than the statements

  k := (some expression);
  j := k;
  i := k;

the first leave i and j having a history of te values computed for k,
while the second has all 3 storing the same value. This is because in a
normal programming language, statements are executed sequentially, and
one statement doesn't start until the previous statement is done
(optimizations may reorder things, but the appearance to the programmer
is this fixed oreder)

In Verilog
  i <= j;
  j <= k;
  k <= (some expression)

and
  k <= (some expression)
  j <= k;
  i <= j;

both do the same thing as a block of statements all execute in parallel,
on the clocking term the expression is part of. The language effectively
building up that next state vector and updating all the items in
parallel. (The languages do have ways of generating sequential
descriptions, one statement executing before the next, but this can lead
to unrealizable descriptions, but can be useful for simulation test beds.)

On Monday, August 12, 2019 at 8:04:57 AM UTC-4, Richard Damon wrote:
> On 8/11/19 2:10 AM, A.P.Richelieu wrote:
> > Den 2019-08-11 kl. 00:21, skrev Rick C:
> >> I'm discussing Finite State Machine (FSM) design in logic with some
> >> hardware folks and I thought I'd ask what a software community thinks.
> >>
> >> Moore - outputs are only a function of the state.
> >>
> >> Mealy - outputs are a function of both inputs and state.
> >>
> >> So considering this issue, it seems it comes down to as Wikipedia
> >> says, "In Mealy machines, input change can cause output change as soon
> >> as logic is done" while Moore machines outputs don't change until the
> >> clock.
> >>
> >> In software, I was thinking this distinction is meaningless since the
> >> clock, for all practical purposes, is equivalent to entering the code
> >> for the FSM.  In this case one does not need to concern with the issue
> >> of an output changing immediately without being clocked...
> >>
> >> But then that really is not the distinction that this classification
> >> is intended to address.  The distinction is that the outputs of the
> >> Moore FSM are only dependent on the state while the Mealy outputs
> >> depend on the input as well and so effectively the outputs are part of
> >> the state even if the next state does not depend on them.
> >>
> >> I guess it is a bit different in software than hardware because
> >> effectively all inputs and outputs are clocked.
> >>
> >> As much as anything, I was thinking out loud here.  But feel free to
> >> comment.
> >>
> > 
> > There is no difference between S/W and H/W.
> > Most hardware today is described with software.
> > 
> > When you program in Verilog or VHDL you can implement both Moore and
> > Mealy statemachines.
> > 
> > When you program in procedural languages, you can drive a statemachine
> > with a clock tick or in a loop, but you can still change the output by
> > taking an interrupt when an input is toggled.
> > 
> > AP
> 
> 
> Maybe in Theory there is no difference between Hardware and Software
> (and I am not sure you can even really make that claim) but in Practice
> there is a lot of difference.
> 
> Hardware is generally a HIGHLY PARALLEL environment, lots of stuff
> happens at once. Software is highly serial, instructions act in
> sequence, one after the other, with maybe a bit of parallelism if you
> have a multi-core processor, at which point you will use software rules
> to make sure those interactions happen in the right order.
> 
> It is VERY hard to make an accurate Mealy or Moore FSM model in software
> (at least for multiple interacting FSM) as fundamental to the concept is
> a master clock that all state gets updated on at once. The best you can
> do in software is have all the state machines compute a 'next state' and
> then generate a 'clock tick' and update all the machines at once to
> their next state.
> 
> Verilog and VHDL are very different languages than a normal programing
> language because they are parallel languages. In a normal computer
> langauge the statements
> 
>   i := j;
>   j := k;
>   k := (some expression);
> 
> has a very different result than the statements
> 
>   k := (some expression);
>   j := k;
>   i := k;
> 
> the first leave i and j having a history of te values computed for k,
> while the second has all 3 storing the same value. This is because in a
> normal programming language, statements are executed sequentially, and
> one statement doesn't start until the previous statement is done
> (optimizations may reorder things, but the appearance to the programmer
> is this fixed oreder)
> 
> In Verilog
>   i <= j;
>   j <= k;
>   k <= (some expression)
> 
> and
>   k <= (some expression)
>   j <= k;
>   i <= j;
> 
> both do the same thing as a block of statements all execute in parallel,
> on the clocking term the expression is part of. The language effectively
> building up that next state vector and updating all the items in
> parallel. (The languages do have ways of generating sequential
> descriptions, one statement executing before the next, but this can lead
> to unrealizable descriptions, but can be useful for simulation test beds.)

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. 

-- 

  Rick C.

  -+ Get 1,000 miles of free Supercharging
  -+ Tesla referral code - https://ts.la/richard11209

On 8/10/19 6:21 PM, Rick C wrote:
> I'm discussing Finite State Machine (FSM) design in logic with some
> hardware folks and I thought I'd ask what a software community
> thinks.
> 
> Moore - outputs are only a function of the state.
> 
> Mealy - outputs are a function of both inputs and state.
> 
> So considering this issue, it seems it comes down to as Wikipedia
> says, "In Mealy machines, input change can cause output change as
> soon as logic is done" while Moore machines outputs don't change
> until the clock.
> 
> In software, I was thinking this distinction is meaningless since the
> clock, for all practical purposes, is equivalent to entering the code
> for the FSM.  In this case one does not need to concern with the
> issue of an output changing immediately without being clocked...
> 
> But then that really is not the distinction that this classification
> is intended to address.  The distinction is that the outputs of the
> Moore FSM are only dependent on the state while the Mealy outputs
> depend on the input as well and so effectively the outputs are part
> of the state even if the next state does not depend on them.
> 
> I guess it is a bit different in software than hardware because
> effectively all inputs and outputs are clocked.
> 
> As much as anything, I was thinking out loud here.  But feel free to
> comment.

Mealy seems to be sort of a hybrid of logic-driven and state-driven
design.  Logic-driven embedded programs are hard to get right and hard
to maintain, whereas state machines make you think out the desired
operation on gruesome detail ahead of time.

Cheers

Phil Hobbs

-- 
Dr Philip C D Hobbs
Principal Consultant
ElectroOptical Innovations LLC / Hobbs ElectroOptics
Optics, Electro-optics, Photonics, Analog Electronics
Briarcliff Manor NY 10510

http://electrooptical.net
https://hobbs-eo.com

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).

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.

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 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.  

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. 


> 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. 

-- 

  Rick C.

  +- Get 1,000 miles of free Supercharging
  +- Tesla referral code - https://ts.la/richard11209