hi: I need to build a sequence detector that is able to detect the sequences 010, 101, and 111 with overlap. I can only use D-flip flops, gates and/or multiplexers. I already know how to make sequence detectors of only one sequence starting with a state diagram and so far I'm doing great, but making one of three sequences has me completely lost. First I thought detecting 010 and 101 in the same system wouldnt actually make a difference in the design but that doesnt make much sense. Anyways, starting point or a nice reference for this kind of problem would be really appreciated! Thanks in advance.

 

https://www.google.com/search?q=sequence+detector&ie=utf-8&oe=utf-8

 

Just start out from an initial state of (I haven't seen anything) and then progress down a logic path that says, "If I see a 0 then I need to go to a state that tells me that I've seen a 0." The same for a 1.

Just keep track of which fragments of which sequences each state tells you that you have seen. There aren't that many states, so it won't take long to figure them all out.

 

Sorry I made another thread of the same problem but now I have more material done and might get more responses. I have to make a detector that detects 010, 101 and 111 with overlap. It can be done using gates, multiplexers and only D-flip flops.

I attached the picture of the state diagram I did, it's for a Moore system. Does anybody see a mistake? So far the professor isn't asking for the simplest design, except for the combinational circuits around the flip-flops, so as long as it detects the sequences its going to be fine.

 

You should have just made a reply to your other thread. Multiple threads for the same problem just invite confusion and chaos. I'll ask the mods to join the threads.

 

Are you supposed to give any indication as to which sequence was detected?

It's a bit hard to follow the logic (without solving the problem completely ourselves).

Try documenting your states with a comment indicating which pieces of which sequences have been detected if you are in that state. This will make it very easy to see if your state diagram solves the problem.

 

In sanity checking your state diagram, it appears that something is not consistent regardless of what the details of your assignment.

The only state you have that appears to be an accepting state is State E. Having reached State E, you then stay in State E as long as you keep receiving 1 at the input, but you leave State E if you receive a 0. Does that make sense?

Actually, I suppose it might depending on the fine interaction of the three sequences and these three look like they might fit the bill. I'll look at it more closely.

 

Oops. You definitely have a problem. Look at State E. Where do you go if you receive a 0? To State D or to State F?

But I think you are actually fairly close.

 

I think the problem you have stems from thinking that you only need one accepting state (State E). If you are only supposed to detect that one of the sequences was successfully seen and then stop further processing, this is fine. But if you are supposed to keep running and always indicate if the last input finishes one of the three sequences, then you need multiple accepting states.

 

Sorry for the extra post, thanks for answering. The sequencer is never supposed to stop, it should just give a signal whenever it detects one of the sequences. It stays in state E when receiving 1 so that it keeps detecting the 111 sequence. Im not sending it to A in case of a 0 so that it can recycle the previous 1 since it is with overlap. In state F im doing something similar if it keeps receiving 0 except that it is not giving a signal of detection, it is just waiting for a 1 hopefully to reach state E and detect one of the sequences. Thanks in advance for the help, It is really appreciated.

 

If you are in State E and you get a zero, what state do you go to next? State D or State F? You show an arrow going to both? How can that be?

If you got to State E by detecting 010. Then how does staying in State E upon receiving a 1 keep you detecting the 111 sequence?

 

Oh Ffffff you are right! Thanks! Let me check.

 

I think the right one is E to D.

E to F wont work for sure.

If I reach E by detecting 010 and receive another 1 it would then be recycling that 1 in the middle and detect/become 101.

 

Oh! but in the next 1 it would detect a 011....gotta check that

 

Added another state (H) to avoid detecting a 011.
Now E only points to D. What do you guys think?

Moderators note: Resized image,Please keep the size of attachments small.

 

I think I'm not going to download a 1.8MB attachment.

I think I'm not going to reverse engineer your state diagram again unless the states are documented as suggested previously.

 

Here are all the tables and the final circuit. I encountered a problem when it reaches H, detecting 010. If I keep switching 1's and 0's it reaches state D but that state doesn't detect and at the time of the 2nd 010 it should.

 

This is the other option I was thinking about. I'm not sure if it will work with the specifications given but I'll send that too just in case.

 

This is the other option I was thinking about. I'm not sure if it will work with the specifications given but I'll send that too just in case.

This is a viable approach provided it is acceptable to assume that, from the very beginning, you have seen an arbitrarily long string of zeros. For instance, if you initialize all three registers to zero and then the first to bits you see are a 1 followed by a 0, you will decode 010 even though you have only seen 10 so far.

 

Here are all the tables and the final circuit. I encountered a problem when it reaches H, detecting 010. If I keep switching 1's and 0's it reaches state D but that state doesn't detect and at the time of the 2nd 010 it should.

You still aren't getting the point of documenting your states. Here is what I mean:

STATE|0|1|Have Seen
A|B|C|nothing
B|B|D|0
C|E|F|1
D|?|?|01
E|?|?|10
F|?|?|11
G|?|?|010
H|?|?|101
I|E|I|111

Notice that each state represents a specific prefix that has been detected. The last three states are those in which a full sequence has been detected. From each state you just need to decide, based on the next bit received, what prefix you have now seen.