string pattern recognizer

Discussion in 'Homework Help' started by ckaiser813, Sep 30, 2009.

  1. ckaiser813

    Thread Starter Member

    Jan 21, 2009
    17
    0
    trying to understand how the heck I understand the values of the inputs for these examples,

    i'm suppose to design a machine that outputs 0 whenever the input 1001 is detected and which outputs a 1 otherwise, serial one bit at a time.

    I understand what i'm looking for I just don't understand how to write my inputs? any help??
     
  2. blueroomelectronics

    AAC Fanatic!

    Jul 22, 2007
    1,758
    98
    Nope I don't understand your question.
     
  3. ckaiser813

    Thread Starter Member

    Jan 21, 2009
    17
    0
    the exact question from my prof

    Use the steps and method to design an F.S.M. for following state machine.
    'A state machine is required which outputs a logic 0 whenever the input sequence 1001 is detected, and which outputs a 1 otherwise. The input is supplied serially, one bit at a time. Also, 0010010010110 should be recognized as 1001 twice.'
     
  4. beenthere

    Retired Moderator

    Apr 20, 2004
    15,815
    282
    Something like a 4 bit shift register with a parallel output plus an AND gate.
     
  5. JDT

    Well-Known Member

    Feb 12, 2009
    658
    85
    First, draw a State Diagram. From this diagram, there is a systematic method (can't remember the name) to produce a Mealy Machine (which is a type of Clocked Sequential System) which includes logic simplification. I know this because I did it at college - long time ago now! (In fact I got a distinction in that particular course.)

    One thing I can remember is that your system has to be able to store the number of states on your state diagram. This requires a number of flip-flops. Example 4 states = 2 flip-flops, 8 states = 3 flip-flops.

    I would have to go back to those dusty text books in the loft. I'm sure some Googling or Wikipedia will help.
     
  6. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    One method is to play "State Machine." You start with State 1, which looks at a bit which State 0 -- the initializer state -- has passed to you.

    If you like it, you get the next bit, and pass it to the next state. If you do NOT like the bit, you'll need to change to another state, not necessarily the previous one.

    SO, you go through the bitstream, deciding if the bit is one you want or not, and taking action upon your decision.

    --Rich
     
  7. JDT

    Well-Known Member

    Feb 12, 2009
    658
    85
    Well I've had a bit of a think about this (without the help of the textbook) and come up with a state diagram with 5 states.

    Because there are 5 states, 3 flip-flops are required to store the state.

    These flip-flops require some logic to compute the next state, as per the diagram, depending on the current state and the input.

    See the attached diagram. Each "Logic" box has a logic function (equation). I know there is a nifty method to work out these equations. Probably a truth table would be a good start.
     
    • FSM.png
      FSM.png
      File size:
      31.7 KB
      Views:
      29
    Last edited: Oct 1, 2009
  8. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    Check what happens with a "11001" pattern. Also, "101001" and "1000". Note S3 has problems of ambiguity, as well as being undefined for a "0".

    --Rich
     
  9. JDT

    Well-Known Member

    Feb 12, 2009
    658
    85
    You're right. The link from S3 to S0 should be 0. Think that fixes it?
     
  10. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    Nope. Walk through the different patterns and see what happens. Each pattern I gave has a valid 1001 pattern. Does your state machine detect them all? Also test for just 1001, and 100101001.

    --Rich
     
  11. JDT

    Well-Known Member

    Feb 12, 2009
    658
    85
    OK. New State Diagram attached. Was a bit hasty before!

    The test is: from whatever state you happen to be in, 1001 always gets you to S4. (And in the special case of S4 - 001 goes back to S4.

    Think this new diagram is OK. No doubt you will tell me if not!

    Edit: In S1, input 001 gets you to S4. But, to be in S1, the last input must have been 1.
     
    Last edited: Oct 2, 2009
  12. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    Good! Looks like you've gotten it! :D

    Congrats,
    --Rich
     
  13. JDT

    Well-Known Member

    Feb 12, 2009
    658
    85
    Thanks. Now we just need the logic. Perhaps if things are quiet today I might have a go at it.

    BTW: What happened to the guy that originally asked this question?
     
  14. ckaiser813

    Thread Starter Member

    Jan 21, 2009
    17
    0
    i forgot i asked you guys about this ha

    i figured it out on my own

    those were my inputs Q1 Q0 |IN | D1 D0 | OUT (I used D flip flops)
    from there I buillt karnaugh maps and reduced the equations... I have 2 FF, 4AND, 2 OR in my circuit... works the way they want too and i just tested it on multisim
     
  15. JDT

    Well-Known Member

    Feb 12, 2009
    658
    85
    Only 2 flip-flops! Post your circuit.

    BTW: Can anyone recommend a free, but nice, logic simulator?
     
    Last edited: Oct 6, 2009
  16. beenthere

    Retired Moderator

    Apr 20, 2004
    15,815
    282
Loading...