Counting in state-machines

[Harvs]

This may sound like a bit of a noob question, but here goes anyway.

When one has a state machine that effectively goes through a linear series of steps, I've seen (and used) a couple of different methods for counting within states.

One being where a counter is separated from the state logic, with a bunch of control signals between.  In most examples of this I've seen it can end up extremely obfuscated.

Another being counter's placed within the states themselves (i.e. within branches of the case statement.) This is far less obfuscated, but can end up with quite a few small counters.

The other way I've used recently that I picked up somewhere (I'm thinking the zipcpu website, but I could be wrong) is to use a single counter, then ranges within the case statement.  This is very clean from a code perspective, and uses only a single counter, but I can't help but wonder if it's a good idea since the synthesis step outputs two full width comparators for every range.  So given the very simple pseudo-code below for a qspi transaction there's 6x 6-bit greater than comparators out of ISE.  Maybe this is a non-issue?

I guess I'm wondering if there's a consensus on how this should be coded for FPGA implementation?

case (state) is
 when 0 =>
  -- waiting for input
 when 1 =>
 -- start bit
 when 2 to 9 =>
 -- shift out command byte
 when 9 to 14 =>
 -- dummy bytes
 when 15 to 39 =>
 -- High 'z' IO
 -- shift in data

[langwadt]

many ways to skin a cat

I guess you could by default increment the state and only have the cases states that change something
you could do the state as one-hot

I often use a single loadable counter decrementing when it is not zero

[tggzzz]

FSM state encoding is a standard topic. There are different implementation techniques depending on what you want to optimise.

The classic tradeoffs are "speed" vs "space", with the latter being subdivided into sequential and combinatorial  and routing resources. There is another consideration that can sometimes be relevant: the ability to detect and recover from "should never occur" conditions.

So, the answer depends on how much you are pushing the speed, and the proportion of resources you are using.

Starting points:

• look at the application notes supplied by your device manufacturer. If none, look at Xilinx's app notes.
  
• search for "one hot", and fan out from there

[AndyC_772]

The one method I certainly wouldn't use is the one you've shown in your example. If you want to change the number of clock cycles for which the logic remains in one state, you also have to change the conditions to be in every subsequent state, and that's wasted effort and a chance for bugs to creep in.

A better solution (IMHO, of course!) is to have a single counter which records the amount of time spent since the last change of state. Zero said counter each time you assign a new value to the state variable.

[NivagSwerdna]

many ways to skin a cat

^ this

It might be a good decision to do it this way.... alternatively state machines are often arranged in a hierarchy so you could have child state machines for each of the chunks of state if you see what I mean.  Sometimes having something inefficient in space can be efficient in time etc... trade offs... swings and roundabouts etc... 

[hamster_nz]

The one method I certainly wouldn't use is the one you've shown in your example. If you want to change the number of clock cycles for which the logic remains in one state, you also have to change the conditions to be in every subsequent state, and that's wasted effort and a chance for bugs to creep in.

A better solution (IMHO, of course!) is to have a single counter which records the amount of time spent since the last change of state. Zero said counter each time you assign a new value to the state variable.

Or maybe better, have the counter count down towards zero, then when zero assign the new state value and the new starting point for the counter

(in no particular language)

Code: [Select]

     count--;  -- Always decrement the counter.
     switch(state)
         state_a:
              if count = 0:
                  state = state_b;
                  count = 99
         state_b:
              if count = 0:
                  state = state_c;
                  count = 149
         state_c:
              if count = 0:
                  state = state_a;
                  count = 19             

It tends to give tighter, less resource hungry logic because you only test against zero, not a lot of different terminal counts.

[Harvs]

Thanks, interesting points. 

As much as FSM encoding is a standard topic, I've read many texts that provide some questionable advice for anything beyond trivial examples.  So it's interesting to hear what people in industry are doing.

[SiliconWizard]

Very general: if the "counters" for states that require mutiple cycles are relatively small, the most efficient way (in terms of speed and area) is likely to use multiple states, as you more or less showed in your example. But that's likely true only for a limited number of overall states; beyond a certain number, FSMs will become inefficient when synthesized.

Still, one drawback of doing this is that it makes your code hard to maintain if you ever need to modify the individual "counters" or make them generic. Likewise, it more or less forces you to use integers as states rather than identifiers, which also makes code harder to read and harder to maintain.

So, my personal view on this is: unless you know the number of counts will forever be fixed and is small, don't do it.

If you want to do this and make code easier to maintain, at least use constants instead of hard-coded values for the states in your 'case' statements. Declare those constants with a clear identifier, and each computed from the previous "state", so it becomes much easier to read and maintain. Pretty please avoid using hard-coded values.

[NorthGuy]

... how this should be coded for FPGA implementation?

Doesn't really matter.

If you take the model posted by the OP, then renumber states (as the tools will do anyway) so that they're aligned, such as

Code: [Select]

