[SOLVED] Determining the detecting sequence from given state diagram of mealy machine

I was given a state diagram of a mealy machine as shown below:


I should determine what does this mealy machine do, that means find what kind of sequence it is detecting. I've tried to solve this and got 6 possible sequences:

When going from

I assume I've made that right, but I guess some of these sequences can be part of other sequences and thus can be combined or eliminated, but have no idea how to do it. How could I get the final sequence that the mealy machine detects?

I also think that this mealy machine can be simplified, that means, some of the states could be eliminated. I was thinking of states S2 and S5, because they actually do the same job as S1 and S4 respectively.

You analysis don't appear like the standard state transition table, which could give you much more information, such as for instance other states not predicted on the original diagram which you could manage in the final logic.

Okay. So I've made a state transition table with S - current state, S' - next state, x - input and y - output. I've also marked areas which I think can somehow be simplified, but that might not be correct. What can I deduce from this table that would help me simplify my state diagram?

Now I realize you were using the Row matching method, wich I'm unaware. The only one I know is by the Implication table, but is hard to explain. Anyway, nex stage is to draw the table of the state in the triangular box format, and fill with the transition pairs.

Thanks, however I don't quite understand what you mean by drawing the state transition table in triangular box format.

Referring to this: **broken link removed** you can see there is a triangle box.

- - - Updated - - -

I see 1 followed by any number of 0's followed by 1 (we are now in S3)
The next part gets weird either
we wait for a bunch of 0's followed by a 1
or we detect a 1 and then wait for 0 or more 0s before detecting another 1 setting the detect output

The sequence detector will detect any series of 4 1's separated by zero or more 0's. see sequence S0-S1-S3-S6-S0.

This is a really silly FSM. It looks like a very contrived example. Should be only 4 states each one staying in the state based on a 0 input.

- - - Updated - - -

Oops, I probably gave away the answer to the optimization problem.

Ok, thanks for help. I'm going to try to check it with the implication table suggested above anyway. I'm now trying to convert this four state Mealy machine into Moore machine. I guess I need a fifth state for it, because with only four states the output 1 would be immediately seen on the first state. Considering the fifth state, it would lead back to the beginning (S0) no matter if the input 0 or 1 is. Am I correct?

Yeah for a "pure" Moore machine you'll need the 5th state, as the output must come from finding that last 1.

You could implement the output in a Regsitered Mealy fashion where the output is a FF with the S3 state (4 states) and the input being a 1.

This method breaks the Mealy problem of inputs directly influencing the outputs via combinational circuits, which impacts the Fmax.

- - - Updated - - -

Zerograff said:

Considering the fifth state, it would lead back to the beginning (S0) no matter if the input 0 or 1 is. Am I correct?

Click to expand...

Actually if there is a 1 on that last 5th state is this supposed to be the start of the next sequence of four 1's or is that not allowed?, basically this would mean you have....
Four 1's in a row (what you've proposed by only going back to S0):
0..01(0...)1(0...)1(0...)10 - A new sequence of four 1's is not allowed immediately after the first sequence (differs from original FSM)
Five 1's in a row:
0..01(0...)1(0...)1(0...)11 - A new sequence of four 1's is allowed immediately following the first sequence (original FSM allows this)

Seems like the first one is allowed by the original FSM, so you would need to check if the input is 0 or 1 and go to either S0 or S1 respectively.