# Finding a solution to a partially specified FSM [Digital Circuit]

Discussion in 'Homework Help' started by knmonster, Jun 8, 2012.

1. ### knmonster Thread Starter New Member

Jun 8, 2012
6
0
Hi everyone, I've been trying to figure this out but I'm not sure what exactly I need to do.
Given:

where the inputs are xy
and

Which is the hardware schematic for the left flip-flop F1.

I need to fill in the automaton and complete the hardware schematic for the right flip-flop F0, using a jk flip-flop.

I think I have the missing states, but I'm not entirely sure how to do this problem.
This is based of the sr flip-flop. If I can even do it like that.
00 - top, 01 - right, 10 - left, 11 -bottom

As for figuring out the logic for the jk inputs of the jk flip flop, I'm not even sure how to begin. One of the things that is confusing me is that on the same 11 or 00 transition, a logic transformation will enable it to either stay or transition. I don't understand how it can transform to two different things. The only thing i've thought about to getting around that would be using the jk flip-flop Q output along with x and y or possibly using the F1 output from the sr flip-flop?

2. ### WBahn Moderator

Mar 31, 2012
20,065
5,665
Q1) What is the transition table for the left FF circuit that you posted? Make a table that has three columns for inputs, x, y, F, and one output column, F'. Here F' means the next value of F, not the complement of F. If that's confusing, then be more explicit and call it Fnext.

Q2) Now, using this as the known circuit for the left FF and using the information from the FSM transition diagram for the required behavior of the right FF, what is the transition table for the whole ASM? Since you don't know which value of the left FF corresponds to which state in the table, this involves a bit of detective work. So pick one of the states and figure out the next state transitions from that state both ways and check to see which is compatible with the diagram. If only one of them is, then that is the only assignment that has a chance of being correct. If neither of them are, then the circuit has no solution (assuming no errors made to that point). If both of them are, then either assignment is still possible. Proceed to one of the other states and repeat the process. Do this for all states making sure that each state has at least one assignment of the left FF that is compatible with the FSM. If so, then assign the value of the left FF to those states that only have one compatible choice. For the rest, assign them according to the need to keep all four states unique.

Q3) Now that you have a completed FSM, what is the complete transition table for the whole thing?

Q4) Now what is the control logic truth table for the J and K inputs of the right FF?

Q5) Now what is the logic schematic for the JK FF.

3. ### WBahn Moderator

Mar 31, 2012
20,065
5,665
You got it backwards. Post your answer to my Q1 if you don't see why.

4. ### WBahn Moderator

Mar 31, 2012
20,065
5,665
I either think this is a really good exercise or a really bad exercise. If they have you actually build the circuit and verify that it works, then it is a really good exercise because it won't work properly or consistently. If it is just a design problem on paper, then it is a really bad exercise because it is teaching you to build circuits that won't work properly or consistently (unless they go into what its weakness is and how to deal with it).

5. ### knmonster Thread Starter New Member

Jun 8, 2012
6
0
Q1) For the transition table I gotL
X Y F F'
0 0 F F
0 1 F 1
1 0 F 0
1 1 F F

I'm not entirely certain I did this correct, but with it my values would be:
10 -top, 00 - left, 11 -right, 01 - bottom?

Q3)

I'm not sure how to go from here to the implementation table though. I know I use the flip flop excitation table, but the example in the book are really confusing. Can you provide an example to get started?
Thanks, I really appreciate your help.

6. ### WBahn Moderator

Mar 31, 2012
20,065
5,665
What you have so far is correct.

Since we already know what the answer for the left FF, let's do it as an example. We would need to do it anyway as a check that we got our table correct, so it kills two birds with one stone.

The excitation logic is nothing more than the inputs to the FF that are required to move from the present state, Q, to the desired next state, Q'. For the RSFF, it is:

 Q Q' R S comment 0 0 x 0 Can either leave unchanged (00) or clear (10) 0 1 0 1 1 0 1 0 1 1 0 x Can either leave unchanged (00) or set (01)

With this, we go to our transition table for the whole thing and pull out the information for just the left FF and make two Karnaugh maps, one for R and one for S.

Down the left column is the present state while across the top row will be the xy inputs (i.e., the same as your table). I'm calling the left state 'A' and the right state 'B'.

For each cell in the table, we simply look at the systems transition table and see what A is going from and going to. For instance, in the state 00 with input 00, the A is going from 0 to 0. We then look at our excitation table and see that, to accomplish this, it doesn't matter what R is, but S has to be a 0. So we put 'x' in the R table and '0' in the S table in that cell.