0, 32 to 39, 64 to 69, 96 to 120 etc
instead of

Code: [Select]

1,2 to 9, 9 (???) to 14, 15 to 39
then you can regard the state as a concatenation of the two numbers - lower 5 bits represent the counter, and the higer bits represent the state proper. This way you'll arrive to the exact solution offered by AndyC_772, so these two are in fact the same.

The method offered by hamster_nz doesn't differ much neither. It always compares to zero, but different states have to load different counters, while AndyC_772 has to compare to different end numbers, but always loads zero. Both should bring similar performance.

The difference is in what you write, not what you're going to get. And that is totally matter of your preference.

[AndyC_772]

Bear in mind also that the logic occupied by the implementation of the FSM itself is likely to be minimal compared to the logic that actually performs useful functions in each state.

If your design is 95% useful functionality and 5% FSM and counters, concentrate on making that 5% as readable and easy to maintain as you can. Unless you've somehow ended up with a device that's too small, and are desperately struggling to squeeze in every last gate, you just don't need to worry about making the control logic space efficient.

[Bassman59]

Like others have suggested, for state sequencers I like to use something along these lines:

Code: [Select]

    constant MAXTIME : natural := 1000; -- or whatever
    subtype duration_t is natural range 0 to MAXTIME;
    signal duration : duration_t;

    type statetimes_t is record
        state1 : duration_t;
        state2 : duration_t;
        state3 : duration_t;
    end record statetimes_t;

    -- Initialize this elsewhere. Maybe from flash? Hpwever you want!
    signal statetimes : statetimes_t;

sequencer : process (clk, rst_l) is
begin
    if rst_l = '0' then
        state <= S_IDLE;
        duration <= 0;
        outputs <= (others => '0';);
    elsif rising_edge(clk) then

        -- This sets the time we spend in any particular state which watches duration.
        StateTime : if duration > 0 then
            duration <= duration - 1;
        end if StateTime;

        Decoder : case (state) is
            when S_IDLE =>
                outputs <= O_IDLE; -- define somewhere.
                if trigger = '1' then
                    duration <= statetimes.state1;
                    outputs <= O_S1; -- define somewhere
                    state <= S_STATE_1;
                end if;

            when S_STATE_1 =>
                if duration = 0 then
                    duration <= statetimes.state2;
                    outputs <= O_S2;
                    state <= S_STATE_2;
                end if;
 
            when S_STATE_2 =>
                if duration = 0 then
                    duration <= statetimes.state3;
                    outputs <= O_S3;
                    state <= S_STATE_3;
                end if;

            when S_STATE_3 =>
                if duration = 0 then
                    outputs <= O_S4;
                    state <= S_STATE_4;
                end if;

            when S_STATE_4 =>
                outputs <= O_IDLE;
                state <= S_IDLE;
        end case Decoder;
    end if;
end process sequencer;
The cool things about this idiom are:

1. The record holds the duration of each state. If you add more states that need such timing, add another entry to the record.

2. The length of each state in the table can be stored in non-volatile memory and recalled as needed, and it can be updated from a command parser or such. Or you could just make them constants.

3. It takes advantage of VHDL's "last assignment wins" so the duration timer doesn't need explicit load or count enables. Each state loads the new time and then the timer just counts down to zero from that value. (The synthesizer will build a big mux in front of the timer for all of the load values.)

4. Compares to zero are "faster" than compares to register outputs, so we always count down and compare to zero to see when our state ends.

5. Any state that doesn't require such timing/duration control need not implement it. State 4 above is an example.

As others have noted, there are many ways to do this.

[langwadt]

The one method I certainly wouldn't use is the one you've shown in your example. If you want to change the number of clock cycles for which the logic remains in one state, you also have to change the conditions to be in every subsequent state, and that's wasted effort and a chance for bugs to creep in.

A better solution (IMHO, of course!) is to have a single counter which records the amount of time spent since the last change of state. Zero said counter each time you assign a new value to the state variable.

Or maybe better, have the counter count down towards zero, then when zero assign the new state value and the new starting point for the counter

(in no particular language)

Code: [Select]

     count--;  -- Always decrement the counter.
     switch(state)
         state_a:
              if count = 0:
                  state = state_b;
                  count = 99
         state_b:
              if count = 0:
                  state = state_c;
                  count = 149
         state_c:
              if count = 0:
                  state = state_a;
                  count = 19             

It tends to give tighter, less resource hungry logic because you only test against zero, not a lot of different terminal counts.

and if you want to be cute you can put the zero check outside

Code: [Select]

 
    if(count != 0)
     count--; 
    else
     switch(state)
         state_a:
                  state = state_b;
                  count = 99
         state_b:
                  state = state_c;
                  count = 149
         state_c:
                  state = state_a;
                  count = 19             


[Harvs]

Like others have suggested, for state sequencers I like to use something along these lines:

I like it, very clean.