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

W

Weng Tianxiang

Guest
Why differences between Merly-type and Moore-type clock-gated state machines are important on how to stop clocking?

I need help to understand a puzzle:

Merly-type state machine generates outputs which depend on inputs to the state machine and the current states of the state machine, while Moore-type state machine generates outputs which depend only on the current states of the state machine.
Am I right if I treat a Merly-type state machine as a Moore-type state machine plus an independent combinational logic which has the same inputs to the state machine and the Moore-type state machine's state outputs?
If I am right, why the paper "Automatic synthesis of lower power gated-clock finite state machine"
https://si2.epfl.ch/~demichel/publications/archive/1996/CADICSvol15iss6Jun96pg630.pdf
says (p.632, 2nd column, last section) "The knowledge of the state and the input is not sufficient to individuate the conditions when the clock can be stopped."

Thank you.

Weng
 
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
Why differences between Merly-type and Moore-type clock-gated state machines are important on how to stop clocking?

I need help to understand a puzzle:

Merly-type state machine generates outputs which depend on inputs to the state machine and the current states of the state machine, while Moore-type state machine generates outputs which depend only on the current states of the state machine.
Am I right if I treat a Merly-type state machine as a Moore-type state machine plus an independent combinational logic which has the same inputs to the state machine and the Moore-type state machine's state outputs?
If I am right, why the paper "Automatic synthesis of lower power gated-clock finite state machine"
https://si2.epfl.ch/~demichel/publications/archive/1996/CADICSvol15iss6Jun96pg630.pdf
says (p.632, 2nd column, last section) "The knowledge of the state and the input is not sufficient to individuate the conditions when the clock can be stopped."

Thank you.

Weng

The writer states their reason a couple of sentences later which I quote "The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock". The writer then goes on to refer to an Example 1 and concludes "Unfortunately, we do not have any way to know is the output value in the current clock cycle (it could be either 10 or -1".

I'm not interested enough to read anymore of this but the writer's Figure 1 does not represent a Mealy state machine. The inputs get registered and then it goes into logic. However, the definition of a Mealy state machine is "a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs."...current inputs...not input delayed by a clock cycle.

So in the writer's example, he is correct that for Figure 1, clock gating wouldn't work, the outputs would not be correct because the registers on the inputs would be blocked from reaching the output computation logic. The writer's flaw is that Figure 1 is not a Mealy state machine so that any conclusions he draws from Figure 1 do not apply to a Mealy state machine. Figure 1 may be considered a Luca Benini and Giovanni De Micheli state machine....but not a Mealy state machine.