We can fill in the table quickly by looking for every place A goes from 0 to 0 and entering these values ('x' in R and '0' in S) while we have them in our mind.

Karnaugh map for R
 AB\xy 00 01 11 10 00 x 0 x x 01 x 0 x x 10 0 0 0 1 11 0 0 0 1

Karnaugh map for S
 AB\xy 00 01 11 10 00 0 1 0 0 01 0 1 0 0 10 x x x 0 11 x x x 0

Now we can produce the excitation equations for R and S and we get

R = xy'
S = x'y

Note: Here I AM using the ' to indicate logical inversion (i.e., complement).

We see that these match the logic in the schematic for the left FF, so life is good.

7. ### knmonster Thread Starter New Member

Jun 8, 2012
6
0
This is what I got for J
 AB/xy 00 01 11 10 00 0 1 0 1 01 x x x x 11 x x x x 10 1 0 1 0

K
 AB/xy 00 01 11 10 00 x x x x 01 1 0 1 0 11 0 1 0 1 10 x x x x

J = A'x'y + A'xy' + Ax'y' + Axy
K = A'x'y' + A'xy + Ax'y + Axy'

Is that correct? I think I understood how to get these tables, but I'm not 100 percent sure on it.

8. ### WBahn Moderator

Mar 31, 2012
20,065
5,665
You got it! Good job!

The equations and the logic can be "simplified" a bit by noting fragments that are used in more than one circuit and also noting that XOR gates could be used in places. But in terms of basic SOP equations, this is it.

Now, one thing I would like to you pay attention to is whether your instructor deals with the timing hazards that the RS portion of the circuit presents. You may not have covered timing hazards yet, so they may be aware of them and just choosing to let sleeping dogs lie. If so, I understand the thinking, just am not sure I agree with it.

If they don't say anything, then you might simply ask if they would expect this state machine, if constructed as it stands now, to function properly and reliably. If they say yes, then they are likely out of their depth and are teaching a course they really aren't prepared or qualified to teach. It happens and is not necessarily their fault, but it would mean that you need to be a bit careful to make sure you understand the what's and why's of everything they tell you. In the end, that situation can make you learn more that you would have otherwise. On the flip side, if they say that, no, it probably won't work properly and reliably, then you have a good indication that they do know the subject matter pretty well.

To see what the main problem is, consider that you are in state 00 and that xy is currently 00. Now let's say you want to change xy to 11. The FSM says that nothing should happen and that it should stay in state 00. But no two inputs ever change at exactly the same time, so the circuit is going to see xy go either 00->01->11 or 00->10->11. See if you can figure out which of these paths causes a problem and why.

9. ### knmonster Thread Starter New Member

Jun 8, 2012
6
0
Thanks so much! You explained it much better than the professor did.

We've gone over static hazards, but nothing was mentioned about it in this problem. The focus lately has been on figuring out FSM's and implementing them, but they way the professor explained it was very convoluted.

Wouldn't the path 00->01->11 cause the error, because the states would transition from 00->11->11. While 00->10->11 would be okay because the states transition from 00->01->00.

So thanks again for all the help!

10. ### WBahn Moderator

Mar 31, 2012
20,065
5,665
You are more than welcome.

You are thinking along the right lines on the effect of the hazard, but are making a key mistake that indicated you aren't quite seeing the underlying cause. Keep in mind that the state of B can ONLY change on a rising clock edge, while the state of A can change immediately in response to changes in xy.

So let's walk through it:

AB = 00; xy = 00 : Starting condition
xy -> 01: A set to 1 (B can't change)
AB -> 10
xy -> 11: A stays in 1 (again, B can't change)
The JKFF is clocked
AB -> 11: Per the transition table

For the other way:
AB = 00; xy = 00 : Starting condition
xy -> 10: A cleared to 0 (which it already was) (B can't change)
AB -> 00
xy -> 11: A stays in 0 (again, B can't change)
The JKFF is clocked
AB -> 00: Per the transition table

So the first one ia a persistent failure while the second would not cause a problem.

Note that even if the states went from 00->01->00, this would be a problem because the state was supposed to remain unchanged. This is a glitch failure and if either FF glitches, that is a problem that violates the FSM definition and that must be dealt with.

Here is what I would recommend you do. Work the problem as stated. Then describe the timing hazard problem and rework the left logic using a clocked FF (your choice, DFF, JKFF, or TFF). It should be very easy because you already know you only have to deal with two inputs and that the state of A and B don't matter.

I think you will find that migrating to one of them is trivially easy.

second and for exactly the reason you described, except I think you made a typo in the one that would cause a problem because 00->10 would