Why differences between Merly-type and Moore-type clock-gate

[Weng Tianxiang]

On Sunday, August 11, 2019 at 1:56:47 PM UTC-7, Rick C wrote:

On Sunday, August 11, 2019 at 4:01:22 PM UTC-4, Weng Tianxiang wrote:
On Saturday, August 10, 2019 at 5:47:35 PM UTC-7, Richard Damon wrote:

Richard,
With the classic definition, the distinction between a machine defined by the Mealy method (ON THE ARCS) or the Moore method (on the states)

My explanation for (ON THE ARCS) is that the input is STABLE ONLY ON the edge (setup time plus hold time), not because an output is registered by a register.

The problem is everyone has their own interpretation of what a Mealy machine is. So in the end "it means just what I choose it to mean—neither more nor less." Apologies to Lewis Carrol. Discussing FSM always seems to end up in Humpty Dumpty speak.

--

Rick C.

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

Sorry to everyone who joined the discussion posted by me.

Finally I find that the concept of Mealy and Moore state machine is a garbage, useless and should have no value in all modern circuit designs, worth nothing to discuss it.

Weng

 

[KJ]

On Saturday, August 10, 2019 at 8:47:35 PM UTC-4, Richard Damon wrote:

I think a big problem with this discussion is there seems to be two
different definition of the Mealy machine.

Good post, but there is really only one definition: Mealy, George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. pp. 1045–1079.

For those without access to the definitive source, Wikipedia presents their definition at https://en.wikipedia.org/wiki/Mealy_machine which is:
In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs.

Other 'definitions' are actually just other people's statements. To the extent that those statements actually exactly match with the definition from the definitive source, those opinions can be considered alternate definitions. However, if the statements don't match the definition, then they are just statements...or possibly 'incorrect definitions', but that seems like a worthless title.

Might seem pedantic, but many people post stuff trying to state something as fact when it is not since it has no documented basis...in other words it just their words, not fact. That's my reason for my believing "You can't believe everything you read on the internet".

Kevin

 

[Richard Damon]

On 8/10/19 9:48 PM, Rick C wrote:

On Saturday, August 10, 2019 at 8:47:35 PM UTC-4, Richard Damon wrote:
I think a big problem with this discussion is there seems to be two
different definition of the Mealy machine.

What I learned was that, given input I, and state S, and output O that a
Moore machine had the description: (S' indicates S on next clock, f & g
are pure combinatorial functions)

S' = f(S, I)
O = g(S)

and a Mealy machine was

S' = f(S, I)
O = g(S, I)

Note that in both cases, O is a pure combinatorial function of some signals.

On the state diagram, the Moore machine puts the output values on the
states, and the Mealy puts them on the arcs.

It seems, some want to define Mealy as instead,

O' = g(S, I)

i.e, the outputs specified doesn't happen until the clock that updates
the state, i.e. the arcs aren't specifying the CURRENT output, but the
NEXT output.

That's not really the issue. I don't think anyone is suggesting the outputs must be registered in a Mealy machine. If I said that, I was mistaken. The issue at hand is whether the inputs change between state transitions in useful systems.

Inputs always change some point after the clock, if fully synchronized,
it will be one Clk->Q delay.

With a Mealy Machine, the output O will change Tpd after the input
change, and thus will be available to later logic on the same clock cycle.

Note, the proper interpretation of the state table for a state machine
is that it lists CURRENT state, CURRENT input, CURRENT output, and NEXT
state, so that on the clock you move the next state to the current state.

A key factor that this definition defies is that in the classic
definition, you can determine how much 'state' is in the system by the
size of S (and how you encode it) and that determines how many registers
you need. This modified definition effectively has added 1 bit of state
for every output, and of course for that definition, you can always
convert it, as you are just playing name games of which bits are 'state'
and which are 'output'

