learning vhdl - state machines

Discussion in 'VHDL' started by Al Muliman, Feb 12, 2009.

  1. Al Muliman

    Al Muliman Guest

    Trying to find an accepted way to construct state machines in vhdl, I
    came upon this:

    http://web.engr.oregonstate.edu/~traylor/ece474/new_vhdl_pdfs/state_machines_in_vhdl.pdf

    This is just explanation that I found - I picked this one because it
    seems rather nice.

    One key point seems to be to avoid latches.

    The accepted way to construct state machines would be to have a
    synchronous part that turns the next state into the current and a
    combinatorial part that determines the next state.

    My worry is that the combinatorial part selects a new state with an
    encoding that is "more than one bit away" from that of the current state
    (or any other state that the combinatorial part might otherwise have
    selected) just as the synchronous part flipsflops. In my mind the
    current state might become a mix of the two different states that the
    combinatorial part had to choose from. Is this worry unfounded?

    I am a total fpga noob with a software background mind you.
     
    Al Muliman, Feb 12, 2009
    #1
    1. Advertisements

  2. Al Muliman

    eliascm

    Joined:
    Jan 30, 2009
    Messages:
    42
    Likes Received:
    0
    State Machines

    What should happen in your state machine, as in any synchronous design, is the the combinational changes that start on a clock edge will be stable by the time the next clock edge occurs. The only way this wouldn't happen is that the clock period is so short that the combinational logic changes don't become stable between clock edges. If you set your timing contraints correctly, the FPGA synthesis software will indicate whether or not you will have a timing problem.
     
    eliascm, Feb 12, 2009
    #2
    1. Advertisements

  3. Al Muliman

    Al Muliman Guest

    Jonathan Bromley skrev:
    So... you would separate the clocked and combinational parts of the
    process into a process each and have the two processes share the state
    variables like I see in some of the other examples? I thought it seemed
    handy to just put the two parts in the same process, but I am definately
    trying to learn what is the most accepted practice.
    But... as I understand, the combinational process which selects the next
    state is not clocked at all? So any asynchronous input to the
    combinational process might potentially result in an undesired state
    being clocked past the state FFs due to different delays through the
    various part of the combinational process?

    Forgive me, but I don't have much (you might say "any") understanding of
    what circuitry is generated by the vhdl constructs. I am working on an
    example so I can see for myself but it will be a little while till I get
    there.
    Ok, thanks for the heads up. I will stick with VHDL for now to avoid
    more confusion than what already clouds my mind, but I'm sure I'll do
    good to keep your comment in mind.

    Thank you for your input.
     
    Al Muliman, Feb 12, 2009
    #3
  4. Al Muliman

    Al Muliman Guest

    Okay that was also the solution I had reached on my own before I started
    looking for the True Path. But that means states and outputs are
    registered, right? Inferred... learning new words here. And more logic,
    right? So I might try the combinational approach to see what that could
    do for me.
    I sensed as much, but I am agnostic (and still a bit confused).
    Ah good, I am still on track. Thank you.
    Yes, I know of gray code and learned today that the enumeration types
    typically used for state machines can be "custom encoded":

    attribute enum_encoding: string;
    attribute enum_encoding of state_type:type is "001 010 011 100 101 110 111";

    I suppose the default encoding is 0,1,2,3 etc...
    I recognise the reasoning from software development. It is inevitable
    and possibly necessary. But I should learn.
    It's more like a sense of what's going on than actual awareness. A
    mixture of what little I recall from the lectures I have attended about
    digital design (reduction of karnaugh maps, race conditions and that
    sort), the parallels I can draw from software development and the
    realization that vhdl is nothing like software at all. What happens when
    i write "if rising_edge(clk)" - the inferring that is going an - all
    that I have to learn. I have yet to wrap my mind around functions and
    procedures in vhdl - that I am definately saving for later. Right now I
    just need a lean, mean state machine...

    The topic seems a nice angle to get started on vhdl - I recognise state
    machines from software development, and they are used all the time... in
    vhdl as well as in software I expect.

    I do belive you have answered the questions that bothered me the most.
    Thank you.
     
    Al Muliman, Feb 12, 2009
    #4
  5. Al Muliman

    Andy Guest

    Registered outputs do not always need more logic than combinatorial
    ones (except the register itself, which is almost free in most FPGA
    architectures). In the simplest case, with one-hot state encoding, the
    output is optimized to be just the corresponding bit in the state
    register (whether you are using combinatorial or registered outputs)

    How you code things depends on how you think. If you think of outputs
    being (combinatorially) decoded from states, then to register the
    outputs with the same clock-cycle-based timing (on and off at the same
    time as the states are), you need to assert the output with every
    transition into the state(s) that you would have decoded. That may
    mean more coding, but not usually more resulting logic. I've gotten so
    used to it, it is second nature to me, and I prefer registered outputs
    from state machines (avoids output glitches).

    I use a single, clocked process for the state machine and its outputs.
    It is immune from latches, requires less coding that two processes,
    and simulates more quickly due to modern simulator optimizations
    (mostly noticeable in large designs).

    I also happen to use VHDL variables inside clocked processes, but
    depending on how you think about design, they may help or hinder you.
    Variables behave more like SW (updates are not postponed), and thus
    the clock-cyclic behavior is easier to understand, but mentally
    synthesizing a variable-based description into gates and flops is not
    as easy. It suffices to say that a good synthesis tool will reliably
    synthesize a clocked process into a circuit that behaves, on a clock-
    cyclic basis, like the description simulates, so long as the inputs
    are synchronous to the clock. If you prefer to design with gates and
    flops, then use signals, and maybe even separate combinatorial and
    clocked processes. If you prefer to design with a behavioral
    description and let the synthesis tool do the lifting, use variables
    in clocked processes.
    Not necessarily true. First off, it depends on whether you want grey
    coding to avoid decoding glitches, or you want grey coding to avoid
    erroneous transitions based on asynchronous inputs.

    In a gray coded state machine for asynchronous inputs, the most
    adjacent destinations, including the current state if applicable,
    reachable from the current state is two. If a state machine needs to
    transition from one state to one of two different desitination states
    (without the possibility of waiting in the current state), those two
    destinations must be "adjacent" (hamming distance=1) to each other,
    not to the original state. Thus the transitions are not always
    adjacent, but the destinations are. This is (was, before registers
    became cheap) the typical approach to gray coding state machines:
    State driven transitions are always synchronous, and do not require
    adjacent transitions. Input-driven transitions may not be synchronous,
    and thus need adjacent transitions.

    These were reliable techniques, and still are, from a hardware point
    of view. But from a design review/audit point of view, separately
    synchronizing all state machine inputs is much easier to verify that
    it is done correctly. It also renders worrying about adjacent
    transitions moot, which then makes other, potentially more efficient
    state encodings (e.g. one-hot) usable.

    Andy
     
    Andy, Feb 12, 2009
    #5
  6. I avoid latches and fussing with Gray codes
    by following a single process template
    like the one below.

    main : process (clock, reset) is
    begin -- for details see http://mysite.verizon.net/miketreseler/

    if reset = '1' then -- Assumes synched trailing edge reset pulse
    init_regs; -- reg_v := init_c;
    elsif rising_edge(clock) then
    update_regs; -- reg_v := f(reg_v);
    end if;
    update_ports;
    end process main;

    In my code, counters, state machines, shifters, arbiters etc
    are all described the same way:
    [] a register declaration
    [] a procedure to update the register on every rising clock edge.

    Each process can cover one or more registers.

    -- Mike Treseler
     
    Mike Treseler, Feb 12, 2009
    #6
  7. Al Muliman

    Al Muliman Guest

    Ok I think I need an example now...

    Is this the newfangled pattern for a fsm:

    entity fsm is
    port ( clock : in std_logic;
    reset : in std_logic;
    input : in std_logic);
    end fsm;
    architecture behavioral of fsm is
    type state_type is (THIS, THAT);
    begin
    process (clock, reset)
    variable state : state_type;
    begin
    if (reset = '1') then
    state := THIS;
    elsif rising_edge(clock) then
    -- register inferred on any variables or signals
    -- assigned to inside this elsif section, right?
    -- due to the rising_edge...
    case state is
    -- Can you assign directly to a state variable when it is
    -- registered? Or does it mess the case up?
    -- Those are things I worry about...
    when THIS => if (input = '1') then state := THAT; end if;
    when THAT => if (input = '0') then state := THIS; end if;
    when others => state := THIS;
    end case;
    end if;
    end process;
    end behavioral;

    I like it - one process, a private variable; no polluting the namespace.
    Sorry, software speak. But is this it then?
    That I shall worry about when I start thinking consciously about design.
    Currently I am fumbling in the dark.
    Thank you for clarifying further.
     
    Al Muliman, Feb 12, 2009
    #7
  8. Al Muliman

    Andy Guest

    With signals in a clocked process, any signals assigned represent
    registers.

    With variables, it is different. A reference to a variable can be a
    registered or combinatorial reference, depending on the relative order
    of reading and writing the variable within a given clock cycle. If a
    variable was previously written in the current clock cycle, before it
    is accessed, then THAT REFERENCE to that variable is combinatorial. If
    the variable was not written prior to being accessed, within that
    clock cycle, then that implies that a previous clock cycle's value
    has to be remembered, from which synthesis will infer a register FOR
    THAT REFERENCE. The key is that the reference to the variable
    determines register/combinatorial, not the variable itself. Multiple
    references to the same variable can be combinatorial, registered, or
    even both, in the case of a conditional prior write. In this case the
    same condition that determines the prior write will drive a
    multiplexer to select the registered or combinatorial value to be used
    for that reference.

    Just remember this: the description will behave like the SW reads:
    variable values are updated as soon as the assignment is executed. If
    the description recalls a value stored in a previous clock cycle, then
    a register will be inferred. If the description recalls a value stored
    previously in the current clock cycle, then a combinatorial value is
    inferred.

    In terms of your template, the reference to state occurs right up
    front in the case statement, before state has been written within the
    current clock cycle. So that reference to state is to the output of
    the register that stores state.

    Hope this helps.

    Andy
     
    Andy, Feb 12, 2009
    #8
  9. Al Muliman

    Al Muliman Guest

    It does. Thank you. It also raises new questions, but I have to keep my
    focus.
     
    Al Muliman, Feb 13, 2009
    #9
  10. Al Muliman

    Al Muliman Guest

    Ah the message pump :)
    Yes I think I get what you are saying. But... I still have questions. I
    am going to think about what has already been explained to me here, read
    a little xilinx documentation and work on my own example (state machine
    for writing to the LCD on a Spartan-3E kit). After that I shall return
    with more questions ;-). You have all been most helpfull. Usenet is
    still alive. If you have any pointers on what the internal building
    blocks of an FPGA looks like, I stand a better chance of learning what
    is meant by a register and when the value that a register holds is
    clocked through, and why they come almost free in an FPGA but not so in
    an Asic.
     
    Al Muliman, Feb 13, 2009
    #10
  11. Al Muliman

    Al Muliman Guest

    The Xilinx documentation of the Spartan-3E probably does just fine.
     
    Al Muliman, Feb 13, 2009
    #11
  12. Sorry for jumping into a conversation, but I thought I'd point out that
    you can move the above line... (the type def)
    to here...

    type state_type is (THIS, THAT);
    That's how I do it :)

    And you don't pollute the "type" namespace with state_type either. So
    if you have more than one process in your entity each with a state
    machine, they can have independent 'state_type's.

    If you only have one process per entity (search out Mike Treseler - a
    big one-process-per-entity advocate) it makes no odds as the namespace
    is private to the entity. I should point out, I'm also usually a
    one-process man, but occasionally have two interacting state machines
    in an entity.
    I'd add a vote for variables too :)

    Cheers,
    Martin
     
    Martin Thompson, Feb 13, 2009
    #12
  13. I see you found the userguide - that's what I would've suggested.
    Each look-up table (LUT) in the FPGA has a register associated with it
    (sometimes called a flipflop - FF). Except in extremely highly
    pipelined design you usually have more LUTs used than FFs (my current
    design uses a few hundred more LUTs than FFs), so there's FF aroudn to
    be used without pushing the device size up. They're not entirely free
    in that although they are there, sometimes routing the signal to a
    free flipflop can't be done as the free one is "miles" away from where
    the logic that generates it is. However, usually, you are putting a
    register on some intermediate signal which also goes off to other
    logic, and in those cases, it's easy for the tools to manage.

    HTH!

    Cheers,
    Martin
     
    Martin Thompson, Feb 13, 2009
    #13
  14. Al Muliman

    Al Muliman Guest

    Jump all you like. I thought I had tried to define the types for the
    process only and found it did not work, but now I see that it does.
    Thank you for pointing that out.
    Right. Things I recognise in some form from software.
    That's what I hear from other people as well. So what I have now is a
    single process containing two state machines using only variables for
    maintaning state. Types and variables defined only for the process. All
    variables except one and all signals are registered. I never finished my
    attempt to create a combinatorial process to select next state. This is
    much more concise and I have no worries. First simulation looks correct.
    I am starting to get a feel for the difference between signals and
    variables, but I am still not quite there.
     
    Al Muliman, Feb 13, 2009
    #14
  15. Al Muliman

    Al Muliman Guest

    It does. Thank you.
     
    Al Muliman, Feb 13, 2009
    #15
  16. Al Muliman

    Al Muliman Guest

    And MIA such an FPGA is a complex thing (Looking at a schematic in the
    user guide and pulling my hair).
     
    Al Muliman, Feb 13, 2009
    #16
  17. Al Muliman

    beky4kr Guest




    VHDL supports enumerating (enumerating example) and type variables.
    This allow better readability and allow the simulator to show the
    values with their ASCII meaningfully names on wave....
    h--p://bknpk.no-ip.biz/SDIO/enumerating_1.html
     
    beky4kr, Feb 13, 2009
    #17
  18. Windows 1.0 was in fact a single loop
    with a cycle time of "whatever".
    I had to be careful not to move the
    mouse during boot, or the cycle time became "forever".
    Fortunately for the engineers, only our
    customers had to deal with windows.
    We stayed in emacs running on the vaxen.
    Now you've let the cat out of the bag.
    Luckily my boss doesn't read usenet ;)
    Yes, synthesis works better than most hope to expect.
    Well, it was more concise and useful than
    the average engineering text on the subject.
    Most of the tips my ski instructor gives me
    seem counterintuitive and dangerous.
    Then, much later, something clicks
    and suddenly I get it.

    -- Mike Treseler
     
    Mike Treseler, Feb 14, 2009
    #18
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.