# Finite state machine problem

Discussion in 'Homework Help' started by cdummie, Feb 16, 2015.

1. ### cdummie Thread Starter Member

Feb 6, 2015
105
1
I have to make synchronous sequential logic that implements finite state machine shown in this picture:

I am allowed to use J-K flip-flops and standard logic gates.

Now, i tried to do it this way, i made transition table, after i described states S0, S1 and S3 with values 00, 01, 10 respectively, and it looks like this:

Now, i am not sure if i have to use 11 for Q1Q0 because there's no state described with 11, yet, table looks "unfinished" without it, and it's easier to minimize those functions. Now, after minimizing this is what i got as inputs:

J1=Q0X, K1=X', Jo=Q1'X', Ko=X.

Now, the part that i'm the least sure of:
Output value. I've seen it in some examples but i never understood the meaning of it, is it output of the whole sequential logic or what? Anyway, this is how the table looks like:

so Y looks like this: Y=Q1'Q0'x'+Q1X. Basically, i want to know if this is correct, am i allowed to add 11 in the table even though there are three states and why do i have to create logic for the output?

2. ### WBahn Moderator

Mar 31, 2012
20,057
5,644
What you have is known as a Mealy machine, in which the output is a function of both the current state and the current inputs.

Each transition edge is labeled with "input/output". So an arrow from State A to State B that is labeled "1/0" says that if you are in state A and the present input is a '1', the present output should be a '0' and you should go to State B on the next active clock edge.

As for why you have to create logic for the output, what other alternative do you have in mind?

3. ### cdummie Thread Starter Member

Feb 6, 2015
105
1

I don't know i just don't understand what is output actually, do i connect the output with the last flip-flop or what? What's with those 11, do i have to add them to the table even though there's no state described with it, i mean, is my work correct?

4. ### WBahn Moderator

Mar 31, 2012
20,057
5,644
If you don't understand what the diagram is telling you, then it really doesn't matter if your work is correct. If it does happen to be correct, it is only by luck and coincidence, what was called by one of my professors as "a happening" -- you do something without understanding it and hope that it "happens" to work. Would you be comfortable going to a doctor who doesn't understand your symptoms, but just "happens" to get the diagnosis correct anyway? If not, then you should not be satisfied with becoming an engineer that is comfortable with using that approach, either.

What "last flip flop"? You have two flip flops and they store your state information. There is no "first" and "last" flip flop -- they are one equal ground. Also, since your output depends not only one which state you are in, but also what the current input is, you can't just tie your output to a flip flop output, can you?

Look up Mealy Machine and read up on how to interpret the state diagram for such a machine.

I don't know what you are referring to by "those 11". I don't see a 11 anywhere in the problem statement. If you are talking about the fourth state (however you choose to code the other three) then the problem doesn't specify how the system should behave for that situation. That's poor problem specification, but it is unfortunately pretty common. Strictly speaking, your solution could do anything if it gets into that state; it could lock up, it could reset, it could start a global thermonuclear war -- all three are equally valid and compliant with the given spec.

5. ### tshuck Well-Known Member

Oct 18, 2012
3,527
675
You may want to take a look at this thread - it was meant to supplement the current section on FSMs in the eBook and introduce the Mealy Machine (the same kind of FSM that you have).

You seem to know the approach, but lack the knowledge of why it is done this way - I attempted to address that in the aforementioned thread. Give it a read and post back if you still have questions.

To get you started, the output is a combination of the FSM state (all of the flip flops that hold the state) and the input.

6. ### cdummie Thread Starter Member

Feb 6, 2015
105
1
Well, i heard of finite state machines just a few weeks ago, and as i noted, i never done many examples, so i'm new to this, i just wanted to know if i'm doing well, but thanks anyway.

7. ### cdummie Thread Starter Member

Feb 6, 2015
105
1
Thanks, i'll check it out and post back.

8. ### WBahn Moderator

Mar 31, 2012
20,057
5,644
I'm trying to think of what your conceptual problem might be and I'm not sure I've got a handle on it, but let's give this a try.

You say that you don't understand what the output actually is. Keep in mind that this state machine is just part of a larger system and what the output means isn't specified. So just think of it as being an indicator light on a panel. If the system is in State S0 and the input is presently a 0, the light should be on. That's what the "0/1" on the arrow coming out from S0 means. If the input is presently a 1, the light should be off. That's what the "1/0" on the other arrow coming out from S0 means. On the next active edge of the clock, if the input is presently a 0, the system will transition to State S1 while if the input is a 1 at that time the system will stay in State S0.

Hopefully that helps.

9. ### cdummie Thread Starter Member

Feb 6, 2015
105
1
I looked up on what t-shuck posted, i saw the circuit i think i understand it better now, i confused it with counters, i see this is a way different

10. ### tshuck Well-Known Member

Oct 18, 2012
3,527
675
FSMs are a different beast with some similarities to synchronous counters. It is pretty easy to get confused if you don't understand what's going on.

Let us know if you still need help.

11. ### cdummie Thread Starter Member

Feb 6, 2015
105
1
It's output that was confusing me, but when i saw the picture in your thread it makes sense, because, there's no point of making the circle if you don't have output implemented, since then i can't know when the sequence is detected.

12. ### tshuck Well-Known Member

Oct 18, 2012
3,527
675
The output-forming logic in a Mealy machine is more involved than what a Moore can be (though it's generally pretty simple).

The Moore implementation's output, being dependent only on the current state, could be made to be a single flip flop output, where a Mealy will be some combination of the current state and the input.

It's also important to note that it is possible to have more than one output in a state machine.

I'm glad it helped you understand better!

Just remember: output-forming logic will take into account the current state (and the input for Mealy machines).

cdummie likes this.