Gate Level model of a Finite state machine

Discussion in 'VHDL' started by Inderkal, Dec 8, 2004.

  1. Inderkal

    Inderkal Guest

    Does anybody have any ideas about implementing a gate level model of a
    finite state machine? Any kind of info will do. I just want to get
    started.
     
    Inderkal, Dec 8, 2004
    #1
    1. Advertising

  2. Inderkal

    rickman Guest

    Inderkal wrote:
    >
    > Does anybody have any ideas about implementing a gate level model of a
    > finite state machine? Any kind of info will do. I just want to get
    > started.


    While working with one-hot encoded state machines, I realized that the
    input function for each state register was a simple two level sum of
    products.

    Your state diagram will have arrows representing the transitions between
    states. A condition is associated with each transition. If you express
    each transition as a product (AND) of the state and the condition you
    can then sum (OR) the resulting products to form the input function to
    the state register.

    This can be generalized to different encoding schemes by using a full
    decode for the state input. The resulting sum will be used to form the
    next state value. All of these values may be further summed (ORed) to
    form the complete state=>next-state function for the machine. This
    generalize method also works for the one-hot encoding, but since all
    state values assert a single bit in the state variable, it can be done
    with the simpler method above.

    --

    Rick "rickman" Collins


    Ignore the reply address. To email me use the above address with the XY
    removed.

    Arius - A Signal Processing Solutions Company
    Specializing in DSP and FPGA design URL http://www.arius.com
    4 King Ave 301-682-7772 Voice
    Frederick, MD 21701-3110 301-682-7666 FAX
     
    rickman, Dec 8, 2004
    #2
    1. Advertising

  3. Rick,
    If at State1 and NextState jumps to State2, you don't mention to clear
    State1 register. Am I right or it isn't needed?

    Weng
     
    Weng Tianxiang, Dec 9, 2004
    #3
  4. Inderkal

    rickman Guest

    Weng Tianxiang wrote:
    >
    > Rick,
    > If at State1 and NextState jumps to State2, you don't mention to clear
    > State1 register. Am I right or it isn't needed?


    You cover that by specifying that state1 is continued while there is no
    active condition that *leaves* state1.

    -foo -bar
    +----+ +----+
    | | | |
    V | foo V | bar
    +--> state1 ----------> state2 ---+
    | |
    +---------------------------------+

    So the equation for next_state1 will be:

    next_state1 <= state1 & -foo + state2 & bar;

    next_state2 <= state2 & -bar + state1 & foo;

    If you have more than one exit from a state, the condition for staying
    in the state is the product of all the negated exit conditions.
    statefoo * -bar * -foo * -others

    So just treat staying in a state as another transition.

    --

    Rick "rickman" Collins


    Ignore the reply address. To email me use the above address with the XY
    removed.

    Arius - A Signal Processing Solutions Company
    Specializing in DSP and FPGA design URL http://www.arius.com
    4 King Ave 301-682-7772 Voice
    Frederick, MD 21701-3110 301-682-7666 FAX
     
    rickman, Dec 9, 2004
    #4
  5. Inderkal wrote:
    > Does anybody have any ideas about implementing a gate level model of a


    Gate level model? You mean RTL model? Or do you really want to design at
    gate level?

    > finite state machine? Any kind of info will do. I just want to get
    > started.


    Vending machine, trafic light controller, elevator controller. Use your
    imagination.

    Paul.
     
    Paul Uiterlinden, Dec 9, 2004
    #5
  6. Inderkal

    Inderkal Guest

    Hi Paul,
    I implemented a RTL model for a reed solomon encoder using a state
    machine for my controller. Now I am bringing everything down to gate
    level. The architecture was no problem. but I do not know how to start
    with the controller.
     
    Inderkal, Dec 9, 2004
    #6
  7. Inderkal wrote:
    > Now I am bringing everything down to gate
    > level. The architecture was no problem. but I do not know how to start
    > with the controller.


    Consider using synthesis to make a gate level netlist.

    -- Mike Treseler
     
    Mike Treseler, Dec 9, 2004
    #7
  8. Rick,
    I learn what you say from some textbooks, what you say is right.

    I want to know if you are a professional compiler designer? i.e. if
    what you say is what really most market predominant ASIC compiler
    providers do with the above equations?

    Weng
     
    Weng Tianxiang, Dec 9, 2004
    #8
  9. Inderkal

    rickman Guest

    Weng Tianxiang wrote:
    >
    > Rick,
    > I learn what you say from some textbooks, what you say is right.
    >
    > I want to know if you are a professional compiler designer? i.e. if
    > what you say is what really most market predominant ASIC compiler
    > providers do with the above equations?


    No, I don't write compilers. I use compilers. I don't know how
    compilers work on the inside and I try not to need to. I much prefer to
    write my code to limit what the compiler can do and force a given
    implementation. Writing your equations the way I describe allows you to
    contol the mapping of the equation to hardware if you need to.

    --

    Rick "rickman" Collins


    Ignore the reply address. To email me use the above address with the XY
    removed.

    Arius - A Signal Processing Solutions Company
    Specializing in DSP and FPGA design URL http://www.arius.com
    4 King Ave 301-682-7772 Voice
    Frederick, MD 21701-3110 301-682-7666 FAX
     
    rickman, Dec 9, 2004
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. deejayfred
    Replies:
    0
    Views:
    581
    deejayfred
    Oct 2, 2003
  2. SomeDude
    Replies:
    3
    Views:
    3,217
    arant
    Aug 14, 2006
  3. Roberto Nunnari
    Replies:
    2
    Views:
    8,596
    Thomas Weidenfeller
    Feb 4, 2004
  4. Davide T

    "Tag" Finite State Machine

    Davide T, Dec 10, 2003, in forum: HTML
    Replies:
    5
    Views:
    432
    Eric Bohlman
    Dec 10, 2003
  5. Paul J. Lucas
    Replies:
    0
    Views:
    506
    Paul J. Lucas
    Sep 2, 2003
Loading...

Share This Page