Clarification in mealy and moore design using verilog

[Gurumurthy]

HI All

I want verilog code for state machine which detects sequence 0101 with mealy and moore model.
I want to understand what is the difference while writing verilog code and seeing the output in wave form veiwer.

The problem is no book shows the difference.
The difference is in moore-output depents on state and mealy- output depends on state and present input.
I want to understant this with an example in verilog which explore all the points.


here is my try

In both the cases output comes after a clock cycle. What is the mistake in Moore machine? How to correct it.

Moore machine_101---https://www.edaplayground.com/x/NStc

Mealy mahine----https://www.edaplayground.com/x/ptp4

[AK6DN]

HI All

I want verilog code for state machine which detects sequence 0101 with mealy and moore model.
I want to understand what is the difference while writing verilog code and seeing the output in wave form veiwer.

The problem is no book shows the difference.
The difference is in moore-output depents on state and mealy- output depends on state and present input.
I want to understant this with an example in verilog which explore all the points.

Very good writeup here, with examples in verilog ... https://verilogguide.readthedocs.io/en/latest/verilog/fsm.html

[hamster_nz]

The Mealy FSM should show that the sequence is detected one cycle earlier than the Moore FSM.

I am not sure that the Mealy/Moore distinction is very soild distinction outside of acidemia - any FSM can have both registered and unregistered outputs.

[gnuarm]

I'm no expert in Verilog, but I'm not sure that matters.  You have some errors in your logic.  For example, you are using a state machine in the Mealy FSM, but you never reset it!  That's a problem.  Combine it with the fact that your State variable has four values, but your case statement only handles three of them and you can have a hung machine! 

As I said, I'm no expert in Verilog.  I see that you've initialized State to 0 in the initial statement, but I don't know that it will translate into hardware to reset the value of State. 

I also don't see logic to detect the appropriate input string, but I'm not sure what string you are attempting to detect.  In "0101", which value has to be found first?  The Mealy machine code is looking for a '1' first. 

But...  the biggest issue I have with the Mealy machine code, is that it only changes state on a clock, but the output changes state on input changes, which are ignored by the state machine.  I know some people code a Mealy machine this way, but it seldom makes sense in a real application.  If that's what you really mean, I would separate the always blocks for nextstate and outp.  In fact, the value of outp can be written as a simple assignment statement, I believe.  I know I could do that in VHDL, one line.  Then the always block can be a clocked process as in the Moore machine making it more simple as well. 

In both the cases output comes after a clock cycle.

I don't know what you mean by this.  Can you explain more clearly? 

Actually the Moore machine also has a flaw.  It will set the output to '1' on a "101" sequence. 

[gnuarm]

The Mealy FSM should show that the sequence is detected one cycle earlier than the Moore FSM.

I am not sure that the Mealy/Moore distinction is very soild distinction outside of acidemia - any FSM can have both registered and unregistered outputs.

Not just that, I've never found a use for a Mealy machine.  What I typically code is a FSM that suits my needs, without considering if it's Mealy or Moore.  Nearly everything in digital is clocked, so it seldom makes sense to have an async output.  If it does make sense to have an async output, I typically treat that as async logic, separate from the FSM. 

I especially hate the explanations of Mealy vs. Moore FSM that start by defining them as "tuples".  Great stuff for mathematicians, but pretty pointless for engineers.

[SiliconWizard]

I am not sure that the Mealy/Moore distinction is very soild distinction outside of acidemia - any FSM can have both registered and unregistered outputs.

Yeah, the teaching of these is pretty much purely academic, not that this isn't interesting or that it shouldn't be taught as such though. Students are there to learn the fundamentals.
The sad thing is that, very often, courses include them without actually explaining what their core difference is and what possible benefit one or the other could possibly have in practice. So that students end up not having learnt anything, not even fundamental notions.

What can be seen in practice using HDLs are FSMs that are in a single clocked process, and FSMs that are split into 2 or more processes, one of them being clocked and others just dealing with states in a combinatorial fashion. And often people conflate that distinction with Mealy vs Moore, which is not even quite correct.

