State Machine Design & VHDL Coding
This section gives an overview of how to describe state machines with VHDL, it assumes some prior knowledge of state machine design.
Translating the state diagram to VHDL
The starting point for most state machine designs is a state flow diagram which shows the various states and the transitions between them. It can also show any outputs that are generated when the state machine is in a particular state. An example is shown below:
Example state machine - The state machine is clocked by a signal 'clk' which is not shown on the flow diagram.
What information is important to us?
- We need to know how the state machine will be clocked - using which signal and on which edge, rising or falling.
- We need to know how the state machine will be initialized - using which signal, asynchronously or synchronous to the clock, active high or active low and the initial state itself.
- We need to interpret the state diagram to decide the state transition conditions.
- We need to choose a state assignment (or state encoding) - this will impact the number of flip-flops required & the speed (i.e. maximum clock frequency that can be employed).
Defining the clock
A state machine advances from one state to another when the particular state transition conditions are satisfied, synchronous to the state machine's clock input. This can be implemented in a process with the clock signal in the sensitivity list. The process will only be activated by events on the clock signal (clk) ensuring all signal and variable changes are synchronized to the clock.
state_machine : PROCESS (clk)
BEGIN
IF (clk'EVENT AND clk = '1') THEN -- sync to clk rising edge
-- state transitions go here
END IF;
END PROCESS state_machine;
All statements enclosed within IF (clk'EVENT AND clk='1') THEN...END IF; will only be evaluated when the (clk'EVENT AND clk='1') condition is true, i.e. when a rising edge occurs on the clk signal. Your synthesis tool should interpret this as positve edge clocked registers.
Alternatively, a WAIT statement could be used, in which case a sensitivity list is not specified:
state_machine : PROCESS BEGIN WAIT UNTIL (clk'EVENT AND clk = '0'); -- sync to clk falling edge -- state transitions here END PROCESS state_machine;
All statements enclosed within WAIT UNTIL (clk'EVENT AND clk='0')...END PROCESS state_machine; will only be evaluated when the (clk'EVENT AND clk='0') condition is true, i.e. when a falling edge occurs on the clk signal.
Your synthesis tool should interpret this as negative edge clocked registers (and will probably need to invert your clock signal).
Note that in the first of these examples, the rising edge of clk is used to clock the state machine, in the second the falling edge is used. (see the section on signal attributes for more information).
Synchronous & asynchronous initialization
Some sort of initialization is usually necessary as the power-up state of the flip-flops may not be defined or a pushbutton reset may be included on the pcb. For simulation, std_logic type signals and variables will default to 'U' (uninitialized) if there is no explicit initialization.
Let's look at synchronous initialization first and assume that that the state machine must transition to the initial state from any other state when the reset input is low. Using the template that we developed earlier:
state_machine : PROCESS (clk)
BEGIN
IF (clk'EVENT AND clk = '1') THEN -- sync to clk rising edge
IF (reset = '0') THEN
state_vector <= idle;
ELSE
-- state transitions here
END IF;
END IF;
END PROCESS state_machine;
The reset signal has not been included in the process sensitivity list, so events on the reset signal will not activate the process - it's still only the clock that activates the process. The second IF condition is only evaluated when a rising edge occurs on the clk signal, i.e. synchronous reset. The state_vector is either a VHDL signal or variable and it is assigned the value idle when the reset signal is '0' at a rising clock edge. What exactly state_vector and idle are will be decided by the state assignments that we choose.
Now for the asynchronous initialization. This time the reset signal must be included in the process sensitivity list as the state machine must respond to events on both the clk signal and the reset signal - so an event on either signal will activate the process.
state_machine : PROCESS (clk,reset)
BEGIN
IF (reset = '0') THEN -- asynch active low reset
state_vector <= idle; -- to idle state on reset
ELSIF (clk'EVENT AND clk = '1') THEN -- sync to clk rising edge
-- state transitions here
END IF;
END PROCESS state_machine;
Note that the reset has priority over the clock implicitly due to the fact that the IF statement is evaluated in sequential order and hence the initialization condition is checked first - if it evaluates to TRUE the state_vector will be assigned the value idle regardless of the value of clk.
State transitions
The templates we have developed so far allow us to define where our example state machine will start from (the initial state is idle) and when the state transitions will take place (synchronous with the rising or falling edge of clk). We now need to define the conditions that cause the state transitions to happen. Examining the example state diagram above we see that :
- The state machine will go to the idle state whenever reset is '0' (i.e. asynchronous).
- It will stay in idle until start is '0' then it will pass to state1.
- From state1, it will pass into state2 if branch is '0', if branch is '1' it will pass into state4.
- From state2, it will pass into state3.
- From state3, it will pass into state4 if hold is '0', otherwise it will stay in state3.
- From state4, it will pass into state5.
- From state5, it will pass into idle.
The generally accepted method of coding a state flow is by using a CASE...WHEN construct with one WHEN for each state. The transition conditions for each state are described by IF...THEN...ELSE statements. The VHDL process will now look like this:
state_machine : PROCESS (clk,reset)
BEGIN
IF (reset='0') THEN -- asynch active low reset
state_vector <= idle; -- to idle state on reset
ELSIF (clk'EVENT AND clk='1') THEN -- sync to clk rising edge
-- state transitions
CASE state_vector IS
WHEN idle => -- when in idle..
IF (start = '0') THEN -- ..wait for start=0
state_vector <= state1; -- ..then go to state1
ELSE
state_vector <= idle; -- ..else stay in idle
END IF;
WHEN state1 => -- in state 1..
IF (branch = '1') THEN -- ..if branch=1
state_vector <= state4; -- ..then go to state4
ELSE
state_vector <= state2; -- ..else go to state2
END IF;
WHEN state2 =>
state_vector <= state3; -- go to state3
WHEN state3 =>
IF (hold = '0') THEN -- ..if hold=0
state_vector <= state4; -- ..then go to state4
ELSE
state_vector <= state_vector; -- ..else stay in state3
END IF;
WHEN state4 =>
state_vector <= state5; -- go to state5
WHEN state5 =>
state_vector <= idle; -- go to idle
WHEN OTHERS => -- all other vector values
state_vector <= idle; -- ..go to idle
END CASE;
END IF;
END PROCESS state_machine;
The last remaining step is to choose values for the states.
Manual State encoding
Note : State encoding is also known as state assignment and the term 'explicit' is sometimes used instead of 'manual'.
Binary encoding
Using binary encoding, each state is assigned a unique binary number. Since our example has 6 states, we will require 3 bits to fully encode it and we will choose to assign the value "000" to idle, "001" to state1, "010" to state2 and so on. There is no strict reason to use this assignment order, but assigning "000" to idle (the initial state) makes sense as the flip-flops inside most types of FPGA will power-up already cleared (i.e. at logic '0') or will be cleared by their reset input. (this restriction does not apply to Xilinx FPGAs). The state encodings are explicitly declared as constants, either in the architecture declarative section or in the process declarative section or in a separate VHDL package - however declaring them in the architecture declarative section is more usual as they generally need only be visible inside the architecture where the state machine process resides. If they need to be visible outside of the architecture (i.e. used by other design entities), then a package can be used.
ARCHITECTURE arc_bincoded OF bincoded IS -- sequential binary state machine encoding CONSTANT idle : std_logic_vector(2 DOWNTO 0) := "000"; CONSTANT state1 : std_logic_vector(2 DOWNTO 0) := "001"; CONSTANT state2 : std_logic_vector(2 DOWNTO 0) := "010"; CONSTANT state3 : std_logic_vector(2 DOWNTO 0) := "011"; CONSTANT state4 : std_logic_vector(2 DOWNTO 0) := "100"; CONSTANT state5 : std_logic_vector(2 DOWNTO 0) := "101"; BEGIN
Gray encoding
This is a form of binary encoding in which only one bit of the state vector changes when moving from state to state so that the state vector doesn't pass through any intermediate values - important if it's being decoded asynchronously elsewhere in the FPGA. The states are then known as "adjacent states". The VHDL code for the state assignments is similar to the binary coding:
ARCHITECTURE arc_graycoded OF graycoded IS -- gray state machine encoding CONSTANT idle : std_logic_vector(2 DOWNTO 0) := "000"; CONSTANT state1 : std_logic_vector(2 DOWNTO 0) := "100"; CONSTANT state2 : std_logic_vector(2 DOWNTO 0) := "101"; CONSTANT state3 : std_logic_vector(2 DOWNTO 0) := "111"; CONSTANT state4 : std_logic_vector(2 DOWNTO 0) := "110"; CONSTANT state5 : std_logic_vector(2 DOWNTO 0) := "010"; BEGIN
Enumerated type
First an enumeration type 'states' is declared whose range of possible values are the names of the states in the state machine. Then the state vector is declared as a signal of type states:
ARCHITECTURE arc_enumtype OF enumtype IS -- enumerated type state machine encoding TYPE states IS (idle,state1, state2, state3, state4, state5); SIGNAL state_vector : states; BEGIN
It is not immediately clear from this exactly how many bits are required to encode all the states (i.e. exactly how many bits are required for the state vector) and what the state encoding will be. Most VHDL compilers will correctly synthesise the required number of bits and default to a sequential binary state assignment, ie. "000", "001"...."101" as in our binary encoding example.
The default state encoding can be overidden by using the enum_encoding attribute:
ARCHITECTURE arc_enumtype OF enumtype IS -- enumerated type state machine encoding TYPE states IS (idle,state1, state2, state3, state4, state5); ATTRIBUTE enum_encoding : string; ATTRIBUTE enum_encoding OF states : TYPE IS "000 100 101 111 110 010"; SIGNAL state_vector : states; BEGIN
This will assign the values "000"; to idle, "100" to state1, etc. The state assignment in this example is gray coded and the synthesis results are the same as the gray encoding example. This technique could be applied equally well to the binary coding scheme.
One-hot encoding (state-per-bit)
The one-hot encoding technique was developed as a consequence of the typical FPGA architecture - rich in registers but with limited fan-in to each internal logic block. It is sometimes known as state-per-bit encoding as the state vector has one bit for each state in the state machine. For more information, see the One-hot state machine & VHDL coding section.
Automatic State Assignment
Some VHDL synthesis tools will allow the state encoding scheme to be selected automatically using a 'synthesis directive' which takes the form of a VHDL attribute. For example, the Metamor compiler will automatically generate a one-hot encoded state machine if the following code is included:
ARCHITECTURE arc_onehot OF onehot IS -- enumerated type state machine encoding TYPE states IS (idle,state1, state2, state3, state4, state5); ATTRIBUTE enum_encoding OF states : TYPE IS "one hot"; SIGNAL state_vector : states; BEGIN
Refer to the documentation supplied with the VHDL synthesis tool you are using.
Two process style
So far all the examples have used a single process to describe the state machine. A popular coding style is to use two processes, a combinatorial process and a synchronous process. In the combinatorial process, the state transition conditions are described in terms of the present state (and any inputs) and in the synchronous process the clocking is defined. Using this style for our example state machine (with asynchronous initialization and explicit binary state encoding) gives :
ARCHITECTURE arc_twoproc OF twoproc IS
-- sequential binary state machine encoding
CONSTANT idle : std_logic_vector(2 DOWNTO 0) := "000";
CONSTANT state1 : std_logic_vector(2 DOWNTO 0) := "001";
CONSTANT state2 : std_logic_vector(2 DOWNTO 0) := "010";
CONSTANT state3 : std_logic_vector(2 DOWNTO 0) := "011";
CONSTANT state4 : std_logic_vector(2 DOWNTO 0) := "100";
CONSTANT state5 : std_logic_vector(2 DOWNTO 0) := "101";
SIGNAL present_state : std_logic_vector(2 DOWNTO 0);
SIGNAL next_state : std_logic_vector(2 DOWNTO 0);
BEGIN
-- the combinatorial process
comb_proc : PROCESS (present_state,start,branch,hold)
BEGIN
-- state transitions
CASE present_state IS
WHEN idle => -- when in idle ..
IF (start = '0') THEN -- ..wait for start=0
next_state <= state1; -- ..then go to state1
ELSE
next_state <= idle; -- ..else stay in idle
END IF ;
WHEN state1 => -- in state 1..
IF (branch = '1') THEN -- ..if branch=1
next_state <= state4; -- ..then go to state4
ELSE
next_state <= state2; -- ..else pass to state2
END IF ;
WHEN state2 =>
next_state <= state3; -- go to state3
WHEN state3 =>
IF (hold = '0') THEN -- ..if hold=0
state_vector <= state4; -- ..then go to state4
ELSE
state_vector <= state_vector; -- ..else stay in state3
END IF ;
WHEN state4 =>
next_state <= state5; -- go to state5
WHEN state5 =>
next_state <= idle; -- go to idle
WHEN OTHERS => -- all other vector values
next_state <= idle; -- ..go to idle
END CASE;
END PROCESS comb_proc;
-- the synchronous process
sync_proc : PROCESS (clk,reset)
BEGIN
IF (reset = '0') THEN -- async active low reset
present_state <= idle; -- to idle state on reset
ELSIF (clk'EVENT AND clk = '0') THEN -- sync to clk falling edge
present_state <= next_state; -- change state
END IF ;
END PROCESS sync_proc;
END ARCHITECTURE arc_twoproc;
Synchronous initialization of two process state machine
To implement a synchronous initialization in a two process state machine, just change the synchronous process as follows:
-- the synchronous process
sync_proc : PROCESS (clk)
BEGIN
IF (clk'EVENT AND clk = '0') THEN -- sync to clk falling edge..
IF (reset = '0') THEN -- async active low reset
present_state <= idle; -- to idle state on reset
ELSE
present_state <= next_state; -- ..change state
END IF;
END IF;
END PROCESS sync_proc;
END ARCHITECTURE arc_twoproc;
Using WHEN OTHERS
The CASE statements used in our examples all include the WHEN OTHERS condition which defines the state machine action when the state vector has a value that is not covered by the state assignments - the state machine is in an illegal state. This can happen in real-world design due to such things as noise, power glitches or flip-flop setup and hold violations.
The designer can choose to make the state machine 'fault tolerant' by forcing the state machine to a legal state (usually the initial state) whenever it is in an illegal state using the WHEN OTHERS as follows:
WHEN OTHERS => -- all other vector values next_state <= idle; -- ..go to idle
This however consumes a lot more logic resources. If fault recovery is not required then the designer can choose to define the uncovered values as 'don't care':
WHEN OTHERS => -- all other vector values next_state <= (OTHERS =>'-'); -- ..don't care
This will allow the logic synthesis tool to minimize the state transition equations. Note that there must be one '-' for each bit in the state vector.
The WHEN OTHERS condition may also be needed for simulation even if all the states have been assigned - the state vector is usually defined as being a std_logic_vector type, and so each bit in the state vector has 9 possible values, not just '1' or '0'.
Generating other outputs
Most state machines are used to generate other outputs, not just the state vector itself. These other outputs are generated either from the state vector only (Moore machine) or from a combination of the state vector and other inputs (Mealy machine).
As an example, we will generate two outputs from our example state machine; out1 will be active high in state2 and state3 and out2 will be active high in state3 if an additional input, in1, is active high. The timing is shown below:
The outputs can be generated in one of several ways :
As a combinatorial function of the present state vector and the inputs
The output decoding logic introduces an extra propagation delay between the clock edge and the output signals. Assuming that the rising edge of clk is used to clock the present state registers (i.e. the state vector) then the clock edge to output delay is as shown below:
The total delay from the rising clock edge to when the output changes state is made up of the delay from the clock edge to when the state vector changes state (Tco) plus the propagation delay in the output decoding logic (Tpd).
If the state machine has been coded in the single process style, the state vector must be declared as a signal (so that it's visible outside the process), and then the outputs can be generated using a conditional signal assignment (WHEN...ELSE):
out1 <= '1' WHEN ((state_vector=state2) OR (state_vector=state3))
ELSE '0';
out2 <= '1' WHEN (in1='1' AND state_vector=state3)
ELSE '0';
If the two process style has been used, the output assignments can be placed inside a separate combinational process (i.e. a third process), with a signal assignment in each WHEN clause:
-- the output combinatorial process
out_comb_proc : PROCESS (present_state)
BEGIN
-- state transitions
CASE present_state IS
WHEN idle =>
out1 <= '0';
out2 <= '0';
WHEN state1 =>
out1 <= '0';
out2 <= '0';
WHEN state2 =>
out1 <= '1'; -- out1 goes active
out2 <= '0';
WHEN state3 =>
out1 <= '1'; -- out1 still active
out2 <= in1; -- out1 goes active if in=1
WHEN state4 =>
out1 <= '0';
out2 <= '0';
WHEN state5 =>
out1 <= '0';
out2 <= '0';
WHEN OTHERS =>
out1 <= '0';
out2 <= '0';
END CASE;
END PROCESS out_comb_proc;
As a synchronous function of the present state vector and the inputs.
This is best described using a multi-process style as the code for the outputs can be kept seperate from the code for the state vector.
ARCHITECTURE arc_decpstate OF decpstate IS
-- sequential binary state machine encoding
CONSTANT idle : std_logic_vector(2 DOWNTO 0) := "000";
CONSTANT state1 : std_logic_vector(2 DOWNTO 0) := "001";
CONSTANT state2 : std_logic_vector(2 DOWNTO 0) := "010";
CONSTANT state3 : std_logic_vector(2 DOWNTO 0) := "011";
CONSTANT state4 : std_logic_vector(2 DOWNTO 0) := "100";
CONSTANT state5 : std_logic_vector(2 DOWNTO 0) := "101";
SIGNAL present_state : std_logic_vector(2 DOWNTO 0);
SIGNAL next_state : std_logic_vector(2 DOWNTO 0);
SIGNAL next_out1 : std_logic;
SIGNAL next_out2 : std_logic;
BEGIN
-- the next state combinatorial process
state_comb_proc : PROCESS (present_state,start,branch,hold)
BEGIN
-- state transitions
CASE present_state IS
WHEN idle => -- when in idle ..
IF (start = '0') THEN -- ..wait for start=0
next_state <= state1; -- ..then go to state1
ELSE
next_state <= idle; -- ..else stay in idle
END IF;
WHEN state1 => -- in state 1..
IF (branch = '1') THEN -- ..if branch=1
next_state <= state4; -- ..then go to state4
ELSE
next_state <= state2; -- ..else pass to state2
END IF;
WHEN state2 =>
next_state <= state3; -- go to state3
WHEN state3 =>
IF (hold = '0') THEN -- ..if hold=0
next_state <= state4; -- ..then go to state4
ELSE
next_state <= next_state; -- ..else stay in state3
END IF;
WHEN state4 =>
next_state <= state5; -- go to state5
WHEN state5 =>
next_state <= idle; -- go to idle
WHEN OTHERS => -- all other vector values
next_state <= idle; -- ..go to idle
END CASE;
END PROCESS state_comb_proc;
-- the next output combinatorial process
out_comb_proc : PROCESS (present_state, hold)
BEGIN
-- output transitions
CASE present_state IS
WHEN idle =>
next_out1 <= '0';
next_out2 <= '0';
WHEN state1 =>
next_out1 <= '1';
next_out2 <= '0';
WHEN state2 =>
next_out1 <= '1';
next_out2 <= in1;
WHEN state3 =>
IF (hold = '1') THEN
next_out1 <= '1';
next_out2 <= in1;
ELSE
next_out2 <= '0';
next_out1 <= '0';
END IF;
WHEN state4 =>
next_out1 <= '0';
next_out2 <= '0';
WHEN state5 =>
next_out1 <= '0';
next_out2 <= '0';
WHEN OTHERS =>
next_out1 <= '0';
next_out2 <= '0';
END CASE;
END PROCESS out_comb_proc;
-- the synchronous process
sync_proc : PROCESS (clk,reset)
BEGIN
IF (reset = '0') THEN -- async active low reset
present_state <= idle; -- to idle state on reset
out1 <= '0'; -- set out1 low on reset
out2 <= '0'; -- set out2 low on reset
ELSIF (clk'EVENT AND clk = '0') THEN -- sync to clk falling edge..
present_state <= next_state; -- ..change state
out1 <= next_out1; -- ..change output out1
out2 <= next_out2; -- ..change output out2
END IF;
END PROCESS sync_proc;
END ARCHITECTURE arc_decpstate;
The main advantage of a state machine implemented in this way, is that the time delay from the clock edge to when the outputs change state is the same as that for the state vector :
However the outputs can only change state when a clock edge occurs.
One disadvantage of this coding style can be seen by examining the output combinatorial process:
WHEN state1 =>
next_out1 <= '1';
next_out2 <= '0';
Our original specification for the outputs required out1 to go active high in state2, but the above code snippet seems to indicate that it goes high in state1, but what the code is really "saying" is that when the state vector changes from state1 to state2, then the signal out1 is assigned the value of the signal next_out1. We can overcome this slight difficulty by using the next state vector instead of the present state.
As a synchronous function of the next state vector and the inputs
This is essentially the same as the previous coding style (and produces the same timing) but avoids the problem of outputs being specified with the states preceding the one in which they are actually active. The only change to the code is in the outputs combinatorial process. The next state vector (next_state)is now included in the sensitivity list instead of the present state vector:
-- the next output combinatorial process
out_comb_proc : PROCESS (next_state, in1)
BEGIN
-- output transitions
CASE next_state IS
WHEN idle =>
next_out1 <= '0';
next_out2 <= '0';
WHEN state1 =>
next_out1 <= '0';
next_out2 <= '0';
WHEN state2 =>
next_out1 <= '1';
next_out2 <= '0';
WHEN state3 =>
next_out1 <= '1';
next_out2 <= in1;
WHEN state4 =>
next_out1 <= '0';
next_out2 <= '0';
WHEN state5 =>
next_out1 <= '0';
next_out2 <= '0';
WHEN OTHERS =>
next_out1 <= '0';
next_out2 <= '0';
END CASE;
END PROCESS out_comb_proc;
The other difference that can be seen is for the output generation in state3:
WHEN state3 =>
next_out1 <= '1';
next_out2 <= in1;
The next state vector is generated from the present state vector and the start, branch and hold inputs - so the code to generate the outputs when the next state vector is state3 isn't qualified with hold.
Maintained by Mark Harvey. Please email me with any comments.