16 State FSM Design

Discussion in 'Homework Help' started by chrisjsmith, Apr 9, 2017.

  1. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    Hello all

    I have to build an FSM. I have a picture of the question attached. I've created my FSM Diagram, the FSM state table but the trouble comes in creating the KMap. I've attached also my attempts the KMap.

    S0, S1, S2, S3 are my current states

    S0+, S1+, S2+, S3+ are my next states

    I'm thinking that i have to create a KMap for the "Next State" for both the INPUTS and OUTPUTS therefore in the end I should have 8 individual
    KMaps: 4 for inputs and 4 for outputs.
    Would I be correct in my approach ?
    Thanks for the assistance :)
     
  2. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    How many signals do you need to produce? You need one for each bit of state and you need one for each bit of output. How many total is that? You need one K-map for each.

    The K-maps you show are incomplete. Notice that S0 is always 0.
     
  3. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    If i'm following what your saying correctly i'd need 4 Kmaps for the input state and 4 Kmaps for the output states so that would be 8 individual Kmaps ?
    When you say "S0 is always 0" you refer to my state table?

    The states after 0111 must i represent these on the Kmap as well...i wasn't sure since after 0111 things begin to loop back to previous states on my FSM diagram....if that's to be considered then in total i would have 32 states.
     
  4. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    K-maps are for signals that you need to produce. You don't need to produce input variables -- they are your input signals.

    How many state variables do you have?

    You need one K-map for each of these?

    How many output variables do you have?

    You need one K-map for each of these?

    Each K-map needs to take into account all of the possible combinations of all of the variables upon which your circuit must base its decisions.

    For each of the state variables, what pieces of information must be considered in order to determine what the next value of that variable should be?

    For each of the output variables, what pieces of information must be considered in order to determine what the value of the output should be?
     
  5. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
     
  6. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    Not how many states. How many state variables? You have S0, S1, S2, and S3. How many is that?

    You have one output variable, namely Y.
     
  7. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    OHHHH
    my apologies I was a tard bit slow there...In that case I have 4 state variables for both the input and output
    thus i'll have 8 K Maps. So my K Map will be my state variables with respect to my output Y (x4) and Next state variables with respect to my
    output Y (x4)
     
  8. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    There's no such thing as n state variables for input (or output).

    You have one input variable. Period.

    You have one output variable. Period.

    You have four state variables. Period.

    You need a K-map for each state variable and for each output variable.

    How many K-maps do you need?

    For each variable that needs a K-map, which signals determine what value that variable needs to be?
     
  9. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    From what you've said I need 5 KMaps

    The input signal X and the output signal Y determines the value that the variable needs to be


    MOD NOTE: Edited post to put responses outside of quoted material.
     
    Last edited by a moderator: Apr 9, 2017
  10. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    First, a word about responding to quoted material. It is generally preferred that the quoted material be the only material between quote tags. Put your responses between quote blocks -- that also means you don't have to use a special font to distinguish them. If you respond like you have been, then if I try to reply to your post I get nothing because, technically speaking and as far as the forum software can tell, your post only quoted material and didn't contain any new content at all. This is considered an empty post and many forums are configured to expressly disallow this.

    So that you can have an example of what I'm referring to, I've gone back and edited the above post to reflect the preferred approach.
     
    chrisjsmith likes this.
  11. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    Correct.

    Really?

    So if X = 1 and Y = 0, what should each of the five variables be?

    You don't have enough information.

    In order to determine what state the machine should go to next, you need two pieces of information: What the value of X is AND what state the machine is presently in.
     
  12. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    Ok makes sense. So when you said my K Map was incomplete it's because I didn't cover all the states that the
    particular state variable could be in?
     
  13. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    Correct.
     
  14. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    So then the K Map i'm suppose to have should be this...SOP so i only show 1's
     
  15. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    That's not a valid K-map. The labels of a K-map have to be in Gray code sequence.

    It would be much better to show a 5-variable K-map as to 4-variable K-maps, each of which is a 4x4 array of minterms. One K-map is for one value of the 5th variable and the other is for the other value. Then you imagine them stacked vertically. There is also a way to mirror the states, which you did in your first attempt, although in a very unorthodox way.
     
  16. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    So i took some time to research the correct sequence for grey code up to the number 15 and corrected that.
    However i'm still unsure about the way you stated my K Map should look. When you say 5 variable 4x4 array i'm thinking
    Horizontal Side of K Map: My 4 State Variable with proper GC sequence up to 15
    Vertical side of K Map: I begin to have doubts. My input invariable X is here, Fine. The sequence is where i'm troubled. For X my options are
    0 and 1 only. Since it's 4X4 that means i'm missing to other options for X which i can't seem to figure out.
     
  17. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    The traditional 4-variable K-map is

    Code (Text):
    1.  
    2.  \AB
    3. CD\ 00|01|11|10
    4.    +--+--+--+--
    5.  00|  |  |  |
    6.    |--+--+--+--
    7.  01|  |  |  |
    8.    |--+--+--+--
    9.  11|  |  |  |
    10.    +--+--+--+--
    11.  10|  |  |  |
    12.  
    If you have five variables, then the classic way (not the only way) is to have two tables, one of which is for E=0 and the other of which is for E=1. Then imagine these two tables stacked on top of each other (like a three-dimensional tic-tac-toe boar). Cells can be group in any cube (as opposed to any square) in which all the values in the cube are the same.

    You can extend this to six variables by having four stacked tables, one each for EF=00,01,11,10.
     
  18. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    Ok and this totally makes sense to me, however when i stack these to tables on top of the other and introduce it to my 4 variable K Map
    do i just put this table to the bottom or right hand side of my 4 variable K Map since the other 2 sides a taken by AB and CD from the example above?
     
  19. WBahn

    Moderator

    Mar 31, 2012
    22,857
    6,821
    Imagine cutting them out and literally stacking on directly above the other. You have a three dimensional K-map.
     
  20. chrisjsmith

    Thread Starter Member

    Nov 12, 2016
    36
    0
    from what i've seen as i still wasn't understanding to clearnly
     
Loading...