But of course the usefulness of understanding a Benini/De Micheli state machine is about the same as understanding Mealy and Moore state machine (hint: only important if you're trying to publish some garbage about such a topic, but not important if you do any design).

Kevin Jennings
 
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
Why differences between Merly-type and Moore-type clock-gated state machines are important on how to stop clocking?

I need help to understand a puzzle:

Merly-type state machine generates outputs which depend on inputs to the state machine and the current states of the state machine, while Moore-type state machine generates outputs which depend only on the current states of the state machine.
Am I right if I treat a Merly-type state machine as a Moore-type state machine plus an independent combinational logic which has the same inputs to the state machine and the Moore-type state machine's state outputs?
If I am right, why the paper "Automatic synthesis of lower power gated-clock finite state machine"
https://si2.epfl.ch/~demichel/publications/archive/1996/CADICSvol15iss6Jun96pg630.pdf
says (p.632, 2nd column, last section) "The knowledge of the state and the input is not sufficient to individuate the conditions when the clock can be stopped."

Thank you.

Weng

The writer states their reason a couple of sentences later which I quote "The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock". The writer then goes on to refer to an Example 1 and concludes "Unfortunately, we do not have any way to know is the output value in the current clock cycle (it could be either 10 or -1".

I'm not interested enough to read anymore of this but the writer's Figure 1 does not represent a Mealy state machine. The inputs get registered and then it goes into logic. However, the definition of a Mealy state machine is "a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs."...current inputs....not input delayed by a clock cycle.

That was my point in reply to this post in another group... sort of. My point was that the definition is not clear. Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic. I don't see the inclusion of input registers to be a problem. If you look at any state machine diagram for a Mealy FSM, you will find the outputs are specified on the transitions while the outputs of a Moore FSM are specified on the states. The transitions don't happen until the clock edge, so it makes sense the outputs don't change until then either.


> So in the writer's example, he is correct that for Figure 1, clock gating wouldn't work, the outputs would not be correct because the registers on the inputs would be blocked from reaching the output computation logic. The writer's flaw is that Figure 1 is not a Mealy state machine so that any conclusions he draws from Figure 1 do not apply to a Mealy state machine. Figure 1 may be considered a Luca Benini and Giovanni De Micheli state machine...but not a Mealy state machine.

Clock gating can work if you don't disable the inputs based on the state changes. The input registers should be enabled based on the inputs changing.


> But of course the usefulness of understanding a Benini/De Micheli state machine is about the same as understanding Mealy and Moore state machine (hint: only important if you're trying to publish some garbage about such a topic, but not important if you do any design).

"Garbage" is a loaded word. Clock gating is not trivial and is essential in many devices. I think it is a very important topic.

--

Rick C.

- Get 1,000 miles of free Supercharging
- Tesla referral code - https://ts.la/richard11209
 
On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
Why differences between Merly-type and Moore-type clock-gated state machines are important on how to stop clocking?

I need help to understand a puzzle:

Merly-type state machine generates outputs which depend on inputs to the state machine and the current states of the state machine, while Moore-type state machine generates outputs which depend only on the current states of the state machine.
Am I right if I treat a Merly-type state machine as a Moore-type state machine plus an independent combinational logic which has the same inputs to the state machine and the Moore-type state machine's state outputs?
If I am right, why the paper "Automatic synthesis of lower power gated-clock finite state machine"
https://si2.epfl.ch/~demichel/publications/archive/1996/CADICSvol15iss6Jun96pg630.pdf
says (p.632, 2nd column, last section) "The knowledge of the state and the input is not sufficient to individuate the conditions when the clock can be stopped."

Thank you.

Weng

The writer states their reason a couple of sentences later which I quote "The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock". The writer then goes on to refer to an Example 1 and concludes "Unfortunately, we do not have any way to know is the output value in the current clock cycle (it could be either 10 or -1".

I'm not interested enough to read anymore of this but the writer's Figure 1 does not represent a Mealy state machine. The inputs get registered and then it goes into logic. However, the definition of a Mealy state machine is "a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs."...current inputs...not input delayed by a clock cycle.

That was my point in reply to this post in another group... sort of. My point was that the definition is not clear. Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic. I don't see the inclusion of input registers to be a problem. If you look at any state machine diagram for a Mealy FSM, you will find the outputs are specified on the transitions while the outputs of a Moore FSM are specified on the states. The transitions don't happen until the clock edge, so it makes sense the outputs don't change until then either.


So in the writer's example, he is correct that for Figure 1, clock gating wouldn't work, the outputs would not be correct because the registers on the inputs would be blocked from reaching the output computation logic. The writer's flaw is that Figure 1 is not a Mealy state machine so that any conclusions he draws from Figure 1 do not apply to a Mealy state machine. Figure 1 may be considered a Luca Benini and Giovanni De Micheli state machine...but not a Mealy state machine.

Clock gating can work if you don't disable the inputs based on the state changes. The input registers should be enabled based on the inputs changing.


But of course the usefulness of understanding a Benini/De Micheli state machine is about the same as understanding Mealy and Moore state machine (hint: only important if you're trying to publish some garbage about such a topic, but not important if you do any design).

"Garbage" is a loaded word. Clock gating is not trivial and is essential in many devices. I think it is a very important topic.

--

Rick C.

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

Rick,

>Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic.

I never do it! All my projects are assumed to work in a global synchronous system so that outputs from one unit become inputs of next unit without any additional registers inserted between them. And any race conditions are expected to exist only on the boundary between 2 asynchronous systems.

Actually I never pay any attention to whether my state machine is a Merly-type state machine or a Moore-type state machine and I am never worried about whether the inputs are registered or not.

KC or Rick, can you list a code example showing that the paper following view is justified:

"The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock."

I fully agree with Rick's following idea:

>Finally, I would submit it is very easy to determine if a FF should be clocked or not. Simply compare the D input to the Q output. If they are the same, gate the clock. If they are different enable the clock. BTW, this effectively turns the D FF into a toggle FF.

Both your comments are very appreciated.

Thank you.

Weng
 
On Friday, August 9, 2019 at 9:13:11 PM UTC-7, Weng Tianxiang wrote:
On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
Why differences between Merly-type and Moore-type clock-gated state machines are important on how to stop clocking?

I need help to understand a puzzle:

Merly-type state machine generates outputs which depend on inputs to the state machine and the current states of the state machine, while Moore-type state machine generates outputs which depend only on the current states of the state machine.
Am I right if I treat a Merly-type state machine as a Moore-type state machine plus an independent combinational logic which has the same inputs to the state machine and the Moore-type state machine's state outputs?
If I am right, why the paper "Automatic synthesis of lower power gated-clock finite state machine"
https://si2.epfl.ch/~demichel/publications/archive/1996/CADICSvol15iss6Jun96pg630.pdf
says (p.632, 2nd column, last section) "The knowledge of the state and the input is not sufficient to individuate the conditions when the clock can be stopped."

Thank you.

Weng

The writer states their reason a couple of sentences later which I quote "The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock". The writer then goes on to refer to an Example 1 and concludes "Unfortunately, we do not have any way to know is the output value in the current clock cycle (it could be either 10 or -1".

I'm not interested enough to read anymore of this but the writer's Figure 1 does not represent a Mealy state machine. The inputs get registered and then it goes into logic. However, the definition of a Mealy state machine is "a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs."...current inputs...not input delayed by a clock cycle.

That was my point in reply to this post in another group... sort of. My point was that the definition is not clear. Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic. I don't see the inclusion of input registers to be a problem. If you look at any state machine diagram for a Mealy FSM, you will find the outputs are specified on the transitions while the outputs of a Moore FSM are specified on the states. The transitions don't happen until the clock edge, so it makes sense the outputs don't change until then either.


So in the writer's example, he is correct that for Figure 1, clock gating wouldn't work, the outputs would not be correct because the registers on the inputs would be blocked from reaching the output computation logic. The writer's flaw is that Figure 1 is not a Mealy state machine so that any conclusions he draws from Figure 1 do not apply to a Mealy state machine. Figure 1 may be considered a Luca Benini and Giovanni De Micheli state machine...but not a Mealy state machine.

Clock gating can work if you don't disable the inputs based on the state changes. The input registers should be enabled based on the inputs changing.


But of course the usefulness of understanding a Benini/De Micheli state machine is about the same as understanding Mealy and Moore state machine (hint: only important if you're trying to publish some garbage about such a topic, but not important if you do any design).

"Garbage" is a loaded word. Clock gating is not trivial and is essential in many devices. I think it is a very important topic.

--

Rick C.

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

Rick,

Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic.

I never do it! All my projects are assumed to work in a global synchronous system so that outputs from one unit become inputs of next unit without any additional registers inserted between them. And any race conditions are expected to exist only on the boundary between 2 asynchronous systems.

Actually I never pay any attention to whether my state machine is a Merly-type state machine or a Moore-type state machine and I am never worried about whether the inputs are registered or not.

KC or Rick, can you list a code example showing that the paper following view is justified:

"The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock."

I fully agree with Rick's following idea:

Finally, I would submit it is very easy to determine if a FF should be clocked or not. Simply compare the D input to the Q output. If they are the same, gate the clock. If they are different enable the clock. BTW, this effectively turns the D FF into a toggle FF.

Both your comments are very appreciated.

Thank you.

Weng

I published the same topic in 3 places, please refer to:
https://www.reddit.com/r/FPGA/comments/co8aw5/why_differences_between_merlytype_and_mooretype/
 
On Saturday, August 10, 2019 at 12:13:11 AM UTC-4, Weng Tianxiang wrote:
On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
Why differences between Merly-type and Moore-type clock-gated state machines are important on how to stop clocking?

I need help to understand a puzzle:

Merly-type state machine generates outputs which depend on inputs to the state machine and the current states of the state machine, while Moore-type state machine generates outputs which depend only on the current states of the state machine.
Am I right if I treat a Merly-type state machine as a Moore-type state machine plus an independent combinational logic which has the same inputs to the state machine and the Moore-type state machine's state outputs?
If I am right, why the paper "Automatic synthesis of lower power gated-clock finite state machine"
https://si2.epfl.ch/~demichel/publications/archive/1996/CADICSvol15iss6Jun96pg630.pdf
says (p.632, 2nd column, last section) "The knowledge of the state and the input is not sufficient to individuate the conditions when the clock can be stopped."

Thank you.

Weng

The writer states their reason a couple of sentences later which I quote "The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock". The writer then goes on to refer to an Example 1 and concludes "Unfortunately, we do not have any way to know is the output value in the current clock cycle (it could be either 10 or -1".

I'm not interested enough to read anymore of this but the writer's Figure 1 does not represent a Mealy state machine. The inputs get registered and then it goes into logic. However, the definition of a Mealy state machine is "a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs."...current inputs...not input delayed by a clock cycle.

That was my point in reply to this post in another group... sort of. My point was that the definition is not clear. Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic. I don't see the inclusion of input registers to be a problem. If you look at any state machine diagram for a Mealy FSM, you will find the outputs are specified on the transitions while the outputs of a Moore FSM are specified on the states. The transitions don't happen until the clock edge, so it makes sense the outputs don't change until then either.


So in the writer's example, he is correct that for Figure 1, clock gating wouldn't work, the outputs would not be correct because the registers on the inputs would be blocked from reaching the output computation logic. The writer's flaw is that Figure 1 is not a Mealy state machine so that any conclusions he draws from Figure 1 do not apply to a Mealy state machine. Figure 1 may be considered a Luca Benini and Giovanni De Micheli state machine...but not a Mealy state machine.

Clock gating can work if you don't disable the inputs based on the state changes. The input registers should be enabled based on the inputs changing.


But of course the usefulness of understanding a Benini/De Micheli state machine is about the same as understanding Mealy and Moore state machine (hint: only important if you're trying to publish some garbage about such a topic, but not important if you do any design).

"Garbage" is a loaded word. Clock gating is not trivial and is essential in many devices. I think it is a very important topic.

--

Rick C.

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

Rick,

Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic.

I never do it! All my projects are assumed to work in a global synchronous system so that outputs from one unit become inputs of next unit without any additional registers inserted between them. And any race conditions are expected to exist only on the boundary between 2 asynchronous systems.

If your inputs come from logic that is on the same clock then those inputs are already registered. Of course you don't need to register them again. Regardless these inputs are registered so the previous analysis applies.


Actually I never pay any attention to whether my state machine is a Merly-type state machine or a Moore-type state machine and I am never worried about whether the inputs are registered or not.

KC or Rick, can you list a code example showing that the paper following view is justified:

"The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock."

I think in my previous post I pointed out that this argument is fallacious. The only reason outputs would change if the state doesn't is if the inputs change in a way that does not change the state, but does change the outputs. In that case, clock the inputs but do not clock the state. Duh!


I fully agree with Rick's following idea:

Finally, I would submit it is very easy to determine if a FF should be clocked or not. Simply compare the D input to the Q output. If they are the same, gate the clock. If they are different enable the clock. BTW, this effectively turns the D FF into a toggle FF.

Both your comments are very appreciated.

Thank you.

Weng

You are welcome.

--

Rick C.

+ Get 1,000 miles of free Supercharging
+ Tesla referral code - https://ts.la/richard11209
 
On Friday, August 9, 2019 at 11:30:34 PM UTC-4, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
I'm not interested enough to read anymore of this but the writer's Figure 1 does not represent a Mealy state machine. The inputs get registered and then it goes into logic. However, the definition of a Mealy state machine is "a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs."...current inputs...not input delayed by a clock cycle.

That was my point in reply to this post in another group... sort of. My point was that the definition is not clear. Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic.

No, you would only register on async (or alternative clock domain) inputs which would be in the minority of cases.

> I don't see the inclusion of input registers to be a problem. If you look at any state machine diagram for a Mealy FSM, you will find the outputs are specified on the transitions while the outputs of a Moore FSM are specified on the states.

The 'problem' is that adding the input registers changes it from a Mealy FSM to something else. The definition of a Mealy state machine 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" (see https://en.wikipedia.org/wiki/Mealy_machine).

I'm not saying that one wouldn't add input registers if they are needed. I'm saying that doing so changes it to longer be a Mealy state machine since the output is not dependent on the current input. In fact, what those input registers actually do is change it to a Moore state machine which is defined as "This is in contrast to a Moore machine, whose (Moore) output values are determined solely by its current state" (same Wiki reference) because the 'state' would also include those input registers. The output in the writer's Figure 1 are logic based on current state which would include the outputs of those input registers...a Moore state machine.

But of course the usefulness of understanding a Benini/De Micheli state machine is about the same as understanding Mealy and Moore state machine (hint: only important if you're trying to publish some garbage about such a topic, but not important if you do any design).

"Garbage" is a loaded word. Clock gating is not trivial and is essential in many devices. I think it is a very important topic.

Rick C.

The term 'garbage' is referring to publishing stuff on the topic of Mealy and Moore state machines, not clock gating.

Kevin Jennings
 
On Saturday, August 10, 2019 at 12:13:11 AM UTC-4, Weng Tianxiang wrote:
On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:

KC or Rick, can you list a code example showing that the paper following view is justified:

"The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock."

The statement is flat out wrong. In a Mealy, the outputs can change regardless of whether there is a state change and therefore the output can change even if the clock to the state machine stops. That is inherent in the definition (previously referenced) of a Mealy state machine. The writer's statement was in the context of Mealy state machines, therefore it is wrong.

As I previously posted, the writer produced an example that was *claimed* to be a Mealy when in fact it was not because it added registers to the inputs. Claiming something to be true does not in fact make it true. In the writer's example, the output no longer depends on the current input and therefore it is not a Mealy state machine. Those additional registers are in fact additional states. From that viewpoint, when you look at the writer's example it is actually a Moore state machine where the output depends only on current state (which includes those input registers).

With a Moore state machine the clock can be stopped if the inputs are in fact not changing but if they are changing the clock must run as well.

I'll promptly now forget the distinction between Mealy and Moore since there is no value in retaining such knowledge beyond knowing that these concepts exist.
Kevin Jennings
 
On Saturday, August 10, 2019 at 9:47:41 AM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 11:30:34 PM UTC-4, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
I'm not interested enough to read anymore of this but the writer's Figure 1 does not represent a Mealy state machine. The inputs get registered and then it goes into logic. However, the definition of a Mealy state machine is "a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs."...current inputs...not input delayed by a clock cycle.

That was my point in reply to this post in another group... sort of. My point was that the definition is not clear. Virtually everyone registers the inputs to prevent erroneous transitions from race conditions in the combinational logic.

No, you would only register on async (or alternative clock domain) inputs which would be in the minority of cases.

As I explained, the only time you don't need to register the inputs is when they are already registered, i.e. in the same clock domain.


I don't see the inclusion of input registers to be a problem. If you look at any state machine diagram for a Mealy FSM, you will find the outputs are specified on the transitions while the outputs of a Moore FSM are specified on the states.

The 'problem' is that adding the input registers changes it from a Mealy FSM to something else. The definition of a Mealy state machine 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" (see https://en.wikipedia.org/wiki/Mealy_machine).

Fine, but that is a theoretical model that is virtually never built other than in devices like relay operated soda machines... which they likely don't make anymore. Inputs to a clocked FSM will be registered if not already so. Using the unregistered inputs for the output logic creates a mismatch in timing between the outputs and the state.


> I'm not saying that one wouldn't add input registers if they are needed. I'm saying that doing so changes it to longer be a Mealy state machine since the output is not dependent on the current input. In fact, what those input registers actually do is change it to a Moore state machine which is defined as "This is in contrast to a Moore machine, whose (Moore) output values are determined solely by its current state" (same Wiki reference) because the 'state' would also include those input registers. The output in the writer's Figure 1 are logic based on current state which would include the outputs of those input registers...a Moore state machine.

I think people confuse what is meant by "the current input". There is nothing in that statement that indicates the input can not be registered and if you consider the usage and even the diagrams for Mealy machines, you will see the output actually is defined by the input *at the time of the state transition*. The output is noted on the transitions in the state diagram. If the outputs depend on the instantaneous value of the input, the output would change will inputs even when there is no state change which can happen only because the timing did not coincide with a clock edge. The conventional notation of Mealy machines has no way to indicate that for clocked FSM.


But of course the usefulness of understanding a Benini/De Micheli state machine is about the same as understanding Mealy and Moore state machine (hint: only important if you're trying to publish some garbage about such a topic, but not important if you do any design).

"Garbage" is a loaded word. Clock gating is not trivial and is essential in many devices. I think it is a very important topic.

Rick C.

The term 'garbage' is referring to publishing stuff on the topic of Mealy and Moore state machines, not clock gating.

Yes, that was obvious.

--

Rick C.

-- Get 1,000 miles of free Supercharging
-- Tesla referral code - https://ts.la/richard11209
 
On Saturday, August 10, 2019 at 10:09:25 AM UTC-4, KJ wrote:
On Saturday, August 10, 2019 at 12:13:11 AM UTC-4, Weng Tianxiang wrote:
On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:

KC or Rick, can you list a code example showing that the paper following view is justified:

"The important consequence is that, even if we know that the state is not going to change, we cannot guarantee that the output will remain constant as well, and therefore we cannot safely stop the clock."


The statement is flat out wrong. In a Mealy, the outputs can change regardless of whether there is a state change and therefore the output can change even if the clock to the state machine stops. That is inherent in the definition (previously referenced) of a Mealy state machine. The writer's statement was in the context of Mealy state machines, therefore it is wrong.

I can logically prove you are not seeing this correctly. If a Mealy FSM is intended to have outputs change from changes in inputs when there is no clock input (regardless of whether it is because of timing or the absence of a clock) there is no way it could be equivalent to a Moore FSM in a clocked FSM design.

There are any number of proofs available that will show you how to convert any Mealy FSM to a Moore FSM. Ergo the Mealy outputs must only change when clocked. Registering the inputs accomplishes this and precludes the problem you describe of outputs changing between clocks.


> As I previously posted, the writer produced an example that was *claimed* to be a Mealy when in fact it was not because it added registers to the inputs. Claiming something to be true does not in fact make it true. In the writer's example, the output no longer depends on the current input and therefore it is not a Mealy state machine. Those additional registers are in fact additional states. From that viewpoint, when you look at the writer's example it is actually a Moore state machine where the output depends only on current state (which includes those input registers).

Registering inputs does not preclude the designation of it being a Mealy FSM.


With a Moore state machine the clock can be stopped if the inputs are in fact not changing but if they are changing the clock must run as well.

I'll promptly now forget the distinction between Mealy and Moore since there is no value in retaining such knowledge beyond knowing that these concepts exist.

Except that they are equivalent and conversions can be made between any such designs.

--

Rick C.

-+ Get 1,000 miles of free Supercharging
-+ Tesla referral code - https://ts.la/richard11209
 
On Saturday, August 10, 2019 at 10:19:11 AM UTC-4, Rick C wrote:
On Saturday, August 10, 2019 at 10:09:25 AM UTC-4, KJ wrote:
On Saturday, August 10, 2019 at 12:13:11 AM UTC-4, Weng Tianxiang wrote:
On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:

If a Mealy FSM is intended to have outputs change from changes in inputs when there is no clock input (regardless of whether it is because of timing or the absence of a clock) there is no way it could be equivalent to a Moore FSM in a clocked FSM design.

You should re-read the definition of a Mealy state machine.
There are any number of proofs available that will show you how to convert any Mealy FSM to a Moore FSM. Ergo the Mealy outputs must only change when clocked. Registering the inputs accomplishes this and precludes the problem you describe of outputs changing between clocks.

Whether or not one form can be converted to the other is not relevant. Once a state machine is 'converted' from Mealy to Moore it is no longer Mealy even though the two forms are functionally equivalent.

As I previously posted, the writer produced an example that was *claimed* to be a Mealy when in fact it was not because it added registers to the inputs. Claiming something to be true does not in fact make it true. In the writer's example, the output no longer depends on the current input and therefore it is not a Mealy state machine. Those additional registers are in fact additional states. From that viewpoint, when you look at the writer's example it is actually a Moore state machine where the output depends only on current state (which includes those input registers).

Registering inputs does not preclude the designation of it being a Mealy FSM.

Re-read the definition of a Mealy state machine paying attention to the part about 'current inputs'.

With a Moore state machine the clock can be stopped if the inputs are in fact not changing but if they are changing the clock must run as well.

I'll promptly now forget the distinction between Mealy and Moore since there is no value in retaining such knowledge beyond knowing that these concepts exist.

Except that they are equivalent and conversions can be made between any such designs.

Functionally equivalent does not mean the identical.

Kevin Jennings
 
On Saturday, August 10, 2019 at 12:34:19 PM UTC-4, KJ wrote:
On Saturday, August 10, 2019 at 10:19:11 AM UTC-4, Rick C wrote:
On Saturday, August 10, 2019 at 10:09:25 AM UTC-4, KJ wrote:
On Saturday, August 10, 2019 at 12:13:11 AM UTC-4, Weng Tianxiang wrote:
On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:

If a Mealy FSM is intended to have outputs change from changes in inputs when there is no clock input (regardless of whether it is because of timing or the absence of a clock) there is no way it could be equivalent to a Moore FSM in a clocked FSM design.

You should re-read the definition of a Mealy state machine.

There are any number of proofs available that will show you how to convert any Mealy FSM to a Moore FSM. Ergo the Mealy outputs must only change when clocked. Registering the inputs accomplishes this and precludes the problem you describe of outputs changing between clocks.

Whether or not one form can be converted to the other is not relevant. Once a state machine is 'converted' from Mealy to Moore it is no longer Mealy even though the two forms are functionally equivalent.


As I previously posted, the writer produced an example that was *claimed* to be a Mealy when in fact it was not because it added registers to the inputs. Claiming something to be true does not in fact make it true. In the writer's example, the output no longer depends on the current input and therefore it is not a Mealy state machine. Those additional registers are in fact additional states. From that viewpoint, when you look at the writer's example it is actually a Moore state machine where the output depends only on current state (which includes those input registers).

Registering inputs does not preclude the designation of it being a Mealy FSM.


Re-read the definition of a Mealy state machine paying attention to the part about 'current inputs'.


With a Moore state machine the clock can be stopped if the inputs are in fact not changing but if they are changing the clock must run as well.

I'll promptly now forget the distinction between Mealy and Moore since there is no value in retaining such knowledge beyond knowing that these concepts exist.

Except that they are equivalent and conversions can be made between any such designs.


Functionally equivalent does not mean the identical.

This issue is entirely about what is meant by "current" input. You seem to think this requires purely combinational logic between the inputs and outputs. I don't see that the word "current" requires that. "Current" can easily mean the input present at the time of the clock in a design that is clocked since that is the nature of "time" in a synchronous system. By the same argument I could reject the use of combinational logic since the output is rather delayed from the input and so is not always reflecting the state of the inputs. The issue of the conversion of a Mealy FSM to a Moore FSM is that they are equivalent. That is mathematically proven and shown in many text books. How could that be if there are fundamental differences in the logic?

I know nothing I say will matter to you. I believe we have had similar conversations before. You toss my argument by sticking to an unsupportable position on the definition of "current". I give what is essentially a mathematical proof and you reject that as somehow not being relevant. Ok. I can't do any more if you reject the facts.

--

Rick C.

+- Get 1,000 miles of free Supercharging
+- Tesla referral code - https://ts.la/richard11209
 
On Saturday, August 10, 2019 at 12:47:21 PM UTC-4, Rick C wrote:

> This issue is entirely about what is meant by "current" input. You seem to think this requires purely combinational logic between the inputs and outputs.

Find and read the definition of a Mealy state machine...there is no 'issue' about what is meant by 'current'. But feel free to research that word as well.

> "Current" can easily mean the input present at the time of the clock in a design that is clocked since that is the nature of "time" in a synchronous system.

The OP topic was about a Mealy state machine. Try to stay on topic. Find and read the definition of a Mealy state machine. Read the paper that Weng was questioning.

> The issue of the conversion of a Mealy FSM to a Moore FSM is that they are equivalent.

Conversion is not the 'issue', the OP posed a question based on a statement from the author regarding Mealy state machines. You keep taking the tangents.

> That is mathematically proven and shown in many text books. How could that be if there are fundamental differences in the logic?

I never said that there were functional differences. The conversion between Mealy and Moore just isn't relevant to what the OP questioned. You are on that tangent, not me.

I know nothing I say will matter to you. I believe we have had similar conversations before. You toss my argument by sticking to an unsupportable position on the definition of "current".

I stayed on topic, you veer off in other directions. I used accepted definitions of Mealy/Moore and posted my reference. You on the other hand just make off-topic comments and you do not post any supporting references...but that's your choice, that's the way you have rolled in the past and are doing so again.

> I give what is essentially a mathematical proof and you reject that as somehow not being relevant. Ok. I can't do any more if you reject the facts..

HAHAHAHAHA...you gave no proof of anything. Maybe you should research what would go into a proof. My point with you is that your postings about being able to convert between Mealy and Moore are not relevant to Weng's question about a comment that a student writer made 23 years ago in a section of a paper that was discussing a Mealy state machine.

Anyway, I'm done with your off topic tangents on this thread. Til we clash (or agree) again...we sometimes do agree.

Kevin
 
On Saturday, August 10, 2019 at 3:21:26 PM UTC-4, KJ wrote:
HAHAHAHAHA...you gave no proof of anything. Maybe you should research what would go into a proof. My point with you is that your postings about being able to convert between Mealy and Moore are not relevant to Weng's question about a comment that a student writer made 23 years ago in a section of a paper that was discussing a Mealy state machine.

Anyway, I'm done with your off topic tangents on this thread. Til we clash (or agree) again...we sometimes do agree.

Kevin

Yes, this is exactly what I expected. You reject the entire community.

You say it is irrelevant if the two types of FSM equivalent and yet you then try to they aren't. Obviously it is relevant because you are concerned about the issue. Look it up. Any Mealy FSM can be represented by an equivalent Moore FSM. If the outputs of a Mealy FSM could change without being clocked that would not be true.

QED

OK, that should be enough to convince anyone but the most stubborn, fact denialist.

--

Rick C.

++ Get 1,000 miles of free Supercharging
++ Tesla referral code - https://ts.la/richard11209
 
On 2019-08-10 08:47, KJ wrote:
The 'problem' is that adding the input registers changes it from a Mealy FSM to something else. The definition of a Mealy state machine 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" (see https://en.wikipedia.org/wiki/Mealy_machine).

I'm not saying that one wouldn't add input registers if they are needed. I'm saying that doing so changes it to longer be a Mealy state machine since the output is not dependent on the current input. In fact, what those input registers actually do is change it to a Moore state machine which is defined as "This is in contrast to a Moore machine, whose (Moore) output values are determined solely by its current state" (same Wiki reference) because the 'state' would also include those input registers. The output in the writer's Figure 1 are logic based on current state which would include the outputs of those input registers...a Moore state machine.
I agree. "Current" means "right now", not at some previous time. If we
register the inputs then we have a state machine that would be defined
as "An FSM whose output values are determined both by its current state
and the input values from the previous clock cycle." Of course if you
redraw the boundaries of what is included in "the machine" so that its
inputs are now defined to be the outputs from the input latches then
this redrawn machine once again becomes a Mealy machine.

Charles Bailey
 
On Saturday, August 10, 2019 at 4:23:53 PM UTC-4, Charles Bailey wrote:
On 2019-08-10 08:47, KJ wrote:

The 'problem' is that adding the input registers changes it from a Mealy FSM to something else. The definition of a Mealy state machine 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" (see https://en.wikipedia.org/wiki/Mealy_machine).

I'm not saying that one wouldn't add input registers if they are needed.. I'm saying that doing so changes it to longer be a Mealy state machine since the output is not dependent on the current input. In fact, what those input registers actually do is change it to a Moore state machine which is defined as "This is in contrast to a Moore machine, whose (Moore) output values are determined solely by its current state" (same Wiki reference) because the 'state' would also include those input registers. The output in the writer's Figure 1 are logic based on current state which would include the outputs of those input registers...a Moore state machine.

I agree. "Current" means "right now", not at some previous time. If we
register the inputs then we have a state machine that would be defined
as "An FSM whose output values are determined both by its current state
and the input values from the previous clock cycle." Of course if you
redraw the boundaries of what is included in "the machine" so that its
inputs are now defined to be the outputs from the input latches then
this redrawn machine once again becomes a Mealy machine.

I did a bit of reading and I did find sources that literally say the outputs change other than at the clock cycles. But that is not terribly important since in the sort of applications the OP is considering there are no inputs that are truly asynchronous. Even if an input is from another clock domain or is input to the device and so asynchronous, it will be synchronized with the FSM clock and so no longer async and this synchronized signal is the input to the FSM.

Probably more significant is the fact that it is not important to the discussion. The authors are talking about gating the clock to FSMs to save power. The state registers in a Mealy FSM work the same as the registers in a Moore FSM. So they incorrectly conclude something different must be done in a Mealy machine. I don't get why a simple XOR gate with inputs from the Q and D signals on the FF can't be used?

It doesn't matter what you call the FSM. In virtually all digital logic the inputs will be operating in the same clock domain by the time they reach the state machine. I think the authors' bigger error is faulty thinking of how clocks can be gated. They also calculate "improvement" very oddly, the delta divided by the lower power so it can be more than 100%. Go figure....

--

Rick C.

--- Get 1,000 miles of free Supercharging
--- Tesla referral code - https://ts.la/richard11209
 
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.

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'

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.

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


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.


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.

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.

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.


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.

--+ Get 1,000 miles of free Supercharging
--+ Tesla referral code - https://ts.la/richard11209
 
On Saturday, August 10, 2019 at 5:47:35 PM UTC-7, 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.

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'

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.

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.

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.

Weng
 
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
 

Welcome to EDABoard.com

Sponsor

Back
Top