courses:system_design:synthesis:finite_state_machines_and_vhdl:state_coding

State Coding

State Encoding

  • State encoding responsible for safety of FSM
type STATE_TYPE is (START, MIDDLE, STOP);
signal STATE : STATE_TYPE ;
  • Default encoding: binary (may vary with synthesis tools and number of states)
START   -> "00"
MIDDLE  -> "01"
STOP    -> "10"
  • Speed optimized default encoding: one hot
START   -> "001"
MIDDLE  -> "010"
STOP    -> "100"
Problem: after synthesis there exist unvalid values for the signal STATE
if {log2(# of states) ≠ ENTIER[log2(# of states)] } ⇒ unsafe FSM!

Notes

A finite state machine is an abstract description of digital hardware. It is a synthesis requirement that the states of the automaton are described as binary values or the synthesis tool itself will transform the state names into a binary description on his own. This transformation is called state encoding.

Most synthesis tools select a binary code by default, except the designer specifies another code explicitly. The states of the automaton above could be encoded by a synthesis tool with the values “00”, “01” and “10”. However other possibilities of state encoding exist. A frequently used code which is needed for speed optimized circuits is the “one-out-of-n” code which is also called one hot code. Here, one bit is used for every state of the automaton. E.g. if the automat has 11 states, then the state vector contains 11 bits. The bit of the vector which is set to ’1’ represents the current state of the automaton.

A problem arises for the encoding of the states which can not be ignored: If the automat has n states, one needs ENTIER[ld(n)] flip flops for a binary code.

This is the smallest integer value bigger or equal to the result of the binary logarithm of n. In the example above, two flip flops are needed for a binary code. As the automat consists only of 3 states and two flip flops can represent up to 4 states (“00”, “01”, “10”, “11”), there is one invalid state which leads to an unsafe state machine, i.e. the behavior of the design when accidentally entering this state is not determined.

Usually, a mechanism has to be provided which corrects the erroneous entering of an invalid state.

Extension of CASE Statement

  • Adding the “when others“ choice
type STATE_TYPE is (START, MIDDLE, STOP);
signal STATE : STATE_TYPE;
  • • •
   case STATE is
      when START   => • • •
      when MIDDLE  => • • •
      when STOP    => • • •
      when others  => • • •
end case ;
Not stimulatable; in RTL there exist no other values for STATE
Not necessarily safe; some synthesis tools will ignore “when others“ choice

Notes

The most obvious method to intercept invalid states is to insert a ’when others’ branch in the CASE statement. With this branch, all values of the examined expression (here: STATE) that are not included in the other branches of the CASE statement are covered. The intention is to intercept all illegal states and to restart the automaton with its reset state (here: START).

VHDL is a very strict language. Therefore, during simulation, only the values defined by the type definition of a signal can be accessed. For this reason, invalid states do not exist in the simulation and consequently can not be simulated. Furthermore the synthesized circuit is also not necessarily safe. Some synthesis tools ignore the ’when others’ branch as, by definition, there are no values to cover in this branch.

Inserting a ’when others’ branch into the case statement is not a good solution for creating a safe state machine.

Extension of Type Declaration

  • Adding dummy values
type STATE_TYPE is (START, MIDDLE,STOP, DUMMY);
signal STATE : STATE_TYPE;
  •••
  case STATE is
      when START   => •••
      when MIDDLE  => •••
      when STOP    => •••
      when DUMMY   => ••• -- or when others
end case ;
  • Advantages:
    • Now simulatable
    • Safe FSM after synthesis
{2**(ENTIER [ld(n)]) -n} dummy states (n=20 ⇒ 12 dummy states)
Changing to one hot coding ⇒ unnecessary hardware (n=20 ⇒ 12 unnecessary flip flops)

Notes

The second way is to define additional values for the enumeration type. So many values have to be added that after state encoding invalid values can no longer occur. If an automaton contains for example 20 states, 5 flip flops are needed with a binary code. With 5 flip flops one can distinguish 32 values (2^5=32). Thus, 12 additional values have to be added to the enumeration type of the state machine.

By adding additional values to the enumeration type, one gets a state machine whose behavior in case of errors can now be simulated. The synthesis also results in a safe circuit representing the original state machine. However this method is somewhat awkward as one has to insert many so called dummy states eventually. Furthermore, this method is only suitable when binary coding for the states of the automaton is used. If one has added for example these 12 additional values for a safe state machine, he will get 12 redundant flip flops when he switches the state encoding to the one hot code as an extra bit is needed for every state.

It is not advisable to make a state machine safe by inserting additional values for dummy states if a one hot code is used. Every new value would lead to an additional flip flop and therefore would only increase the amount of invalid state values after synthesis.

Therefore the method of inserting additional values into the enumeration type is not a good solution, too, as it is applicable to binary state encoding, only.

Hand Coding

  • Defining constants
subtype STATE_TYPE is
       std_ulogic_vector (1 downto 0);
signal STATE : STATE_TYPE;
 
constant START   : STATE_TYPE := "01";
constant MIDDLE  : STATE_TYPE := "11";
constant STOP    : STATE_TYPE := "00";
•••
   case STATE is
      when START   => •••
      when MIDDLE  => •••
      when STOP    => •••
      when others  => •••
   end case;
  • Control of encoding
  • Safe FSM
  • Simulatable
  • Portable design
  • More effort

Notes

The best method of state encoding is hand coding, i.e. the designer decides by himself which code will be used.

This is done by using a vector type instead of an enumeration type. This vector type can based upon the ’std_(u)logic_vector’ type for example. The width of this vector depends on the code chosen. The state signal is now of this vector type, which is the reason for the term “state vector”.

In the next step, constants are defined which represent the corresponding states of the automaton. These constants are set to the state vector values according to the selected code. With these constants, the code can be fixed by the designer and can not be altered by the synthesis tool. This VHDL model is also 100 percent portable. The behavior in case of errors can be verified in a simulation as the state vector can assume all values that might occur in real hardware, now.

The only drawback to mention is a little more effort in writing the VHDL code. This is especially true when the code is changed. The hand coding alternative is the best method to design a safe finite state machine and is furthermore portable among different synthesis tools.

Chapters of System Design > Synthesis > Finite State Machines and VHDL

Chapters of System Design > Synthesis