[ejeffrey]

If you run the Mealy simulator you will see that it actually detects on clock cycle 3.  It also fires on cycle 5 like the Moore.

Both of them are buggy.  The most fundamental problem is that you do not have enough states.  For the Moore state machine you need 5 states: representing that you have matches the last 0, 1, 2, 3, or 4 clock cycles (not counting the current cycle).  Only in the final state is the output high.  The mealy state machine likewise needs 4 states, representing if the previous 0, 1, 2, or 3 clock cycles matched, and then the output is a logical AND of being in the final state and the input matching the 4th bit.

Your two state machines are stylistically different which makes it harder than necessary to compare.  For instance, one uses a reset, the other uses an initial block. One uses a single clocked block, the other uses a combinatoric block to compute the next state and a tiny clocked process to update the state variable. Especially if you want to contrast the different behavior between the two, I would try to make the code look as close to identical as possible, and have the test bench the same as well.

You use an always block for combinatoric logic with an explicit sensitivity list:  "always@(state or inp)"  Don't ever do this in synthesizable code.  Use always @(*).  If you can use System Verilog blocks you can also use always_comb.

I would strongly advice drawing a state diagram, including the initial/idle state on a whiteboard.  Then carefully indicate how each state will be encoded in the register, and what the value of the output will be.  Then write next to each bubble "output = XXX".  For the moore version, that will be a constant.  For the Mealy it can be an expression of the input.

Once you do that, it's very difficult to code it incorrectly.

[ejeffrey]

I especially hate the explanations of Mealy vs. Moore FSM that start by defining them as "tuples".  Great stuff for mathematicians, but pretty pointless for engineers.

I don't get what you don't like about that?  All it says is that a state machine is defined by the possible inputs, possible outputs, initial state, valid states, state transition rule, and the output rule.  What would you say instead?  Do you just not like the word tuple?  Are you upset when someone says "a point in space is described by a tuple of the x, y, and z coordinates?"  Tuple is a pretty standard word in engineering terms to refer to something like this.

[gnuarm]

I especially hate the explanations of Mealy vs. Moore FSM that start by defining them as "tuples".  Great stuff for mathematicians, but pretty pointless for engineers.

I don't get what you don't like about that?  All it says is that a state machine is defined by the possible inputs, possible outputs, initial state, valid states, state transition rule, and the output rule.  What would you say instead?  Do you just not like the word tuple?  Are you upset when someone says "a point in space is described by a tuple of the x, y, and z coordinates?"  Tuple is a pretty standard word in engineering terms to refer to something like this.

I find the mathematical aspect of state machines has virtually nothing to do with using or coding such machines.   It's not the word "tuple".  It's  the point that someone talking about tuples in the context if FSMs, is not useful to an engineer.  Well, not unless they are doing something other than using them.

Please explain to me how the knowledge of the FSM "tuple" is of value?  Your sentence, "a state machine is defined by the possible inputs, possible outputs, initial state, valid states, state transition rule, and the output rule" says everything needed.  No need to use the term "tuple" or drawing symbols that are hard to reproduce and mean nothing when I'm designing with FSMs.

I thought this was pretty clear when I said, "Great stuff for mathematicians, but pretty pointless for engineers."

[Gurumurthy]

Thank you all.

Now i have simulated Moore FSM for detecting 101 sequence and my output changes for 3 rd clock pulse insted of 4 th clock pulse.

what is the error?

link:https://www.edaplayground.com/x/asWh

[gnuarm]

Thank you all.

Now i have simulated Moore FSM for detecting 101 sequence and my output changes for 3 rd clock pulse insted of 4 th clock pulse.

what is the error?

link:https://www.edaplayground.com/x/asWh

