On Friday, August 16, 2019 at 9:22:41 PM UTC-4, Richard Damon wrote:
> On 8/15/19 12:05 AM, Rick C wrote:
> > On Wednesday, August 14, 2019 at 11:13:45 PM UTC-4, Richard Damon wrote:
> >> 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.
> >
> > Ok, but the outputs are always a function of the state in any FSM. So it only makes sense to compute them once the state has been updated.
>
> 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.
Two points. First, I think you don't fully understand the purpose of the clock. It is the trigger that causes the inputs and previous state to be evaluated to produce the next state. Once the next state is updated the outputs 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 overkill given that this is purely software.
> >> 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.
> >
> > You are trying to emulate hardware which is not typically done in a software 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 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 state and it's a Mealy FSM, possibly not optimized.
> >
> >
>
> 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.
Not according to Mealy. Although two pages are missing from the copy of his paper where he proves this, he does show that the two models describe equivalent 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 about methods of designing FSMs from a theoretical aspect which he applied to pulsed logic and as an extension of Moore's work also to relay logic. His approach uses a slightly different model which he goes on to show will describe the same FSMs as Moore's model.
The issue of "present" value of inputs only arises when using level sensitive 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 updated. The input at any other time does not show up in any of the methods or diagrams he developed.
In some ways this is like trying to translate an ancient Greek text. It's not only about the words, but the context.
> >> The Moore model is much simpler as everything is clock, so we never need
> >> the extra cycle to propagate the changes.
> >
> > Not sure what extra cycle you mean. If you are talking hardware or HDL, then 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 that directly because they aren't really trying to emulate the async path through logic separate from the clocked "registers".
> >
>
> 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.
Sorry, but there was nothing in either paper that mandated the use of clocks. 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 effect of the clock is a result of invoking the routine that performs the logic 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 frozen while running the routine, it is as if the inputs are also registered.
> >>> 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.
> >
> > That is exactly my point. When coding an FSM in software, everything is computed in a subroutine and everything in essence is registered, state and outputs. So the distinction between Mealy and Moore becomes moot.
>
> And the fact that you think the difference is moot, is a good indication
> that you no longer have Mealy and Moore machines.
I think you don't appreciate that the two FSM models describe equivalent logic.
> >>> 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.
> >
> > Yes, and my point is no one does. Yet, you can still use the Mealy model 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 identical.
> >
> > I started thinking about all this when someone was being rather pedantic about what a Mealy FSM is. I realized the only significant difference between the two FSM types was that the Mealy FSM could change outputs at times other than clock edges if the inputs change. Then the state diagram with outputs 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 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 drawings.
> >
> >
> >>>> 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.
> >
> > 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 for them to have handshakes between processes. They are easy to design to create 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 the same value of the input since there are logic delays that can disrupt the logic results around the clock edges. But in software in essence this has been done by passing the input values into a subroutine. At that point the inputs have been registered in effect.
> >
>
> 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.
No, that is a red herring as a clock equivalent is inherent when invoking the routine that performs the computations.
> 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.
Again, Mealy and Moore FSM are not specific to CLOCKed sequential logic. So please stop tossing red herrings in the path of the dogs.
> 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.
Of course you can update the variables in the program any way you wish. The state is only an input to the next iteration of the routine and the outputs are only available when the routine exits.
> 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.
Not sure why you toss this into the mix. The issues of Mealy and Moore FSM have nothing to do with clocks whatsoever.
> 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.
I'm not saying the terms Mealy and Moore FSM don't have definitions. I'm saying 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 potential 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 clock.
I wish those two pages weren't missing from Mealy's paper. That is where he 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
--- Tesla referral code - https://ts.la/richard11209