problem with finite state machines and mapping values

Discussion in 'General Electronics Chat' started by krpz, Oct 25, 2012.

  1. krpz

    Thread Starter New Member

    Oct 18, 2012
    Hello i have a querry about FSMs. For example if i have the below FSM:


    i need to assign values to states q0, q1, q2, q3.
    Is there a procedure that i need to follow in order to be correct or i can assign whatever values i want?

    For example if i put: q0=000

    is this correct?

    or if i put: q0=000
    q3= 101
    q4= 001
    this is also correct?

  2. tshuck

    Well-Known Member

    Oct 18, 2012
    Either one works, in fact, we use this in order to optimize a state machine. The optimization is a long process, but is beneficial for a large project. For this instance, it doesn't matter, you will see no difference, just make sure you assign the correct next state!
  3. takao21203

    AAC Fanatic!

    Apr 28, 2012
    It depends what you want the FSM to do in the end.

    Do you use CPLD, discrete logic, or software?

    If I would want to implement a software FSM, just having a flowchart like you show, it would be rather fuzzy to know the how's and why's.

    Have you made up this diagram, or is it from a book?
  4. takao21203

    AAC Fanatic!

    Apr 28, 2012
    It bounces from Q0 to Q1 or to Q2, and back again to Q0.
    Then it it will advance to Q3.
    Once it has reached state Q3, it will remain at this state.


    I don't properly understand what you mean by that.
    A FSM is kind of a serial automaton. Do you mean you feed a bitstream, which is either 000,001,010,or 011?

    000 - it will reach Q3 and remain there.
    001 - it will reach Q3 and remain there.
    010 - it will reach Q1.
    011 - it will reach Q2.
  5. ErnieM

    AAC Fanatic!

    Apr 24, 2011
    Since there are just 4 states you only need two bits to hold the current state, not 3 bits. Note one bit you define is always zero.
  6. takao21203

    AAC Fanatic!

    Apr 28, 2012
    Yes but depends how it is implemented. You could use the current state from the two bits register file, and map it together with the input to a decoder. Then you'll have three bits.

    This is a very simple state machine, only having one input, interpreting it as bitstream, and no output, just the actual state as "output".

    I have a paper from AMD about that, but it is bit vague to read without knowing what the state machine will be good for.

    It can help to understand software you actually write, so you have some theoretical foundation for your work. But in reverse, deriving from that theory, isn't so easy. As I say, the spelling remains rather vague, it is not really clear how the input or inputs behave, if they are bitstreams, how the actual state is mapped back to the input.

    You need to know how you implement it concrectely. Theoretical examination is not so much of use because different ways of implementation exist, and state machine theory is a tool, not a self purpose or something to be understood independently.