I don't know about 1 bit of state for every bit of output. But yes, that is why you can convert a Mealy FSM into a Moore FSM, they are be equivalent. But this is only valid if the inputs and outputs are considered at the clocking points.

But you CAN'T. Please show me how to convert the following machine from
Mealy to Moore. It has a simple implementation of a single flip flop,
and the output is the xor of the input and the output (with NO flip flop
after it)

State Input Output State-Next
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 1

(Poor attempt to draw the diagram for this)

1/1
/------------------\|/----\
| 0/0 ^ v |
| 0 1 | 1/0
| ^ 0/1 v |
\-----/|\-----------------/

I have seen documents talking about the 'Moore Equivalent', but they are
NOT identical machines, because the Moore Equivalent to the Mealy
Machine adds a needed clock cycle of delay.

With the classic definition, the distinction between a machine defined
by the Mealy method (on the arcs) or the Moore method (on the states) in
that there are a number of basic properties that can be easily
determined for Moore machines, as they are relatively isolated from each
other, and thus you can compute the speed of a system of Moore machines
only needing to deal with a given machine and the machines that feed it.
With the Mealy machine, because of the 'shoot through' of signals, you
need to look at much more of the system.

If you are coupling FSMs, this "shoot through" you mentions is really inputs to the second Mealy FSM for some odd reason being run through logic of the first Mealy FSM. If you were to move any of those output logic functions to the second machine both machines could be made Moore with no other changes... well, if you ignore the async logic feeding outputs of the second Mealy FSM, lol. But that logic is just logic and can easily be elsewhere.

The inputs of the second FSM are the output of the first FSM. The may
well depend on the state of the first FSM (as well as its inputs if it
is Mealy). Since it can be dependent on the State of the first machine,
it can't just be moved to the second machine. (You could combine them
into a single bigger more complicated FSM).

I'm not trying to mess with anyone here. I'm just batting this around in my brain. In reality the attachments of outputs to transitions in a Mealy FSM graph makes no sense unless the output is accompanied by a state transition. If the state transition is not required to change outputs in a Mealy machine, that type of directed graph and in fact any that I have seen does not properly represent a Mealy FSM with inputs changing without state transitions and impacting the outputs at times other than state transitions.

Let us look at two simple state machines, the first defined as a Moore
machine, the second as a Mealy machine.

Both have states a, b, c, and d, and output O, and in input I, S'(0) is
the next state for I = 0, S'(1) is the next state if I = 1, similarly
for the Mealy

Moore Machine

S O S'(0) S'(1)
a 0 a b
b 0 a c
c 1 d c
d 1 a c

This is the description of a simple debouncer, the output follows the
input, but a single cycle change of the input gets ignored.

Mealy Machine

S S'(0) O(0) S'(1) O(1)
a a 0 b 0
b a 0 c 1
c d 1 c 1
d a 0 c 1

Note, the states transitions are identical to the above, and the output
is similar to the above, the difference being that with the Moore
Machine, if you had a long series of 0s, then the input goes high, then
on the 1st clock we move to state b, the 2nd clock we move to state c,
and THEN the output changes.

