1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

5-bit synchronous sequence recognizer design

  1. Oct 31, 2016 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations


    3. 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:

    10f5316a8d.jpg

    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 aswell 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?
     
  2. jcsd
  3. Nov 1, 2016 #2
    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.)
     
  4. Nov 1, 2016 #3

    lewando

    User Avatar
    Gold Member

    You could construct two independent state machines, each detecting a specific pattern. Combine the outputs.
     
  5. Nov 1, 2016 #4
    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.
     
  6. Nov 1, 2016 #5

    lewando

    User Avatar
    Gold Member

    You could recognize that you have 25 = 32 possible sequential input patterns. Assign each pattern to a state. You can then do the state transition interconnections.
     
  7. Nov 3, 2016 #6
    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.
     
  8. Nov 3, 2016 #7

    lewando

    User Avatar
    Gold Member

    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.
     
  9. Nov 3, 2016 #8
    Here is an updated one. I completely changed it. Can you check this one instead please:
    e7201e6280.jpg

    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.
     
    Last edited: Nov 3, 2016
  10. Nov 3, 2016 #9

    lewando

    User Avatar
    Gold Member

    State C has two exit cases both zero-case.
     
  11. Nov 3, 2016 #10
    Ah. Apologies for that. I have fixed it. New diagram:

    7f2817d7dc.jpg

    Is everything else okay?
     
  12. Nov 3, 2016 #11

    lewando

    User Avatar
    Gold Member

    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.
     
  13. Nov 3, 2016 #12
    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:

    0061fe98df.jpg
     
  14. Nov 3, 2016 #13

    lewando

    User Avatar
    Gold Member

    I think you got it! I checked it pretty extensively.
     
  15. Nov 3, 2016 #14
    Awesome. Thank you very much. I really appreciate it. Apologies for my stupid mistakes.
     
  16. Nov 3, 2016 #15
    One last thing. I need to design a Moore version of this as well. I know theres two or three extra states but I can't seem to figure it out. Here is what I have so far:
    139a3f4717.jpg

    My issue is with the D,G,H area. Not exactly sure how I put in the extra new states?
     
  17. Nov 4, 2016 #16

    lewando

    User Avatar
    Gold Member

    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.
     
    Last edited: Nov 4, 2016
  18. Nov 4, 2016 #17
    Ah. I see.
    Is this correct?
    51e3b02cfd.jpg
     
  19. Nov 4, 2016 #18

    lewando

    User Avatar
    Gold Member

    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"
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: 5-bit synchronous sequence recognizer design
  1. Designing a 4 bit ALU (Replies: 9)

Loading...