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??

 

Nope I don't understand your question.

 

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.'

 

Something like a 4 bit shift register with a parallel output plus an AND gate.

 

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.

 

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

 

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.

 

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

 

You're right. The link from S3 to S0 should be 0. Think that fixes it?

 

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

 

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.

 

Good! Looks like you've gotten it!

Congrats,
--Rich

 

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?

 

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

 

Only 2 flip-flops! Post your circuit.

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

 

You could look at this - http://www.brothersoft.com/downloads/logic-simulator.html