Sequence Detector

Discussion in 'Homework Help' started by circuitme, Nov 17, 2012.

  1. circuitme

    Thread Starter New Member

    Nov 10, 2012
    6
    0
    Hey everybody,
    So this is a homework assignment and I have fought through it but I am not sure if I am correct. So here is the question and my work so far. Please tell me if I am doing right and if not what am I doing wrong. Please offer a solution to fix it.

    Q.)Create a sequence detector that recognizes the following sequence on input x with overlap: "1011101", and sets the output y to 1 when the sequence has been detected.
    1.)Provide State Diagram
    2.)Generate truth table showing Previous State, input combinations, next state and outputs.
    3.)Encode the states and give the next state equations for the Q's and output as:
    -One hot encoding
    -D-flip flop
    -SR flip flop
    -Jk flip flop
    -T flip flop (Toggle)

    My work:

    2.)Truth Table:

    Previous | State || X | Next State | Y (output)
    0|0||0|00|0
    0|0||1|01|0
    0|1||0|10|0
    0|1||1|00|0
    1|0||0|10|0
    1|0||1|11|0
    1|1||0|10|0
    1|1||1|00|1

    1.)state Diagram is attached

    3.)This part I have not done because I need to know if I am doing the previous parts wrong or not and how to correct them. Also I am not quite sure how to do this part. I have reviewed my notes and can not figure it out. Please help.

    Lastly, I am doing the best I can. I am sorry if I appear to be a noob, or just suck. I am not trying to get you to do my hw but I really do need help. So please!!
     
  2. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,795
    I'm not sure what you mean by "x with overlap". Do you simply mean that the input sequence contains that target sequence at least somewhere?

    You need to document you state diagram better. What state does it start in? What state does (or state transition) means that the target sequence has been identified?

    i'm guessing that you are starting in State A and that a transition from State D to State A, upon seeing a 1, is your success condition. If so, then won't the sequence 1011 be seen as a success?

    You should be able to define your states and describe what each state means in terms of what the system is trying to achieve.
     
  3. circuitme

    Thread Starter New Member

    Nov 10, 2012
    6
    0
    Hey thank you for your response and sorry this took so long, but I have gone through this assignment over and over again. I believe I have completed it. So please check over the questions and my responses and see if I made any mistakes. I have attached everything. Thanks for your help.
     
  4. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,795
    The first question doesn't make sense. Implement each with the "largest" single multiplexer possible? Well, how about a 256:1 mux? Or a 1024:1 mux? Or even bigger? I think it is supposed to be with the "smallest" single mux possible.

    You need to reduce the size of your solution significantly. Others may have no problem downloading multi-megabyte files, but I am on a slow satellite connection and generally won't download something that is more than 300kB or so.
     
  5. WBahn

    Moderator

    Mar 31, 2012
    17,743
    4,795
    Remember, in order for your sequence detector to work, it not only has to output a 1 if it sees the sequence, it has to NOT output a 1 if it doesn't. You also have to be sure that you deal with the situation in which you have seen part of the sequence (i.e., a particular prefix) and that the next token does not extend the prefix you have seen, but it does still leave you with having just seen a smaller prefix of the sequence.

    For instance, if you see 1011 you have seen the 4-bit prefix. If the next bit is a 1, you have seen the 5-bit prefix (10111), but if the next bit is a 0, you still have just seen the 2-bit prefix (10).
     
Loading...