Sequence detector Mealy Diagram

[noobeestudent]

Hi guys, I was tasked to built a 8-bit 2 sequences detector.

The sequences are 0111 0011 and 0100 0010. I have a question.
Is it possible to group the bits if they have an identical value?

For example,

grouping them like this to reduce the number of states in the Mealy diagram.

Is it possible? Please let me know. Any help would be appreciated

 

[FvM]

Possible yes, but it comprises the concept of advanding the state machine based only on the present sequence bit. You need to memorize the previous sequence bit.

It's a step towards a different sequence detector method that reads the sequence bit into a shift register and compare all bits at once. Presumedly not the intended solution of your exercise problem.

It would be interesting to check which sequence detector is optimal in terms of used hardware resources (registers and logic elements). A possible extra after solving the problem straightforwardly.

 

[noobeestudent]

I'm only dealing with logic gates and flip-flops. Would it be advised to reduce the number of states.

This is my current Mealy Diagram.

Should I proceed with state diagram? And simplify the states using a implication chart?

 

[KlausST]

Hi,

my practical solution is to use a shift register a couple of inverters and a couple of gates.

01110011
01000010
1) green: 5 input AND gate with 3 inverters
2) blue: 3 input AND gate
3) orange: 3 input NOR gate
4) upper sequence: 1_out AND 2_out
5) lower sequence: 2_out AND 3_out

there will be a lot of other ways...

Klaus

 

[Akanimo]

Hi,

This is another way to make the comparison. Take the upper bit string as (X7 X6 X5 X4 X3 X2 X1 X0) and the lower bit string as (Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0).
Connect as follows: X7 NOR Y7; X6 AND Y6; X5 AND (X5 XOR Y5); X4 AND (X4 XOR Y4); X3 NOR Y3; X2 NOR Y2; X1 AND Y1; X0 AND (X0 XOR Y0) to obtain (Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0).
Connect (Z7 AND Z6 AND Z5 AND Z4 AND Z3 AND Z2 AND Z1 AND Z0) to obtain A.
Anytime A has the bit value '1' then you have had the sequence in succession.

But then, we should have two registers, X and Y, and we should always replace the content of X with the content of Y, so that we can have successive bit strings for the comparison as illustrated above.

From the values of the bits in the sequence, it is obvious that the bit string Y is moved into corresponding positions of bit string X every clock cycle (i.e. the registers are PIPO), else it would not be possible for the sequence to be in succession. Or if the bit strings are serial, then the sequence cannot possibly be in succession after a single clock cycle. You just didn't clarify this part though.

--- Updated Nov 20, 2020 ---

I have noticed that my solution has the same number of gates as that of Klaus. It seems like with my solution the number of gates cannot be reduced but taking a hard look at Klaus' solution reveals that the number of gates can be reduced, making Klaus' solution a better one.

So how can the number of gates be reduced in Klaus' solution? If we keep every other thing intact but have:
1) 5 input NOR gate with two inverters. Note that you will have two sets of this. One set for the upper and one set for the lower.

If the intention is to write a structural HDL code, then the number of gates can be even further reduced by making
1) 10 input NOR gate with four inverters.

 

[noobeestudent]

I think I was not clear with my question.
The bits are to entered into the machine 1 by 1, thus every correct bit will move in onto the next state.
The sequences I need to detect are 0111 0011 and 0100 0010.
Overlapping patterns are allowed.

It is supposed to be like this but with 8 bit sequences instead of 4 bit.

I hope that this can help to you to understand better.
Thanks in advance for your help.

 

[KlausST]

Hi,

Is this a practical task or a school project?

Klaus

 

[noobeestudent]

Hi,

Is this a practical task or a school project?

Klaus

This is part of my Coursework. Its an assignment to be exact.

 

[KlausST]

Hi,

So, then the task is to use Mealy...
School is long time ago for me, and I can't remember Mealy at all.

Thus I guess I'm not of much help.

Klaus

 

[noobeestudent]

This is the updated mealy diagram after i found some errors on the previous one

 

[vGoodtimes]

The practical solution is to use the shift-reg as previously mentioned. I think this is the case for most fixed-length pattern detectors. But the goal of the school project is to learn a bit about FSM's, not to overcomplicate the problem to the point a FSM is the only solution.

I only get 13 states: s00, s11, s22, s30, s40, s51, s61, s72, s13, s14, s15, s16, s27. Where the first digit is the number of bits matched on pattern1, second digit is number matched on pattern2. For a mealy machine -- where the match outputs can use the input bit -- there is no need for a s18 or s80.

I think these are S8, S14 in your diagram. They are not needed for the mealy machine and perhaps that is the intended lesson. Notice the example 4b detector only has states for 0, 00, 000, 001 -- not 0001 nor 0010.