FSM - Mealy vs. Moore

I'm discussing Finite State Machine (FSM) design in logic with some hardwar e 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 d one" 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 FS M. In this case one does not need to concern with the issue of an output c hanging immediately without being clocked...

But then that really is not the distinction that this classification is int ended 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 commen t.

--
  Rick C. 

  - Get 1,000 miles of free Supercharging 
 Click to see the full signature
Reply to
Rick C
Loading thread data ...

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.

Reply to
Paul Rubin

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 cl ocked. 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, otherwi se Moore.

Example... state B can have two outputs depending on whether it came from s tate 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 th e inputs and present state which will set the next state as well as the out puts, 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 consid ered it is a Moore machine.

That isn't even a good way to put it since these coding styles don't guaran tee the distinction. A Moore machine can be coded so the outputs are set a t the same place in the code as the state. The Mealy FSM will simply alway s 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 i n 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 
 Click to see the full signature
Reply to
Rick C

Den 2019-08-11 kl. 00:21, skrev Rick C:

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

Reply to
A.P.Richelieu

dware folks and I thought I'd ask what a software community thinks.

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

lock, for all practical purposes, is equivalent to entering the code for th e FSM. In this case one does not need to concern with the issue of an outp ut changing immediately without being clocked...

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 inpu t as well and so effectively the outputs are part of the state even if the next state does not depend on them.

vely all inputs and outputs are clocked.

mment.

In software there is no changes in inputs other than at evaluations when th e code runs. So all changes are at clock transitions. In effect it is lik e 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 dif ferent from additional state variables. In theory you could evaluate the o utputs 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 w ith 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 
 Click to see the full signature
Reply to
Rick C

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

Reply to
Richard Damon

issue

he

to

)

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 s tate and calculate the next state before updating the present state. In ef fect your present state is your state holding variable and next state is yo ur 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. Mo ore machines. In a hardware implementation the outputs could change in a M ealy machine when the inputs change between clocks, but in most hardware or software implementations this is not important because the FSM logic is sy nchronous as are the circuits it feeds.

--
  Rick C. 

  -+ Get 1,000 miles of free Supercharging 
 Click to see the full signature
Reply to
Rick C

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 
 Click to see the full signature
Reply to
Phil Hobbs

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.

Reply to
Richard Damon

es. It's actually easy. It only requires that you keep track of the prese nt state and calculate the next state before updating the present state. I n effect your present state is your state holding variable and next state i s your calculation workspace.

. Moore machines. In a hardware implementation the outputs could change in a Mealy machine when the inputs change between clocks, but in most hardwar e or software implementations this is not important because the FSM logic i s synchronous as are the circuits it feeds.

I believe you are not correct. The inputs are always current. The issue i s which state is used, the current or the previous. You would NOT update t he outputs BEFORE the state has changed or they would in essence be registe red 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 out puts 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 th e 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 accommoda te updating the output when the inputs change as well as when the state cha nges. However, in most uses in software it won't matter since the module i s 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... ess entially any time an input might change. A bit esoteric for most applicati ons. The reality is that a true Mealy FSM model is virtually never used in software.

.

I follow your example until the final conclusion. I don't know what you me an by "It should be possible to update either (or both) of the update funct ions 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 
 Click to see the full signature
Reply to
Rick C

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.

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.

Yes, that is part of my point, that the combinatorial nature of the Mealy model makes it hard to model in a software environment.

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.

Reply to
Richard Damon

ages. It's actually easy. It only requires that you keep track of the pre sent 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.

vs. Moore machines. In a hardware implementation the outputs could change in a Mealy machine when the inputs change between clocks, but in most hardw are or software implementations this is not important because the FSM logic is synchronous as are the circuits it feeds.

ou

ue is which state is used, the current or the previous. You would NOT upda te the outputs BEFORE the state has changed or they would in essence be reg istered and be a cycle late.

Ok, but the outputs are always a function of the state in any FSM. So it o nly makes sense to compute them once the state has been updateds.

You are trying to emulate hardware which is not typically done in a softwar e based FSM, unless you are simulating an HDL perhaps. I've never seen any one compute the outputs at any time other than when the FSM state is being updated.

So functionally, there is no real difference between a Mealy or a Moore FSM when implemented in software. You can just call the outputs part of the s tate and it's a Mealy FSM, possibly not optimized.

Not sure what extra cycle you mean. If you are talking hardware or HDL, th en yeah, the Mealy machine can compute changes in outputs between clocks so is faster connecting input to output. But in software no one ever does th at directly because they aren't really trying to emulate the async path thr ough logic separate from the clocked "registers".

list. Any time an input to a non-clocked function is updated, that functio n 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 A FTER being updated.

That is exactly my point. When coding an FSM in software, everything is co mputed in a subroutine and everything in essence is registered, state and o utputs. So the distinction between Mealy and Moore becomes moot.

