EDAboard.com | EDAboard.de | EDAboard.co.uk | WTWH Media

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

Ask a question - edaboard.com

elektroda.net NewsGroups Forum Index - VHDL Language - Why differences between Merly-type and Moore-type clock-gate

Goto page 1, 2  Next

Weng Tianxiang
Guest

Fri Aug 09, 2019 10:45 pm   



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

KJ
Guest

Sat Aug 10, 2019 4:45 am   



On Friday, August 9, 2019 at 4:54:45 PM UTC-4, Weng Tianxiang wrote:
Quote:
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

Rick C
Guest

Sat Aug 10, 2019 4:45 am   



On Friday, August 9, 2019 at 11:13:54 PM UTC-4, KJ wrote:
Quote:
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

Weng Tianxiang
Guest

Sat Aug 10, 2019 5:45 am   



On Friday, August 9, 2019 at 8:30:34 PM UTC-7, Rick C wrote:
Quote:
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

Weng Tianxiang
Guest

Sat Aug 10, 2019 6:45 am   



On Friday, August 9, 2019 at 9:13:11 PM UTC-7, Weng Tianxiang wrote:
Quote:
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/

Rick C
Guest

Sat Aug 10, 2019 7:45 am   



On Saturday, August 10, 2019 at 12:13:11 AM UTC-4, Weng Tianxiang wrote:
Quote:
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.


Quote:
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!


Quote:
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

Rick C
Guest

Sat Aug 10, 2019 3:45 pm   



On Saturday, August 10, 2019 at 10:09:25 AM UTC-4, KJ wrote:
Quote:
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.


Quote:
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

Rick C
Guest

Sat Aug 10, 2019 3:45 pm   



On Saturday, August 10, 2019 at 9:47:41 AM UTC-4, KJ wrote:
Quote:
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.


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


Quote:
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

KJ
Guest

Sat Aug 10, 2019 3:45 pm   



On Saturday, August 10, 2019 at 12:13:11 AM UTC-4, Weng Tianxiang wrote:
Quote:
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

KJ
Guest

Sat Aug 10, 2019 3:45 pm   



On Friday, August 9, 2019 at 11:30:34 PM UTC-4, Rick C wrote:
Quote:
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.

Quote:


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

KJ
Guest

Sat Aug 10, 2019 5:45 pm   



On Saturday, August 10, 2019 at 10:19:11 AM UTC-4, Rick C wrote:
Quote:
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.
Quote:

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.

Quote:

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

Quote:

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

Rick C
Guest

Sat Aug 10, 2019 6:45 pm   



On Saturday, August 10, 2019 at 12:34:19 PM UTC-4, KJ wrote:
Quote:
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

KJ
Guest

Sat Aug 10, 2019 8:45 pm   



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.

Quote:

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

Charles Bailey
Guest

Sat Aug 10, 2019 9:45 pm   



On 2019-08-10 08:47, KJ wrote:
Quote:

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

Rick C
Guest

Sat Aug 10, 2019 9:45 pm   



On Saturday, August 10, 2019 at 3:21:26 PM UTC-4, KJ wrote:
Quote:

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

Goto page 1, 2  Next

elektroda.net NewsGroups Forum Index - VHDL Language - Why differences between Merly-type and Moore-type clock-gate

Ask a question - edaboard.com

Arabic version Bulgarian version Catalan version Czech version Danish version German version Greek version English version Spanish version Finnish version French version Hindi version Croatian version Indonesian version Italian version Hebrew version Japanese version Korean version Lithuanian version Latvian version Dutch version Norwegian version Polish version Portuguese version Romanian version Russian version Slovak version Slovenian version Serbian version Swedish version Tagalog version Ukrainian version Vietnamese version Chinese version Turkish version
EDAboard.com map