With the second machine, given the same input, on the first clock we
move to state b as above, and THEN the output goes high (since we are in
state b with i=1, and then on the 2nd clock we move to state c, and the
output stays high. This machine generates its output almost a whole
cycle earlier (it may have its output delayed by a bit more propagation
delay.

Mealy machines can of course have output without a state change, as the
arcs can be from the state to itself, and in fact you MUST have such
arrows if you can have input combinations that don't change the state
(like states a and c above). In fact, a Mealy machine, since the arcs
define the output states, must have a complete set of arcs out for ALL
possible combinations of inputs, as you need to define the output for
all conditions. In contrast, a Moore machine might use the definition
that if the inputs don't match any of the provided arcs, the state stays
the same, so you can omit the arcs from a state to itself.

I did some work with async state machines once. An async Mealy FSM can be properly represented by the Mealy FSM graph while a sync Mealy FSM can't.

I am not talking about an asynchronous state machine here (Those are
really neither Mealy or Moore, as the state transitions are not tied to
the clock). Asynchronous machines, where some of the state latches can
change state on certain input changes (not tied to the clock) are a very
different beast and need different tools to analyze.

With Moore machines, you can, by re-encoding the states, convert g(S)
into a simple selection of state bits, and then the output is available
immediately (well, one clk->q delay, the delay ALL signals have) after
the clock, and each machine can be computed totally independent of the
other machines. (assuming a uniform clock in the system, if you have
multiple clock domains, you need to do special analysis to take those
issue into account, which is beyond the theory in Mealy/Moore machines).

Generally, the flip-flops that are needed to synchronize signals not of
the current machines clock domain are NOT considered part of the
machine, as those ffs really need the multi-domain analysis.

Indeed.

 

[Rick C]

On Sunday, August 11, 2019 at 5:47:37 PM UTC-4, Richard Damon wrote:

On 8/10/19 9:48 PM, Rick C wrote:

I don't know about 1 bit of state for every bit of output. But yes, that is why you can convert a Mealy FSM into a Moore FSM, they are be equivalent. But this is only valid if the inputs and outputs are considered at the clocking points.

But you CAN'T. Please show me how to convert the following machine from
Mealy to Moore. It has a simple implementation of a single flip flop,
and the output is the xor of the input and the output (with NO flip flop
after it)

State Input Output State-Next
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 1

(Poor attempt to draw the diagram for this)

1/1
/------------------\|/----\
| 0/0 ^ v |
| 0 1 | 1/0
| ^ 0/1 v |
\-----/|\-----------------/

I have seen documents talking about the 'Moore Equivalent', but they are
NOT identical machines, because the Moore Equivalent to the Mealy
Machine adds a needed clock cycle of delay.

FSM: process (CLK, RST)
begin
if RST then
Q <= '0';
elsif rising_edge(CLK) then
Q <= D;
end if;
end process;

There is the new FSM with the output Q. Then a bit of logic is needed to produce the intended output.

Out <= D xor Q;

I'm sure you will say this is a Mealy FSM. That is fair. But adding a bit of combinational logic to a FSM does not actually make it a new FSM. As Weng has realized, this distinction is without value in "modern" design.

I realized something was amiss when I saw the outputs indicated on the transitions could not represent the outputs of a combinational circuit of the inputs and state.

If you are coupling FSMs, this "shoot through" you mentions is really inputs to the second Mealy FSM for some odd reason being run through logic of the first Mealy FSM. If you were to move any of those output logic functions to the second machine both machines could be made Moore with no other changes... well, if you ignore the async logic feeding outputs of the second Mealy FSM, lol. But that logic is just logic and can easily be elsewhere..

The inputs of the second FSM are the output of the first FSM. The may
well depend on the state of the first FSM (as well as its inputs if it
is Mealy). Since it can be dependent on the State of the first machine,
it can't just be moved to the second machine. (You could combine them
into a single bigger more complicated FSM).

Simply make the required state variables available as outputs.

It can be argued that every set of interacting FSMs is a single FSM. But that is of no value in this discussion.

I'm not trying to mess with anyone here. I'm just batting this around in my brain. In reality the attachments of outputs to transitions in a Mealy FSM graph makes no sense unless the output is accompanied by a state transition. If the state transition is not required to change outputs in a Mealy machine, that type of directed graph and in fact any that I have seen does not properly represent a Mealy FSM with inputs changing without state transitions and impacting the outputs at times other than state transitions.

Let us look at two simple state machines, the first defined as a Moore
machine, the second as a Mealy machine.

<snipped a lot of example and discussion>

I believe we all understand the issues here. What bothers me is the disconnect between the definition of the two types of machines and the notation used to describe them. Mealy himself in his original paper used the notation of assigning outputs to the transitions which can not represent the operation of the Mealy FSM implemented with clocked synchronous logic. On reading the paper I understand why. While he mentions the use of a clock in his definitions of a synchronous circuit, but the circuits he uses have NO CLOCK! They are asynchronous state machines which will change state as soon as the inputs change. In that case it makes sense to say the outputs of a Mealy FSM reflect the "current" state of the inputs as well as being represented by outputs assigned to the state changes.

Bottom line, as Weng has said, there is no real value to the distinction between Mealy and Moore FSM. As others have said, often a given implementation is not either of these two theoretical models.

--

Rick C.

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

 

[Richard Damon]

On 8/11/19 8:01 PM, Rick C wrote:

On Sunday, August 11, 2019 at 5:47:37 PM UTC-4, Richard Damon wrote:
On 8/10/19 9:48 PM, Rick C wrote:

I don't know about 1 bit of state for every bit of output. But yes, that is why you can convert a Mealy FSM into a Moore FSM, they are be equivalent. But this is only valid if the inputs and outputs are considered at the clocking points.

But you CAN'T. Please show me how to convert the following machine from
Mealy to Moore. It has a simple implementation of a single flip flop,
and the output is the xor of the input and the output (with NO flip flop
after it)

State Input Output State-Next
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 1

(Poor attempt to draw the diagram for this)

1/1
/------------------\|/----\
| 0/0 ^ v |
| 0 1 | 1/0
| ^ 0/1 v |
\-----/|\-----------------/

I have seen documents talking about the 'Moore Equivalent', but they are
NOT identical machines, because the Moore Equivalent to the Mealy
Machine adds a needed clock cycle of delay.


FSM: process (CLK, RST)
begin
if RST then
Q <= '0';
elsif rising_edge(CLK) then
Q <= D;
end if;
end process;

There is the new FSM with the output Q. Then a bit of logic is needed to produce the intended output.

Out <= D xor Q;

I'm sure you will say this is a Mealy FSM. That is fair. But adding a bit of combinational logic to a FSM does not actually make it a new FSM. As Weng has realized, this distinction is without value in "modern" design.

I realized something was amiss when I saw the outputs indicated on the transitions could not represent the outputs of a combinational circuit of the inputs and state.

So you are saying you can convert any Mealy machine into a Moore
machine, if it doesn't have to be a Moore machine? That sounds like a FAIL.

Your description is exactly how to describe it as a Mealy machine, you
have a process to compute the next state and output equations that
depend on the state and the inputs, i.e. a Mealy machine.

If you are building a Moore machine, you can do the same thing but the
outputs are only dependent on the state variables, and not the input.
The one difference is that with a Moore machine, it is generally
possible to refactor the machine, so that you move the output
computation so that you compute the 'next output' instead of the
'current output' and then put those into register like the state (and
perhaps by re-encoding the state remove some of the existing state
registers, so the output has just a single clk to out delay. (It may
increase the setup time of the machine, which is the reason you might
not be able to do this). This motion of the output is one thing that can
NOT be done with a Mealy machine.

I don't understand how you can can say that the outputs are not a
combinatorial output of the input and the current state? Is that not
exactly what the truth table provides, it lists all combinations of the
input and the state, and the exact desired output for that combination.

If you are coupling FSMs, this "shoot through" you mentions is really inputs to the second Mealy FSM for some odd reason being run through logic of the first Mealy FSM. If you were to move any of those output logic functions to the second machine both machines could be made Moore with no other changes... well, if you ignore the async logic feeding outputs of the second Mealy FSM, lol. But that logic is just logic and can easily be elsewhere.

The inputs of the second FSM are the output of the first FSM. The may
well depend on the state of the first FSM (as well as its inputs if it
is Mealy). Since it can be dependent on the State of the first machine,
it can't just be moved to the second machine. (You could combine them
into a single bigger more complicated FSM).

Simply make the required state variables available as outputs.

It can be argued that every set of interacting FSMs is a single FSM. But that is of no value in this discussion.

Yes, the full single domain design can be called a single FSM. But large
FSMs are hard to analyze, which is why it helps the understanding to
partition them into smaller interconnected machines. The conceptual load
to analyze such a combination can be significantly less than the system
as a whole. Divorcing the output generation from the state transition
often destroys the encapsulation which was helping to reduce the system
complexity, removing the advantage of partitioning into smaller machines.

I'm not trying to mess with anyone here. I'm just batting this around in my brain. In reality the attachments of outputs to transitions in a Mealy FSM graph makes no sense unless the output is accompanied by a state transition. If the state transition is not required to change outputs in a Mealy machine, that type of directed graph and in fact any that I have seen does not properly represent a Mealy FSM with inputs changing without state transitions and impacting the outputs at times other than state transitions.

Let us look at two simple state machines, the first defined as a Moore
machine, the second as a Mealy machine.

snipped a lot of example and discussion

I believe we all understand the issues here. What bothers me is the disconnect between the definition of the two types of machines and the notation used to describe them. Mealy himself in his original paper used the notation of assigning outputs to the transitions which can not represent the operation of the Mealy FSM implemented with clocked synchronous logic. On reading the paper I understand why. While he mentions the use of a clock in his definitions of a synchronous circuit, but the circuits he uses have NO CLOCK! They are asynchronous state machines which will change state as soon as the inputs change. In that case it makes sense to say the outputs of a Mealy FSM reflect the "current" state of the inputs as well as being represented by outputs assigned to the state changes.

Bottom line, as Weng has said, there is no real value to the distinction between Mealy and Moore FSM. As others have said, often a given implementation is not either of these two theoretical models.

With a quick search, I can't seem to find a free version of the paper,
and I am not feeling the need to pay $35 for an official copy (and it is
old enough that if they didn't renew the copyright I would expect it to
have expired by now, being a 1955 document), so I will go on my
understand from my studies.

I suspect you are misunderstanding the paper. A Mealy machine IS a clock
sequential machine for the States, the states update synchronously on
the system clock. The difference between the Mealy model and the Moore
model is that Mealy built the combinatorial output based on both the
current state and the inputs. As is typical for synchronous systems,
often the registers are not drawn with a clock, as it is implied, ALL
the registers are clocked together, and drawing the clock to all of them
just adds clutter.

The introduction to the paper, that I can find, it clearly refers to the
Moore paper, and talks about extending it, so it clearly is talking
about a synchronous system.

The way to read a Mealy diagram, if you are currently in State S1, with
input I, find the arc leaving S1 that matches the input going to some
state S2 (which might be the same as S1), and be outputing the specifed
output on the arc until the next clock at which point the state will
change to S2, and the output will then change to be based on the arcs
leaving S2 and the then current input. Any change to the input value may
cause a change to the output as you change which arc you are following.
The outputs that other synchronous machines will act on will be based on
the last value of the input prior to the clock arriving. As changes
propogate through the system, the output might change several times
until it stabilizes on its final value. One thing that you do need to be
careful with Mealy machines, is it is possible to accidentally build an
asynchronous latch or an astable network if there is a combitorial loop
in the logic. I thought I remember that such a loop was to be excluded
in a proper Mealy design.

 

[Richard Damon]

On 8/11/19 4:56 PM, Rick C wrote:

On Sunday, August 11, 2019 at 4:01:22 PM UTC-4, Weng Tianxiang wrote:
On Saturday, August 10, 2019 at 5:47:35 PM UTC-7, Richard Damon wrote:

Richard,
With the classic definition, the distinction between a machine defined by the Mealy method (ON THE ARCS) or the Moore method (on the states)

My explanation for (ON THE ARCS) is that the input is STABLE ONLY ON the edge (setup time plus hold time), not because an output is registered by a register.

The problem is everyone has their own interpretation of what a Mealy machine is. So in the end "it means just what I choose it to mean—neither more nor less." Apologies to Lewis Carrol. Discussing FSM always seems to end up in Humpty Dumpty speak.

There is a precise definition of what a Mealy machine is, and it is well
described in the literature. I find no disagreement with that definition
among what I consider reputable sites.

Yes, there ARE people who will misuse the terms either because they
don't know better, or they choose to not care. That doesn't mean the
definition isn't precise. (Just that some people are Wrong).

The essence of the definition is that you state with a set of states S
(with a starting state specified), a set of input values I, and a set of
output values O.

The machine can be described via a pair of mappings, one is the
transition mapping of the combinations of S and I to S to describe the
next state, and another, the output mapping that defines a mapping of S
and I to O to define the output.

The output mapping needs to be run as needed due to a change in S or I,
and the transition mapping is run when it is time to advance the system
to the next state.

Note that the Moore machine can be described similarly, except that the
output mapping is only a mapping of S to O, and as such, a Moore machine
only needs to be evaluated when you want a state update, so much of the
math becomes simpler.

 

[Rick C]

On Friday, August 16, 2019 at 10:30:04 PM UTC-4, Richard Damon wrote:

On 8/11/19 8:01 PM, Rick C wrote:
On Sunday, August 11, 2019 at 5:47:37 PM UTC-4, Richard Damon wrote:
On 8/10/19 9:48 PM, Rick C wrote:

I don't know about 1 bit of state for every bit of output. But yes, that is why you can convert a Mealy FSM into a Moore FSM, they are be equivalent. But this is only valid if the inputs and outputs are considered at the clocking points.

But you CAN'T. Please show me how to convert the following machine from
Mealy to Moore. It has a simple implementation of a single flip flop,
and the output is the xor of the input and the output (with NO flip flop
after it)

State Input Output State-Next
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 1

(Poor attempt to draw the diagram for this)

1/1
/------------------\|/----\
| 0/0 ^ v |
| 0 1 | 1/0
| ^ 0/1 v |
\-----/|\-----------------/

I have seen documents talking about the 'Moore Equivalent', but they are
NOT identical machines, because the Moore Equivalent to the Mealy
Machine adds a needed clock cycle of delay.


FSM: process (CLK, RST)
begin
if RST then
Q <= '0';
elsif rising_edge(CLK) then
Q <= D;
end if;
end process;

There is the new FSM with the output Q. Then a bit of logic is needed to produce the intended output.

Out <= D xor Q;

I'm sure you will say this is a Mealy FSM. That is fair. But adding a bit of combinational logic to a FSM does not actually make it a new FSM. As Weng has realized, this distinction is without value in "modern" design.

I realized something was amiss when I saw the outputs indicated on the transitions could not represent the outputs of a combinational circuit of the inputs and state.



So you are saying you can convert any Mealy machine into a Moore
machine, if it doesn't have to be a Moore machine? That sounds like a FAIL.

Your description is exactly how to describe it as a Mealy machine, you
have a process to compute the next state and output equations that
depend on the state and the inputs, i.e. a Mealy machine.

Just find any text book on the topic and read the section on converting from one type of FSM to the other. What you keep focusing on is the idea that the outputs have to change from input changes which are not at the time of a state change. THAT was not part of Mealy's FSM design method although it is in his description of the FSM.

The trouble is at his time there were no logic types that you could use for the type of FSM where inputs change and not trigger a state change or at least the potential. Everyone focuses on inputs changing the outputs when the state isn't changing because the clock hasn't happened yet. That's not what Mealy was working with.

If you are building a Moore machine, you can do the same thing but the
outputs are only dependent on the state variables, and not the input.
The one difference is that with a Moore machine, it is generally
possible to refactor the machine, so that you move the output
computation so that you compute the 'next output' instead of the
'current output' and then put those into register like the state (and
perhaps by re-encoding the state remove some of the existing state
registers, so the output has just a single clk to out delay. (It may
increase the setup time of the machine, which is the reason you might
not be able to do this). This motion of the output is one thing that can
NOT be done with a Mealy machine.

I don't understand how you can can say that the outputs are not a
combinatorial output of the input and the current state? Is that not
exactly what the truth table provides, it lists all combinations of the
input and the state, and the exact desired output for that combination.

Instead of focusing on that one erroneous aspect of Mealy's FSM description, look at the diagrams he uses for his FSM. They show output specifications on state transitions and ONLY on state transitions. This allows one type of FSM to be morphed into the other.

If you are coupling FSMs, this "shoot through" you mentions is really inputs to the second Mealy FSM for some odd reason being run through logic of the first Mealy FSM. If you were to move any of those output logic functions to the second machine both machines could be made Moore with no other changes... well, if you ignore the async logic feeding outputs of the second Mealy FSM, lol. But that logic is just logic and can easily be elsewhere.

The inputs of the second FSM are the output of the first FSM. The may
well depend on the state of the first FSM (as well as its inputs if it
is Mealy). Since it can be dependent on the State of the first machine,
it can't just be moved to the second machine. (You could combine them
into a single bigger more complicated FSM).

Simply make the required state variables available as outputs.

It can be argued that every set of interacting FSMs is a single FSM. But that is of no value in this discussion.



Yes, the full single domain design can be called a single FSM. But large
FSMs are hard to analyze, which is why it helps the understanding to
partition them into smaller interconnected machines. The conceptual load
to analyze such a combination can be significantly less than the system
as a whole. Divorcing the output generation from the state transition
often destroys the encapsulation which was helping to reduce the system
complexity, removing the advantage of partitioning into smaller machines.

I'm not trying to mess with anyone here. I'm just batting this around in my brain. In reality the attachments of outputs to transitions in a Mealy FSM graph makes no sense unless the output is accompanied by a state transition. If the state transition is not required to change outputs in a Mealy machine, that type of directed graph and in fact any that I have seen does not properly represent a Mealy FSM with inputs changing without state transitions and impacting the outputs at times other than state transitions.

Let us look at two simple state machines, the first defined as a Moore
machine, the second as a Mealy machine.

snipped a lot of example and discussion

I believe we all understand the issues here. What bothers me is the disconnect between the definition of the two types of machines and the notation used to describe them. Mealy himself in his original paper used the notation of assigning outputs to the transitions which can not represent the operation of the Mealy FSM implemented with clocked synchronous logic. On reading the paper I understand why. While he mentions the use of a clock in his definitions of a synchronous circuit, but the circuits he uses have NO CLOCK! They are asynchronous state machines which will change state as soon as the inputs change. In that case it makes sense to say the outputs of a Mealy FSM reflect the "current" state of the inputs as well as being represented by outputs assigned to the state changes.

Bottom line, as Weng has said, there is no real value to the distinction between Mealy and Moore FSM. As others have said, often a given implementation is not either of these two theoretical models.


With a quick search, I can't seem to find a free version of the paper,
and I am not feeling the need to pay $35 for an official copy (and it is
old enough that if they didn't renew the copyright I would expect it to
have expired by now, being a 1955 document), so I will go on my
understand from my studies.

https://archive.org/details/bstj34-5-1045

Unfortunately two pages are missing.

I suspect you are misunderstanding the paper. A Mealy machine IS a clock
sequential machine for the States, the states update synchronously on
the system clock. The difference between the Mealy model and the Moore
model is that Mealy built the combinatorial output based on both the
current state and the inputs. As is typical for synchronous systems,
often the registers are not drawn with a clock, as it is implied, ALL
the registers are clocked together, and drawing the clock to all of them
just adds clutter.

YOU are adding the "clock" to sequential for both types of FSM. Once you omit that you might do better at understanding that both Mealy and Moore's papers were not about the hardware, they are about design methods.

The introduction to the paper, that I can find, it clearly refers to the
Moore paper, and talks about extending it, so it clearly is talking
about a synchronous system.

Synchronous is not the same thing as sequential. A main logic type at the time was relay logic which is asynchronous sequential.

The way to read a Mealy diagram, if you are currently in State S1, with
input I, find the arc leaving S1 that matches the input going to some
state S2 (which might be the same as S1), and be outputing the specifed
output on the arc until the next clock at which point the state will
change to S2, and the output will then change to be based on the arcs
leaving S2 and the then current input. Any change to the input value may
cause a change to the output as you change which arc you are following.
The outputs that other synchronous machines will act on will be based on
the last value of the input prior to the clock arriving. As changes
propogate through the system, the output might change several times
until it stabilizes on its final value. One thing that you do need to be
careful with Mealy machines, is it is possible to accidentally build an
asynchronous latch or an astable network if there is a combitorial loop
in the logic. I thought I remember that such a loop was to be excluded
in a proper Mealy design.

I don't want to discuss this with you in two different forums. I also am not going to let you invent how to read Mealy state diagrams. You can invent anything you want, but don't attribute it to Mealy.

--

Rick C.

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

 

[Rick C]

On Friday, August 16, 2019 at 10:50:32 PM UTC-4, Richard Damon wrote:

On 8/11/19 4:56 PM, Rick C wrote:
On Sunday, August 11, 2019 at 4:01:22 PM UTC-4, Weng Tianxiang wrote:
On Saturday, August 10, 2019 at 5:47:35 PM UTC-7, Richard Damon wrote:

Richard,
With the classic definition, the distinction between a machine defined by the Mealy method (ON THE ARCS) or the Moore method (on the states)

My explanation for (ON THE ARCS) is that the input is STABLE ONLY ON the edge (setup time plus hold time), not because an output is registered by a register.

The problem is everyone has their own interpretation of what a Mealy machine is. So in the end "it means just what I choose it to mean—neither more nor less." Apologies to Lewis Carrol. Discussing FSM always seems to end up in Humpty Dumpty speak.


There is a precise definition of what a Mealy machine is, and it is well
described in the literature. I find no disagreement with that definition
among what I consider reputable sites.

Yes, there ARE people who will misuse the terms either because they
don't know better, or they choose to not care. That doesn't mean the
definition isn't precise. (Just that some people are Wrong).

The essence of the definition is that you state with a set of states S
(with a starting state specified), a set of input values I, and a set of
output values O.

The machine can be described via a pair of mappings, one is the
transition mapping of the combinations of S and I to S to describe the
next state, and another, the output mapping that defines a mapping of S
and I to O to define the output.

The output mapping needs to be run as needed due to a change in S or I,
and the transition mapping is run when it is time to advance the system
to the next state.

Note that the Moore machine can be described similarly, except that the
output mapping is only a mapping of S to O, and as such, a Moore machine
only needs to be evaluated when you want a state update, so much of the
math becomes simpler.

One last time. Yes, Mealy himself defined his FSM model (what he calls a "switching circuit") as having outputs that depend on the "present input combination and the present state". But in his world there was no input separate from the "clock" as it was pulse logic.

So Mealy never said or implied that the outputs would change at any time other than when the state was potentially changing.

When people try to interpret his intent as saying the outputs could change separately from the clock, they are misinterpreting his paper.

If you stop arguing semantics and actually look at the other evidence such as the equivalence of the two types of machines, you will see that Mealy did not invent a unique FSM architecture. Heck, typing into google gives suggested search for "equivalence of mealy and moore machine". Or better, search for "Conversion from Mealy to Moore Machine".

Or better yet, here is a paper with the mathematical proof that for every Moore FSM there is an equivalent Mealy and vice versa.

http://lms.uop.edu.jo/lms/pluginfile.php/35159/mod_resource/content/0/chap08.pdf

Enough?

--

Rick C.

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