o the next state is calculated and passed onto the present state at that ti me.

modate 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 modu le is not run other than when a state change is considered - equivalent to the clocked process in VHDL.

you need to evaluate the output function separate from the state changes... essentially any time an input might change. A bit esoteric for most appli cations. The reality is that a true Mealy FSM model is virtually never use d in software.

Yes, and my point is no one does. Yet, you can still use the Mealy model w ith outputs assigned to the state transitions rather than to the states. T his may be equivalent to a Moore machine, but the coding won't be identical .

I started thinking about all this when someone was being rather pedantic ab out what a Mealy FSM is. I realized the only significant difference betwee n the two FSM types was that the Mealy FSM could change outputs at times ot her than clock edges if the inputs change. Then the state diagram with out puts specified on the state transitions is not really descriptive of those actions.

If you read Mealy's paper (which came after Moore's) he was considering wha t amounts to async sequential logic where the input changes trigger the out put changes. He talks about clocks, but doesn't show them in his drawings.

uts.

t
t
e

he

ne

ot

e

u mean by "It should be possible to update either (or both) of the update f unctions to different logic".

cts the signals between the two machines?

I believe FSM in software don't actually have the race condition of one FSM being updated before the other since there really aren't clocks involved. Nothing sets a sequence to the machines. On the other hand it is common f or them to have handshakes between processes. They are easy to design to c reate a synchronization, rather than causing a race condition.

The same is true in hardware when FSM are on different clocks. We have to take some specific measures to make sure all parts of the logic are using t he same value of the input since there are logic delays that can disrupt th e logic results around the clock edges. But in software in essence this ha s been done by passing the input values into a subroutine. At that point t he inputs have been registered in effect.

--
  Rick C. 

  ++ Get 1,000 miles of free Supercharging 
 Click to see the full signature
Reply to
Rick C

But the output change happens AFTER the clock, so shouldn't be done in the code that processes the changes that happen AT the clock. It means that anything that wants to depend on the state of those outputs to determine what happens at that clock edge, needs to do something to take special care so it gets the right value.

If there is no difference, then your doing it wrong. If the Moore machine can do anything the Mealy machine could do, then you don't really have a Mealy machine.

Again, you have a terminology issue, if you don't have the effect of the system clock, you don't have Moore or Mealy machines.

And the fact that you think the difference is moot, is a good indication that you no longer have Mealy and Moore machines.

Yes, the fundamental problem with using FSM terms designed for hardware based FSM in a software environment is that you don't have the clock.

Remember that the Mealy and Moore description describe the transitions happening on THE CLOCK, so if you don't have a THE CLOCK, you can't really use those term. Misusing terms becomes a good way to obfuscate what you are doing and to mislead others.

You could define "the clock" as a lap through the loop of the program, but then you need to make sure that all of the changes of state happen at that end of the loop, which means you can't just blindly update state as you move down the loop to its bottom.

In the same way, you can't use the FSM techniques across a multi-clock domain, as that violates the "THE CLOCK" condition, but you need to handle each clock domain by itself, and then the multi-clock boundry using multi-clock domain techniques.

In many ways this dicussion sounds a bit like a person wanting to describe a car, and even though it wasn't made by Volkswagen, they want to call the car a 'Beetle'. It may be a descriptive name, it may help evoke some ideas, but it is wrong. If the car isn't a Beetle, don't call it one, maybe it can be called Beetle like or Beetlish, but don't lie and use the wrong term.

In the same way, the terms Mealy and Moore when used for state machines do have very definite meanings, and imply very definite things. If you are in an environment where those don't apply, the terms don't apply either.

Reply to
Richard Damon

:

guages. It's actually easy. It only requires that you keep track of the p resent state and calculate the next state before updating the present state . In effect your present state is your state holding variable and next sta te is your calculation workspace.

y vs. Moore machines. In a hardware implementation the outputs could chang e in a Mealy machine when the inputs change between clocks, but in most har dware or software implementations this is not important because the FSM log ic is synchronous as are the circuits it feeds.

you

ssue is which state is used, the current or the previous. You would NOT up date the outputs BEFORE the state has changed or they would in essence be r egistered and be a cycle late.

r
I

ll

it only makes sense to compute them once the state has been updated.

Two points. First, I think you don't fully understand the purpose of the c lock. It is the trigger that causes the inputs and previous state to be ev aluated to produce the next state. Once the next state is updated the outp uts must be updated too. It matter not a whit where the code is. The only important thing is that the code is executed in the right order.

Second, I think you are trying to think in terms of hardware which is overk ill given that this is purely software.

r

he

d

tware based FSM, unless you are simulating an HDL perhaps. I've never seen anyone compute the outputs at any time other than when the FSM state is be ing updated.

FSM when implemented in software. You can just call the outputs part of t he state and it's a Mealy FSM, possibly not optimized.

