State Diagrams and State Transition Tables!

Discussion in 'Homework Help' started by ElijahSykes, Sep 20, 2006.

  1. ElijahSykes

    Thread Starter New Member

    Sep 20, 2006
    6
    0
    Hey, I'm just starting an electronics course and am having some difficulty working out state diagrams and state transition tables from looking at circuit diagrams!

    The question I am attempting is here:
    http://www.cl.cam.ac.uk/tripos/y2002p2q3.pdf

    I think I have part (a) and (b) right :rolleyes: -
    a) The system has 8 states
    b) The state transition table will have 8 rows (one for each state)

    However.. Parts (c) and (d) have confused me :mad: ,

    I dont know how to go from the circuit diagram to the state transition table! :confused:

    So far I gather the table needs 3 columns; Present State, Next State and Output - but I dont know which parts of the input/output values to put into the columns..

    Then it asks me to draw the state diagram.. but if I am right in saying there are 8 states.. surely thats going to be one very complicated diagram with 8 circles and several connections between each of them for the transitions! :eek:

    I would really appreciate any guidance you guys could offer me, thanks!
     
  2. n9352527

    AAC Fanatic!

    Oct 14, 2005
    1,198
    3
    Where did you get the 8 states from?
     
  3. ElijahSykes

    Thread Starter New Member

    Sep 20, 2006
    6
    0
    Hey, thanks for taking a look at this,
    I worked out that there should be eight states since there are 3 variables which affect the output of the system - A, B and Y (A&B are inputs, Y is fed back into the system thus effectively being an input aswell),

    So A, B and Y could be in any of the following 8 states:

    A B Y
    0 0 0
    0 1 0
    1 1 0
    1 0 0
    0 0 1
    0 1 1
    1 1 1
    1 0 1

    Make any sense?! :confused:
     
  4. n9352527

    AAC Fanatic!

    Oct 14, 2005
    1,198
    3
    Actually, the number of states does not have any relationship with the number of input signals. A system with only one input signal, can have substantially more than one states. Decoding transmission of serial data is an example of this. Also, a system that has only two states can have more than two input signals.

    The maximum number of possible states in a system is dictated by the memory elements inside the system. The states have to be physically represented inside the system, this is usually implemented by the memory elements (in this case flip-flops). If a system only has one flip-flop, then the maximum number of states are only two. 2 FFs = 4, etc. ...

    To complete the transition table, you have to work out the transitions of the JK FFs for different values of A, B and Y.
     
  5. ElijahSykes

    Thread Starter New Member

    Sep 20, 2006
    6
    0
    Hey, thanks for your response - that has been very helpful :)

    Just to make sure I'm understanding what you said correctly,
    - A systems possible states can be determined by enumerating all the possibilities of ways values can be held in memory.

    So... since I have 2 JK Flip-flops ( 'x' and 'y' ) in my system, and each of these can have one of 2 possible outputs (1 or 0), there are four possible states:

    x y
    ----
    0 0 - State1 (S1)
    0 1 - State2 (S2)
    1 1 - State3 (S3)
    1 0 - State4 (S4)

    Then for the State Transition Table:

    -I put the possible inputs horizontally
    -I put the 4 states (S1-4) vertically
    -The cells indicate the next state given a particular input
    -The forward-slashes indicate conditions which can't happen



    [​IMG]


    Sound alright?! ;)

    Cheers :)
     
  6. n9352527

    AAC Fanatic!

    Oct 14, 2005
    1,198
    3
    Excellent work! You might want to find out the preferred format for the table from your tutor. There are several of them to choose from...
     
  7. JoeJester

    AAC Fanatic!

    Apr 26, 2005
    3,269
    1,063
    n93,

    Although I understand the reasoning illustrated, and the directions state X and Y are outputs, Y certainly influences X. I would have assumed that X is the ONLY output from the circuit.

    The output of the Y ff loops back to the combinational logic without an indication of leaving the circuit, as is illustrated by the X output.

    If we were to include Y as an output, why didn't we include the outputs of the "combinational logic" circuits?
     
  8. n9352527

    AAC Fanatic!

    Oct 14, 2005
    1,198
    3
    Hi Joe,

    It is certainly possible to include the output signals from the combinatorial logic as output signals for the system.

    Broadly, there are two types of common finite state machine (FSM) designs. The first is Moore machine, where the system's outputs depend only on the system's current state. A FSM of this type, then only considers the FFs outputs (or signals that are solely derived combinatorially from the FFs outputs) as the system's outputs.

    It doesn't matter whether a particular FF output influences the next state or not (fedback through the combinatorial logic to the FF inputs). In this example, X does not influence the next state, so it's sole purpose is to indicate the current state. Whereas Y does influence the next state and also indicates the current state. The outputs, which depend on the current state only, are derived from X and Y.

    The second is Mealy machine, where the system's outputs depend not only from the current state, but also from the input signals (or signals that are combinatorially derived from the input signals). In this type of machines, then it is possible to include the output from the combinatorial logic as part of system's outputs as you indicated.

    Moore machines are simpler to design and much easier to understand than Mealy machines. I think this is why most of the introductory courses in digital design put forward Moore machines first as examples or exercises for learning state tables and state transition diagrams.
     
  9. JoeJester

    AAC Fanatic!

    Apr 26, 2005
    3,269
    1,063
    N93,

    Nicely done.

    Thanks.
     
Loading...