# 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,808
295
Something like a 4 bit shift register with a parallel output plus an AND gate.

5. ### JDT Well-Known Member

Feb 12, 2009
658
87
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
29
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
87
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
File size:
31.7 KB
Views:
29
Last edited: Oct 1, 2009
8. ### RiJoRI Well-Known Member

Aug 15, 2007
536
29
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
87
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
29
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
87
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.

• ###### FSM-1.png
File size:
20.4 KB
Views:
32
Last edited: Oct 2, 2009
12. ### RiJoRI Well-Known Member

Aug 15, 2007
536
29
Good! Looks like you've gotten it!

Congrats,
--Rich

13. ### JDT Well-Known Member

Feb 12, 2009
658
87
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 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
87
Only 2 flip-flops! Post your circuit.

BTW: Can anyone recommend a free, but nice, logic simulator?

Last edited: Oct 6, 2009

Apr 20, 2004
15,808
295