Not according to Mealy. Although two pages are missing from the copy of hi s paper where he proves this, he does show that the two models describe equ ivalent machines. This is also stated in text books. In fact, they give a procedure for converting between the two.

Mealy never claimed he designed a "new" or "novel" FSM. His paper was abou t methods of designing FSMs from a theoretical aspect which he applied to p ulsed logic and as an extension of Moore's work also to relay logic. His a pproach uses a slightly different model which he goes on to show will descr ibe the same FSMs as Moore's model.

The issue of "present" value of inputs only arises when using level sensiti ve logic which was not around when Mealy and Moore wrote their papers. To Mealy the "present" state was the input at the time the state was being upd ated. The input at any other time does not show up in any of the methods o r diagrams he developed.

In some ways this is like trying to translate an ancient Greek text. It's n ot only about the words, but the context.

ed

, then yeah, the Mealy machine can compute changes in outputs between clock s so is faster connecting input to output. But in software no one ever doe s that directly because they aren't really trying to emulate the async path through logic separate from the clocked "registers".

Sorry, but there was nothing in either paper that mandated the use of clock s. The relay logic in Mealy's paper is definitely not clocked being async sequential logic.

But this is a red herring. I never said there was nothing like a clock. I said in software they don't try to emulate the async, combinational logic path that everyone insists is a part of a Mealy machine. In software the e ffect of the clock is a result of invoking the routine that performs the lo gic of the FSM. That is why I say it is equivalent to *all* outputs being clocked, both state and outputs. In addition, because all the inputs are f rozen while running the routine, it is as if the inputs are also registered .

y list. Any time an input to a non-clocked function is updated, that funct ion is evaluated to calculate the output. In the case of a Moore machine t he outputs would only be calculated when the present state changes, meaning AFTER being updated.

e

s computed in a subroutine and everything in essence is registered, state a nd outputs. So the distinction between Mealy and Moore becomes moot.

I think you don't appreciate that the two FSM models describe equivalent lo gic.

So the next state is calculated and passed onto the present state at that time.

ommodate updating the output when the inputs change as well as when the sta te changes. However, in most uses in software it won't matter since the mo dule is not run other than when a state change is considered - equivalent t o the clocked process in VHDL.

, you need to evaluate the output function separate from the state changes. .. essentially any time an input might change. A bit esoteric for most app lications. The reality is that a true Mealy FSM model is virtually never u sed in software.

el with outputs assigned to the state transitions rather than to the states . This may be equivalent to a Moore machine, but the coding won't be ident ical.

c about what a Mealy FSM is. I realized the only significant difference be tween the two FSM types was that the Mealy FSM could change outputs at time s other than clock edges if the inputs change. Then the state diagram with outputs specified on the state transitions is not really descriptive of th ose actions.

what amounts to async sequential logic where the input changes trigger the output changes. He talks about clocks, but doesn't show them in his drawi ngs.

,

tputs.

ic

put

put

the

he

the

he

hine

not

ate

ut

you mean by "It should be possible to update either (or both) of the update functions to different logic".

nects the signals between the two machines?

ed

gh

o
.
t

FSM being updated before the other since there really aren't clocks involv ed. Nothing sets a sequence to the machines. On the other hand it is comm on for them to have handshakes between processes. They are easy to design to create a synchronization, rather than causing a race condition.

to take some specific measures to make sure all parts of the logic are usi ng the same value of the input since there are logic delays that can disrup t the logic results around the clock edges. But in software in essence thi s has been done by passing the input values into a subroutine. At that poi nt the inputs have been registered in effect.

No, that is a red herring as a clock equivalent is inherent when invoking t he routine that performs the computations.

Again, Mealy and Moore FSM are not specific to CLOCKed sequential logic. S o please stop tossing red herrings in the path of the dogs.

Of course you can update the variables in the program any way you wish. Th e state is only an input to the next iteration of the routine and the outpu ts are only available when the routine exits.

Not sure why you toss this into the mix. The issues of Mealy and Moore FSM have nothing to do with clocks whatsoever.

er.

I'm not saying the terms Mealy and Moore FSM don't have definitions. I'm s aying people have dragged excess baggage into the discussion that Mealy and Moore never packed! Don't put YOUR definition of FSM on Mealy. He wrote a paper to discuss designing FSM, not implementations. He never said they required a clock and he never even knew inputs could change without the pot ential of a state change. Either the logic was pulsed logic where the data WAS the clock, or it was relay logic which is asynchronous and has no cloc k.

I wish those two pages weren't missing from Mealy's paper. That is where h e finishes the proof that the two FSM descriptions are equivalent. But you can find this in any textbook on the subject.

--
  Rick C. 

  --- Get 1,000 miles of free Supercharging 
 Click to see the full signature
Reply to
Rick C

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.