5-bit synchronous sequence recognizer design

[CoolDude420]

Homework Statement

I am trying to design a 5-bit sequence recognizer. The circuit has to detect two sequences of bits. The first sequence is 11001. The second is 10010. The output when no sequence should be 00. When the 1st input sequence is detected, the output should be 01. When the second sequence is detected, the output should be 10. Overlapping should also be detected. I'm designing a mealy type machine first.

Homework Equations

The Attempt at a Solution

The first step that we always do is draw a state diagram or state table whichever is easier. I chose to draw the state diagram first.

State Diagram:

A = No pattern has been detected yet
B = 1 has been detected.
C = 11 or 10 has been detected
D = 110 or 100 has been detected.
E = 1100 or 1000 has been detected.
F = 1101 or 1001 has been detected.

I am only meant to output 01 when the first sequence is detected(11001) and output 10 when the second sequence is detected(10010).
However as you can see with the bold bit numbers in the description for each state, if 10001(A>B>C>D>E>B) is detected, there will be an output of 01 there as well even though that is not a valid sequence.
Likewise with 11010(A>B>C>D>F>A), there will be an output of 10 even though its not a valid sequence.

I am quite confused as to how to fix this?

 

[Tom.G]

Overlapping should also be detected.

I presume that means that if one of the patterns occurs within a sliding 5-bit window that spans two adjacent packets, that is to constitute a match.
Sounds like using a shift register rather than a state machine would be a lot easier. Then build decoders to detect each of the patterns.

(When you get yourself into a box it's time to think outside the box.)

 

[lewando]

You could construct two independent state machines, each detecting a specific pattern. Combine the outputs.

 

[CoolDude420]

I presume that means that if one of the patterns occurs within a sliding 5-bit window that spans two adjacent packets, that is to constitute a match.
Sounds like using a shift register rather than a state machine would be a lot easier. Then build decoders to detect each of the patterns.

(When you get yourself into a box it's time to think outside the box.)

You could construct two independent state machines, each detecting a specific pattern. Combine the outputs.

The specifications of the assignment say that it has to be one finite state machine to detect both the sequences(i.e one circuit block). Apologies for not including this in the initial post.

 

[lewando]

You could recognize that you have 2⁵ = 32 possible sequential input patterns. Assign each pattern to a state. You can then do the state transition interconnections.

 

[CoolDude420]

You could recognize that you have 2⁵ = 32 possible sequential input patterns. Assign each pattern to a state. You can then do the state transition interconnections.

I understand that. My issue is with the connections between the states themselves. Am I missing a few states or something in my diagram? Can you help me out with my diagram please? I don't see how I can fix it.

 

[lewando]

You should not get too attached to a configuration, especially if it doesn't work. By the way, state E has no zero case exit path. Let me look at your diagram some more.

 

[CoolDude420]

You should not get too attached to a configuration, especially if it doesn't work. By the way, state E has no zero case exit path. Let me look at your diagram some more.

Here is an updated one. I completely changed it. Can you check this one instead please:

Overlapping is allowed. I think this state diagram is correct.

EDIT: Theres a mistake with the C state. The line from C to D should actually be a line from C to C with 1/00 over it.

 

[lewando]

State C has two exit cases both zero-case.

 

[CoolDude420]

State C has two exit cases both zero-case.

Ah. Apologies for that. I have fixed it. New diagram:

Is everything else okay?

 

[lewando]

How did you test it?

Consider this sequence: 10010010. The first part works (10010 results in output=10), but the next three: 010 (when preceded by 10) should also produce output = 10, but you end up in state D with output = 00.

 

[CoolDude420]

How did you test it?

Consider this sequence: 10010010. The first part works (10010 results in output=10), but the next three: 010 (when preceded by 10) should also produce output = 10, but you end up in state D with output = 00.

Ah. I see. I think I have fixed it. I've tried some other sequences and they work fine. Is there anything else you can spot.
Here is the new version:

 

[lewando]

I think you got it! I checked it pretty extensively.

 

[CoolDude420]

I think you got it! I checked it pretty extensively.

Awesome. Thank you very much. I really appreciate it. Apologies for my stupid mistakes.

 

[CoolDude420]

I think you got it! I checked it pretty extensively.

One last thing. I need to design a Moore version of this as well. I know there's two or three extra states but I can't seem to figure it out. Here is what I have so far:

My issue is with the D,G,H area. Not exactly sure how I put in the extra new states?

 

[lewando]

You had a Mealy transition path for 11001 of A -> B -> C-> E -> F -> .
Leave state A when you have detected pattern xxxx1.
Leave state B when you have detected pattern xxx11.
Leave state C when you have detected pattern xx110.
Leave state E when you have detected pattern x1100.
Leave state F when you have detected pattern 11001.

For a Moore, you will need to add an extra state: A -> B -> C-> E -> F -> F'
In state A you have detected pattern xxxxx.
In state B you have detected pattern xxxx1.
In state C you have detected pattern xxx11.
In state E you have detected pattern xx110.
In state F you have detected pattern x1100.
In state F' you have detected pattern 11001.

You had a Mealy transition path for 10010 of A -> B -> D-> G -> H ->.
Leave state A when you have detected pattern xxxx1.
Leave state B when you have detected pattern xxx10.
Leave state D when you have detected pattern xx100.
Leave state G when you have detected pattern x1001.
Leave state H when you have detected pattern 10010.

For a Moore, you will need to add an extra state: A -> B -> D-> G -> H -> H'
In state A you have detected pattern xxxxx.
In state B you have detected pattern xxxx1.
In state D you have detected pattern xxx10.
In state G you have detected pattern xx100.
In state H you have detected pattern x1001.
In state H' you have detected pattern 10010.

Work with that structure.

 

[CoolDude420]

You had a Mealy transition path for 11001 of A -> B -> C-> E -> F -> .
Leave state A when you have detected pattern xxxx1.
Leave state B when you have detected pattern xxx11.
Leave state C when you have detected pattern xx110.
Leave state E when you have detected pattern x1100.
Leave state F when you have detected pattern 11001.

For a Moore, you will need to add an extra state: A -> B -> C-> E -> F -> F'
In state A you have detected pattern xxxxx.
In state B you have detected pattern xxxx1.
In state C you have detected pattern xxx11.
In state E you have detected pattern xx110.
In state F you have detected pattern x1100.
In state F' you have detected pattern 11001.

You had a Mealy transition path for 10010 of A -> B -> D-> G -> H ->.
Leave state A when you have detected pattern xxxx1.
Leave state B when you have detected pattern xxx10.
Leave state D when you have detected pattern xx100.
Leave state G when you have detected pattern x1001.
Leave state H when you have detected pattern 10010.

For a Moore, you will need to add an extra state: A -> B -> D-> G -> H -> H'
In state A you have detected pattern xxxxx.
In state B you have detected pattern xxxx1.
In state D you have detected pattern xxx10.
In state G you have detected pattern xx100.
In state H you have detected pattern x1001.
In state H' you have detected pattern 10010.

Work with that structure.

Ah. I see.
Is this correct?

 

[lewando]

You should be able to answer that question yourself by running a set of sequences through it. The sequences should be long enough to give complete coverage. 10 bits should be enough. The first 5 should be variable the last 5 one of your target patterns. So 64 sequences? Associated with each sequence is the expected responses. Additionally, it could help to organize your diagram to facilitate evaluation--instead of a cloud of bubbles, consider two distinct branches representing the two main "success paths"