# Beginner Boolean Algebra, Sequential Circuit.

Discussion in 'Homework Help' started by zesverige, Jun 19, 2012.

1. ### zesverige Thread Starter New Member

Jun 18, 2012
4
0
Hi,

I have been working on this question, and am stuck on the next state equations....

http://imgur.com/VzY69

anyway I have got the Characteristic equations to be:

JA= M, KA= M' , JB= A, KB = A' , JC = B, KC = B

Now the next state equations i have used the JK FLIP FLOP Char Equation

Q t+1 = JQ' + K'Q

to work out the next state equations.

so A t+1 = JA' + K'A
=> (M)A' +(M')'A
=> MA' + MA
=> M(A'+A)
=> M(1) A'+A = 1
=> M

Now i am a bit confused as this process repeats itself for each next state equations, only the final Letter differs..

I get B t+1 = A
and C t+1 = B

Am i doing something wrong?

Also where do i go from here?

State Transition Table -

Primary Inputs | Current State | Next State | Output |
M A | B | C At+1 Bt+1 Ct+1 P
0 0 0 0
0 0 0 1
0 0 1 0
0
0
0
0
0
1 WHAT WOULD (A t+1) and B and C look like?
1
1
1
1
1
1
1

SORRY for the lengthy-ish post..all i want is some clear pointers on where to go from where i am? or if i have done it correctly.

Thanks for you patience and Time in reading this..

2. ### Ryzaar New Member

Jun 12, 2012
10
0
Ooh that looks like one of the 2010 ENGR exams at Flinders University (I'm revising that exact question right now ).

Anyway, once you have filled out your State Transition table with your input and current state values, you have to work out your next state values using boolean algebra. E.g. your top row:

M A B C
0 0 0 0

At+1= M
Bt+1= A
Ct+1= B

Therefore the next-state columns in your table will look like:

At+1 Bt+1 Ct+1
--0----0----0--

Do that for every combination of MABC, and you'll have all of your next-states. The same goes for your output as well.

EDIT: Double check your next-state equation for "JC = B, KC = B", I got something different. First thing to notice is there is no NOT B, unlike the two excitation equations before.

Last edited: Jun 20, 2012
3. ### zesverige Thread Starter New Member

Jun 18, 2012
4
0
what are the chances of that ayee...well ye so i got those correct, thats good news!

So basically the Ct+1 column is the same as t B column
and Bt+1 is the same as A column?

Can i ask you what you got as the output equation?

EDIT: OH **** yes..to be honest i didnt even do that one i just looked at the other 2 and made an assumption. Cheers i Will change it.

EDIT AGAIN: What was your Ct+1 equation... (B)B + (B')B
BB+B'B
B + B'B

Last edited: Jun 20, 2012
4. ### Ryzaar New Member

Jun 12, 2012
10
0
Yes, for mine, my A+1 column matches my M column, Bt+1 matches the A column, and then the Ct+1 and P columns are slightly different.

For your Ct+1 equation, I think you incorrectly substituted Q for B, rather than C:

Qt+1 = JQ' + K'Q

Ct+1 = BC' + B'C
Ct+1 = B XOR C

For the output equation, you can see that M and A are XORed, and then NANDed with NOT C.

This then gives me: (C' (M XOR A) )'
(notice I have inverted that whole lot as it passes through a NAND gate).

Let me know where you get up to, as I have completed the question, and can show you anything you might not understand. The P column may be hard to fill in, so here is my tip:

1. Work out where M XOR A = 1. There is one specific section of the table where this occurs.
2. Since M XOR A is NANDed with NOT C, you will only get an output of 1 where M XOR A = 1, and C = 1
3. Everywhere else will be an output of 1, as a 2-input NAND gate will always output 1 when at least one if its inputs is 0.

5. ### zesverige Thread Starter New Member

Jun 18, 2012
4
0
I tried doing as you stated in the 3 tips!, i think i may have done it correctly.

P

0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1

XOR Gate = 1 when ===== > 0 XOR 1 now you NAND that 1 with the C column which has given me this..also like you stated the NAND = 1 if a ZERO is present. so that is how i got the ones...I just realized i didnt accomodate for the NOT C, i more so just NAND'D the (A(+)M) with C

I thought i had it for a sec..but now i am even more confused.

EDIT: ALSO is there 8 states? each having 2 transitions?

EDIT: Just done all the states and the transitions..cant really explain it to you, but it goes all over the place..it doesnt flow nicely in a circle.. however i dont think that is an issue as long as it is correct.. In my notes i have an arrow pointing to the state that represents the Y Value..In our case the P value.. what if you have multiple P outputs for the same STATE

FOR EXAMPLE

M---A--B--C----At+1---Bt+1---Ct+1---P
1---0--0--1----1--------0-------1-----0
1---0--1--0----1--------0-------1-----1

See how i have P = 1 and P=0 on the same state....do i draw 2 arrows saying P is equal to both 1 and ZERO on this state..

Thanks Man appreciate it.

Last edited: Jun 20, 2012
6. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
I see that Ryzaar has already been offering assistance. Here's my input without regard to what he has already said (just so that it will be complete and self-consistent). If you think this is duplicating too much, feel free to ignore.

I think you mean to call them the "excitation" equations, not the characteristic equations.

But, yes, I agree that these are correct.

Correct.

Correct. Notice that this is the characteristic equation for a D-type flip flop (DFF), meaning that this is how you would implement a DFF using a JKFF.

You are correct for B, but take a closer look at C. Are the excitation equations comparable between C and those for A and B?

I looked at your subsequent updates and the latest one seems to be:

Is that the correct form for the characteristic equation for C? Doesn't the characteristic equation for a JKFF involve that JKFF's state somewhere?

Assuming that this were correct, can't you simplify that last line even further? What is B'B?

Once you have this correct, you should note that it is a T-type flip flop (TFF), which holds it's states if the input is LO and toggles its state if the input is HI.

I would recommend doing what the question asks for next. I'm not being flip; don't get ahead of yourself without good reason. The next thing asked for is the output equation for P. So do that in terms of the system inputs and states and simplify it as much as you can. In particular, apply DeMorgan's Theorem and you will see that the output equation is extremely simple.

Notice that this is a Mealy Machine, meaning that the input is a function of not only the state variables (as in a Moore Machine), but also of the present inputs. The thing to keep in mind is that state variables only change on the clock, but input variables can change at any time. This will be reflected in your state diagram because you will only have eight states, but each state needs to indicate what the output will be for each combination of the inputs while in that state. So your table must essentially include a subtable for each state that reflects the possible combinations of the input variables used by the output. Since you have three state variables, your table will have eight sections, one for each state. But each section will have two rows, one for each possible value of the single input value used to determine P. One way to combined these neatly and compactly is to organize your table as follows:

 M = 0 M = 1 A B C An Bn Cn P An Bn Cn P 0 0 0 . . . . . . . . 0 0 1 . . . . . . . . 0 1 0 . . . . . . . . 0 1 1 . . . . . . . . 1 0 0 . . . . . . . . 1 0 1 . . . . . . . . 1 1 0 . . . . . . . . 1 1 1 . . . . . . . .

Note that I'm using An as a shorthand for A_next, or A(t+1).

Filling in the table should be very fast at this point using the individual next state equations and the equation for P.

7. ### Ryzaar New Member

Jun 12, 2012
10
0
My final column went a little like this:

1
1
1
1
-M XOR A = 1-
1
1
1
1

I left out the M XOR A section for you to work out. The reason why P = 1 where (M XOR A) = 0, is because this input of the NAND is 0. As I said 'anything' NAND 0 will always give 1.

I think you identified this section that I spoke of, but you accidentally NANDed it with C, rather than NOT C (I may have confused you with my way of solving it quickly).

You are correct in saying that this has eight states, as there are 8 possible combinations for ABC as a 3-bit binary number. Also note that the output occurs during the state transition, not when the state is arrived at. For example, look at this picture:

This picture states that an input of 1 while in S1 takes you to S1 with an output of 1. An input of 0 while in S1 takes you to S2 with an output of 1, etc.

I attempted drawing the diagram in a circular format, but it got really messy. I'll try again in a moment and see if I can show you what I got for comparison.

EDIT: Here is a picture of my state diagram. I tried to draw it out in a linear format but as you can see it's still pretty messy. I put a box around my inputs/outputs so you can see which transition it belongs to.
http://oi46.tinypic.com/11t6238.jpg

If you're still unsure or would like to check out your answers, here is my working out for the question.
http://oi50.tinypic.com/okze2w.jpg

Last edited: Jun 20, 2012
8. ### zesverige Thread Starter New Member

Jun 18, 2012
4
0
Yes i NAND'd it with C, I should have done NOT C, i see now what you have done. The main problem for me would be the table i suppose, i am just unsure on how it will be marked..lets say that i do make a mistake as i have done, (Using C instead of C'), will it be deemed as a Zero or would you have any ideas., Even for the Finite State Machine question What are your thoughts on what type of question will be coming?, I have looked at the previous exams and they all seem to deal with the sequence or word recognizers, one had the coin input problem. Now my question is lets say a silly mistake is made at the states at the start of the FSM, and you go on to complete the entire question using this wrong infromation. WIll it be deemed a Zero.

Cheers man you are a lifesaver, i know i left it late but the important thing is that i understand the question.

Once again I thank you for going out of your way to help me. The world needs more people like you .

9. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
What is this assertion based on? P is merely a logic function of three variables and is, at any time, equal to whatever the function evaluates to on those three variables. If you are parked in a given state and change the input, M, then the output will change (if the logic function evaluates to a different value) immediately. Also, what does it mean "occurs during the state transition"? During the transition, P will tend to be very glitchy since it is not registered.

I still recommend applying DeMorgan's Theorem to P as it makes it much cleaner and less likely to result in the kinds of oversights that the OP was having:

P = ((M XOR A)(C'))'
P = (M XNOR A) + (C)

So P is HI if either C is HI or if M and A are equal.

In general, humans are not good at dealing with logic involving inversions, so try to eliminate as many as you can in expressions that you, as a human, are going to be working with. The reverse is true for hardware; transistors are instrinsically inverting, so expressing logic in terms of NANDs and NORs is the most efficient from a hardware perspective (in most cases).

With that, you can then immediately fill in the output portion of the transition table:

 M = 0 M = 1 A B C An Bn Cn P An Bn Cn P 0 0 0 . . . 1 . . . 0 0 0 1 . . . 1 . . . 1 0 1 0 . . . 1 . . . 0 0 1 1 . . . 1 . . . 1 1 0 0 . . . 0 . . . 1 1 0 1 . . . 1 . . . 1 1 1 0 . . . 0 . . . 1 1 1 1 . . . 1 . . . 1

Filling in the next state portions is also trivial, given the nature of the next-state equations.

An is simply equal to M, Bn is simply equal to A. Cn is the slightly trickier one in that it toggles if B is HI.

 M = 0 M = 1 A B C An Bn Cn P An Bn Cn P 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1

The state diagram can be drawn cleanly with no overlapping lines. I'll post that later after I get to a scanner.

Since humans also deal with base-10 much better than binary, the table can be made even more readable by

 S M=0 P M=1 P 0 0 1 4 0 1 1 1 5 1 2 1 1 5 0 3 0 1 4 1 4 2 0 6 1 5 3 1 7 1 6 3 0 7 1 7 2 1 6 1

Last edited: Jun 20, 2012
zesverige likes this.
10. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
Attached is the State Diagram.

• ###### FSM.png
File size:
6 KB
Views:
54
Last edited: Jun 20, 2012
zesverige likes this.