Look at your code and the simulation.  One thing I'm not familiar with, is the nature of "simultaneous" events in Verilog.  Your clock has a rising edge every 20 ns, on the 20 ns.  Your assignments to rst and in are every 20 ns, on the 20 ns.  So which happens first, the rising clock edge, or the data changes?  I know how VHDL resolves this, but I have no idea how this is handled in Verilog.  I can't say if this is causing a problem with your simulation or not.  It might be useful to start your assignments with a 5 or 10 ns delay, so they change at 25 ns, 45 ns, etc. and you know exactly what value rst and in will have on any given clock rising edge. 

The code starts in state S0 because of the rst being asserted.  On the next three clocks, the state transitions to S1, S2 and finally S3.  That's only three clocks.  The output, out, is set to 1 when the state is S3.  There is no clock delay for this assignment.  It's not inside the always@ (posedge clk...  So the output will change as soon as the state becomes S3.

Why do you expect it to take four clocks?  Another issue might be, the fact that your original problem statement said it was to detect the sequence "0101".  If the '0' is to be detected first, your state machine is wrong, since it starts in state S0 which waits for a '1' state, without ever seeing a '0' state.  Is this correct?

I always tell people writing HDL, to picture the hardware they are trying to build.  The D in HDL stands for DESCRIPTION.  So describe what that hardware would do.  This is not a C program.

[Gurumurthy]

Thank you all.

This time i have modelled with three always block.
two always block for computing  next state logic and output logic and third always for state transtion on clock edge.

still the sequence 101 is detected with 3 clock edge and not 4.

Rectify my understanding.

here is the link: https://www.edaplayground.com/x/6TsY

[ejeffrey]

The problem is that you are missing states in your diagram.  You need an idle state plus 3 or 4 additional states for tracking the number of previous cycles that have matched.

I would suggest again that you erase all your code and draw the state diagram on a whiteboard.  Then write verilog to implement your drawing.

[gnuarm]

The problem is that you are missing states in your diagram.  You need an idle state plus 3 or 4 additional states for tracking the number of previous cycles that have matched.

I would suggest again that you erase all your code and draw the state diagram on a whiteboard.  Then write verilog to implement your drawing.

 

But I would add a step.  From the state diagram, I would draw a diagram of the logic, showing registers and clouds for logic.  This may seem simple and obvious, but I think it will help construct the HDL since this is what seems to be a problem.

[Gurumurthy]

Thank you all,

Here is logic circuit which does this sequence detection.

The output is  flipflop of both and combined with and gate.

I didnt get why it takes 3 clock cycle and instead of 4 clock cycle.

[ejeffrey]

It's still because you are missing the idle state.  For a N element pattern recognizer you need N+1 states to distinguish 0, 1, .., N matches.  You should be able to step through your diagram with the input "101" and see that it ends up in the state S3.

[Gurumurthy]

Sir

How to add extra state in graph?

[gnuarm]

Thank you all,

Here is logic circuit which does this sequence detection.

The output is  flipflop of both and combined with and gate.

I didnt get why it takes 3 clock cycle and instead of 4 clock cycle.

Not sure why that bothers you.  From what I see, it is recognizing the sequence 1>0>1 which will take three clock cycles.  Why do you think it needs to take four clock cycles?  Maybe you are not implementing the state machine you really need?  Please share with us, the exact specification of your problem.

To respond to other posters saying you are missing an IDLE state, the S0 state is your IDLE state.  It's where you start the FSM and is not required to be entered to detect subsequent sequences that are 1>0>1.  Once you leave state S0, there are two other paths that permit the recognition of 1>0>1 inputs, without entering S0.

[audio]

Sir,

There is a book called Verilog FAQ. I have attached from books.google.co.in.

Refer the third point. He says moore machine takes a clock cycle more for operation.

[gnuarm]

Sir,

There is a book called Verilog FAQ. I have attached from books.google.co.in.

Refer the third point. He says moore machine takes a clock cycle more for operation.

To explain this is complicated.  First, I don't see the book.  What I expect he is saying is a Moore output requires an extra clock cycle to produce the result.  That depends on the details of implementation. 

The way your Moore machine is designed, with outputs dependent only on the states, means the input change is not recognized until the clock samples it.  So in reality, the input can change many, many times before the clock edge, without impacting the output. 

I don't see a state diagram for the Mealy machine, so I don't know what you have done with that.  The diagrams I typically find, put the output specification on the transitions, rather than the state.  That means, the outputs are also registered, but that they are clocked in separate registers from the state.  If, in your FSM, the outputs are not registered at all, you will find an indeterminacy of output changes and state changes depending on the detailed timing of the input.  Then, there are the practical considerations of outputs depending on the state, which is changing, without the output being registered.  This can result in spurs on the outputs, regardless of the input remaining constant.

Can you provide a state transition diagram for your Mealy machine?  Just for clarity, it will help if you write Mealy or Moore on every diagram you provide.  I may have mentioned that I don't use either model and so do not remember which is which. 

[ejeffrey]

Thank you all,

Here is logic circuit which does this sequence detection.

The output is  flipflop of both and combined with and gate.

I didnt get why it takes 3 clock cycle and instead of 4 clock cycle.

Not sure why that bothers you.  From what I see, it is recognizing the sequence 1>0>1 which will take three clock cycles.  Why do you think it needs to take four clock cycles?  Maybe you are not implementing the state machine you really need?  Please share with us, the exact specification of your problem.

To respond to other posters saying you are missing an IDLE state, the S0 state is your IDLE state.  It's where you start the FSM and is not required to be entered to detect subsequent sequences that are 1>0>1.  Once you leave state S0, there are two other paths that permit the recognition of 1>0>1 inputs, without entering S0.

In the OP they state that the goal is to recognize the pattern 0101.  That is why I said "missing the idle state" -- it's as if they are treating the initial bit as always matched.  However you describe it there needs to be an extra state to match a 4 bit pattern.

[gnuarm]

Thank you all,

Here is logic circuit which does this sequence detection.

The output is  flipflop of both and combined with and gate.

I didnt get why it takes 3 clock cycle and instead of 4 clock cycle.

Not sure why that bothers you.  From what I see, it is recognizing the sequence 1>0>1 which will take three clock cycles.  Why do you think it needs to take four clock cycles?  Maybe you are not implementing the state machine you really need?  Please share with us, the exact specification of your problem.

To respond to other posters saying you are missing an IDLE state, the S0 state is your IDLE state.  It's where you start the FSM and is not required to be entered to detect subsequent sequences that are 1>0>1.  Once you leave state S0, there are two other paths that permit the recognition of 1>0>1 inputs, without entering S0.

In the OP they state that the goal is to recognize the pattern 0101.  That is why I said "missing the idle state" -- it's as if they are treating the initial bit as always matched.  However you describe it there needs to be an extra state to match a 4 bit pattern.

Yes, I noticed that as well.  As is often the case, the initial problem statement is not well presented.  This one is bordering on the X-Y issue, where he asks for help on X, but he really needs help with Y.  He doesn't see that yet. 

There's also the issue of using clocked registers.  I don't know if the text or problem specify the use of clocked registers.  If the outputs are not clocked, and the inputs are free to change at any time, the outputs can change with the inputs, while the state will only respond on the clock edge.  The use of asynchronous logic will allow more rapid changes in the state, potentially changing the behavior of the state machine with rapidly changing inputs.  But these are seldom used.

[NorthGuy]

It is also unclear whether the overlapping patterns need to be recognized. For example, "010101" contains "0101" twice.

[gnuarm]

It is also unclear whether the overlapping patterns need to be recognized. For example, "010101" contains "0101" twice.

Yes, the current state diagram recognized every past pattern of "101", so, in cases with a sequence of "10101", it would flag twice, once after three inputs, then again after only two.  It makes the worry about how many state transitions are required to seem rather moot.

As is often the case, we likely will never get the complete, original problem statement. 

[Gurumurthy]

Thank you all.