How to Implement a Finite State Machine in VHDL

What is a Finite State Machine or FSM?

Which can be an effective and elegant way to describe a control logic? Which strategies would you use?

One possibility is trivial: start writing your control logic with a series of “if then else” or “case” statement.

Definitely, not an elegant method but in some ways could perhaps be efficient if you are particularly skilled at simplifying the description of your control logic.

Another possibility is to use a Finite State Machine (FSM).

A finite state machine is simply a method that allows you to carry out a control logic in a simple and efficient way.

Different types of Finite State Machine

There are two different main types of finite state machines the Mealy FSM and the Moore FSM.

The fundamental difference between these two types lies in the management of the outputs:

  • The output of the Mealy FSM depends on the present state and inputs.
  • The outputs of a Moore machine depend only on the present state and not on the inputs.

Figure 1 shows the Mealy FSM.

Figure 1 – Mealy FSM schematic view

Figure 2 schematizes the Moore FSM.

Moore FSM schematic view
Figure 2 – Moore FSM schematic view

The Moore FSM  are preferable to the Mealy FSM since the output of the Moore FSM depends only on the current machine state. No assumptions or check on the inputs have to be performed to generate the output of the FSM, so the output decoding is simpler to handle.

Moreover, if the output is combinatorial, i.e. not registered, the Moore FSM is safer w.r.t Mealy FSM: the long combinatorial path between input and output can generate glitch on the machine output or can reduce dramatically the design timing performances.

Here below in Figure 3, is reported a visual representation of a simple Moore Finite State Machine;

Visual Representation of FSM
Figure 3 – Visual Representation of FSM

The circles represent the states. The transition from one state to another state is represented by the connection arrows. In order to move from a current state to the next one the condition, on the connection arrow, shall be verified. If no condition is present on the connection arrow the next state will be the current state after a clock cycle.

In order to visualize the FSM output, a rectangle containing the FSM output can be added to the diagram as in Figure 4

Visual Representation of FSM with output state
Figure 4 – Visual Representation of FSM with output state

 


How to write the VHDL code for Moore FSM

If you represent your FSM with a diagram like the one presented in Figure 3 or Figure 4, the VHDL FSM coding is straightforward and can be implemented as a VHDL template. We can use three processes as in Figure 2 :

  • Clocked Process for driving the present state;
  • Combinatorial Process for the next state decoding starting from the present state and the inputs;
  • Clocked or combinatorial Process driving the FSM output.

The FSM can be also encoded with a single process, but the FSM VHDL template proposed is used to make the code more linear and readable. For example, you can find the similar template in the Xilinx XST user guide page 250.

Note that the present state is stored in registers while the next state is completely combinatorial.

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity control_logic is
 port (
  i_clk       : in  std_logic;
  i_rstb      : in  std_logic;
  -- input
  i_input1    : in  std_logic;
  i_input2    : in  std_logic;
  -- output
  o_output1   : out std_logic;
  o_output2   : out std_logic;
  o_output3   : out std_logic);
end control_logic;

architecture rtl of control_logic is

type t_control_logic_fsm is (
                          ST_S1      ,
                          ST_S2      ,
                          ST_S3      );


signal r_st_present    : t_control_logic_fsm;
signal w_st_next       : t_control_logic_fsm;

begin
--------------------------------------------------------------------
-- FSM
p_state : process(i_clk,i_rstb)
begin
  if(i_rstb='0') then
    r_st_present            <= ST_S3;
  elsif(rising_edge(i_clk)) then
    r_st_present            <= w_st_next;
  end if;
end process p_state;

p_comb : process(
                 r_st_present    ,
                 i_input1        ,
                 i_input2        )
begin
  case r_st_present is
    when ST_S1 => 
      if (i_input1='1') then  
        w_st_next  <= ST_S2;
      else                                                         
        w_st_next  <= ST_S1;
      end if;
    when ST_S2 => 
      if (i_input1='0') and (i_input2='1')then  
        w_st_next  <= ST_S3;
      else                                                         
        w_st_next  <= ST_S2;
      end if;
    when others=> -- ST_S3 => 
      w_st_next  <= ST_S1;

  end case;
end process p_comb;

p_state_out : process(i_clk,i_rstb)
begin
  if(i_rstb='0') then
    o_output1     <= '0';
    o_output2     <= '0';
    o_output3     <= '0';

  elsif(rising_edge(i_clk)) then

    case r_st_present is
      when ST_S1        =>
        o_output1     <= '1';
        o_output2     <= '0';
        o_output3     <= '0';
      when ST_S2        =>
        o_output1     <= '0';
        o_output2     <= '1';
        o_output3     <= '0';
      when others => -- ST_S3 =>
        o_output1     <= '0';
        o_output2     <= '0';
        o_output3     <= '1';
    end case;
  end if;
end process p_state_out;

end rtl;

 

The outputs can be registered or not. The advice is to register all the FSM outputs unless it is absolutely necessary to recover a clock cycle, I mean you have to provide the FSM output with the lowest possible clock latency. Using registered outputs, you will improve the system timing performances.


 

Example Finite State Machine in VHDL

Ok at this point you must be wondering,

Would not be better to make an example so that I really understand this whole theory about the FSM?

Ok, you’re right.

A good example is far better than a good precept.

Suppose we want to implement an automatic vending machine.

The machine can accept only one or five dollars bill.

The vending machine can provide two different types of product:

  • product P1, cost 1 dollar
  • product P2, cost 3 dollars

The machine must be able to:

  • select the type of product
  • decode a number of bills inserted
  • provide the product if the money is sufficient otherwise wait until the correct amount.

In any moment, it shall be possible to have a refund in the case the user no longer wishes to take the product.

In this example, we describe a possible implementation of the architecture of the vending machine and then we will see how to implement the control logic in VHDL using a Finite State Machine (FSM).

In Figure 5 is reported a possible architecture:

Figure An example of Vending Machine Architecture
Figure 5 – An example of Vending Machine Architecture
  1. The product selector block is aimed to provide the current product selection.
  2. The money check block provides the current amount of money inserted into the machine
  3. The product delivery block provides the product selected in case of the amount of money inserted is enough to take the product
  4. The refund delivery block gives back all the money in case of refund request or gives back the refund if required

Figure 6 shows a possible implementation of the FSM, in the control logic block:

Figure - Vending Machine control logic possible implementation
Figure 6 – Vending Machine Control Logic possible implementation

In the state ST_RESET, the FMS wait for product selection.

When the product is selected, the FMS change its state and goes in the state ST_GET_PROD_REQ. Here the product selected is latched into the vending machine control logic. After one clock cycle (no condition is present on the connection arrow), the State Machine goes to the state ST_CHECK_CREDIT until the credit is greater than or equal to the credit required for the delivery of the currently selected product. In the state ST_CHECK_CREDIT, if a refund is requested, the FSM changes its state to ST_PROVIDE_TOTAL_REFUND and enable the total refund delivery, then goes to ST_RESET. Otherwise, if the credit is sufficient for product delivery, the ST_PROVIDE_PRODUCT enables the delivery of the selected product. After product delivery, the state ST_PROVIDE_REFUND aim the vending machine to provide the refund if the credit inserted were greater than the credit requested.

 

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity control_logic is
 port (
  i_clk                       : in  std_logic;
  i_rstb                      : in  std_logic;
  i_refund_request            : in  std_logic;  -- 1 clock pulse
  -- from product selector
  i_product_sel               : in  std_logic;  -- '0'=> product 1, '1'=> product 2
  i_product_sel_valid         : in  std_logic;  -- 1 clock pulse
  -- from money check
  i_money_value               : in  std_logic;  -- '0' => 1 dollar; '1' => five dollars
  i_money_value_valid         : in  std_logic;  -- 1 clock pulse
  -- to product delivery
  o_product_delivery_sel      : out std_logic;  -- '0'=> product 1, '1'=> product 2
  o_product_delivery_sel_ena  : out std_logic;  -- 1 clock pulse
  -- to delivery refund
  o_money_refund_value        : out std_logic_vector(3 downto 0); -- refund value, up to 15 dollars = (2^4)-1
  o_money_refund_value_ena    : out std_logic);  -- 1 clock pulse
end control_logic;

architecture rtl of control_logic is

constant C_PRICE_PRODUCT_1       : integer := 1;
constant C_PRICE_PRODUCT_2       : integer := 3;

type t_money_table is array(0 to 1) of integer range 1 to 5;
constant money_table : t_money_table := (1, 5);

type t_control_logic_fsm is (
                          ST_RESET                ,
                          ST_ST_GET_PROD_REQ      ,
                          ST_CHECK_CREDIT         ,
                          ST_PROVIDE_PRODUCT      ,
                          ST_PROVIDE_TOTAL_REFUND ,
                          ST_PROVIDE_REFUND       );


signal r_price_product             : integer range 1 to 3;
signal r_price_product_counter     : integer range 0 to 15;
signal r_refund                    : integer range 0 to 15;
signal w_money_value               : integer range 1 to 15;

signal r_st_present                : t_control_logic_fsm;
signal w_st_next                   : t_control_logic_fsm;

begin

-- convert input money selector to current money value
w_money_value <= money_table(0) when (i_money_value='0') else money_table(1);

--------------------------------------------------------------------
-- FSM
p_state : process(i_clk,i_rstb)
begin
  if(i_rstb='0') then
    r_st_present            <= ST_RESET;
  elsif(rising_edge(i_clk)) then
    r_st_present            <= w_st_next;
  end if;
end process p_state;

p_comb : process(
                 r_st_present                       ,
                 i_product_sel_valid                ,
                 i_refund_request                   ,
                 r_price_product_counter            ,
                 r_price_product                    
                 )
begin
  case r_st_present is
    when ST_ST_GET_PROD_REQ  => 
      w_st_next  <= ST_CHECK_CREDIT;
      
    when ST_CHECK_CREDIT     =>
      if (r_price_product_counter>=r_price_product) then  
        w_st_next  <= ST_PROVIDE_PRODUCT;
      elsif(i_refund_request='1') then
        w_st_next  <= ST_PROVIDE_TOTAL_REFUND;
      else
        w_st_next  <= ST_CHECK_CREDIT;
      end if;
    
    when ST_PROVIDE_PRODUCT  => 
      w_st_next  <= ST_PROVIDE_REFUND;
    
    when ST_PROVIDE_REFUND   => 
      w_st_next  <= ST_RESET;
    
    when ST_PROVIDE_TOTAL_REFUND   => 
      w_st_next  <= ST_RESET;
      
    when others=> -- ST_RESET            => 
      if (i_product_sel_valid='1') then  
        w_st_next  <= ST_ST_GET_PROD_REQ;
      else                                                         
        w_st_next  <= ST_RESET;
      end if;

  end case;
end process p_comb;

p_state_out : process(i_clk,i_rstb)
begin
  if(i_rstb='0') then
    r_price_product            <= C_PRICE_PRODUCT_1;
    r_price_product_counter    <= 0;
    r_refund                   <= 0;
    o_money_refund_value_ena   <= '0';
    o_product_delivery_sel     <= '0';
    o_product_delivery_sel_ena <= '0';

  elsif(rising_edge(i_clk)) then

    case r_st_present is
      when ST_ST_GET_PROD_REQ        =>
        if(i_product_sel='0') then
          r_price_product            <= C_PRICE_PRODUCT_1;
        else
          r_price_product            <= C_PRICE_PRODUCT_2;
        end if;
        o_money_refund_value_ena   <= '0';
        o_product_delivery_sel     <= i_product_sel;
        o_product_delivery_sel_ena <= '0';
        
      when ST_CHECK_CREDIT           =>
        if(i_money_value_valid='1') then
          r_price_product_counter   <= r_price_product_counter + w_money_value;
        end if;
        
      when ST_PROVIDE_PRODUCT        =>
        o_product_delivery_sel_ena <= '1';
        o_money_refund_value_ena   <= '0';

      when ST_PROVIDE_REFUND         =>
        r_refund                   <= r_price_product_counter - r_price_product;
        o_product_delivery_sel_ena <= '0';
        o_money_refund_value_ena   <= '1';
      
      when ST_PROVIDE_TOTAL_REFUND   =>
        r_refund                   <= r_price_product_counter;
        o_product_delivery_sel_ena <= '0';
        o_money_refund_value_ena   <= '1';
        
      when others =>  -- ST_RESET            =>
        r_price_product_counter    <= 0;
        r_refund                   <= 0;
        o_product_delivery_sel_ena <= '0';
        o_money_refund_value_ena   <= '0';
    end case;
  end if;
end process p_state_out;

o_money_refund_value      <= std_logic_vector(to_unsigned(r_refund,4));

end rtl;

VHDL Code Example of the Control Logic of a Vending Machine 

 

 

Now you should have clear how to implement Moore FSM in VHDL. Using the FSM VHDL code template provided above, you will implement a Finite State Machine in its canonical implementation.

Moreover, you should be able to implement you own Vending Machine in VHDL!

 

If you appreciated this post, please help us to share it with your friend.

 

[social_sharing style=”style-7″ fb_like_url=”https://surf-vhdl.com/how-to-implement-a-finite-state-machine-in-vhdl” fb_color=”light” fb_lang=”en_US” fb_text=”like” fb_button_text=”Share” tw_lang=”en” tw_url=”https://surf-vhdl.com/how-to-implement-a-finite-state-machine-in-vhdl” tw_button_text=”Share” g_url=”https://surf-vhdl.com/how-to-implement-a-finite-state-machine-in-vhdl” g_lang=”en-GB” g_button_text=”Share” linkedin_url=”https://surf-vhdl.com/how-to-implement-a-finite-state-machine-in-vhdl” linkedin_lang=”en_US” alignment=”center”]

 

If you need to contact us, please write to surf.vhdl@gmail.com

We appreciate any of your comment, please post below:

23 thoughts to “How to Implement a Finite State Machine in VHDL”

    1. i_product_sel_valid has the functionality of “product_request” in figure 6. It is used to start the delivery of the product
      o_product_delivery_sel_ena : it is used as a valid signal for product delivery. I mean every time it goes high (for one clock cycle) the FMS if providing a new product

  1. Also, I could not understand the parts
    “w_money_value <= money_table(0) when (i_money_value='0') else money_table(1);"

    " type t_money_table is array(0 to 1) of integer range 1 to 5;
    constant money_table : t_money_table := (1, 5);"

    I have an i_money_value that is a vector. And "00" means no money, "01" means $1, "10" means $5 and "11" means $10. How can I modify the code above in order to make it suitable for the i_money_value that is 2-bit.

    1. Yes, you can modify for sure.
      something like this:

      type t_money_table is array(0 to 3) of integer range 1 to 10;
      constant money_table : t_money_table := (0,1, 5,10);
      t_money_table(0) => 0 = no money
      t_money_table(1) => 1$
      t_money_table(2) => 5$
      t_money_table(3) => 10$

      or whatever you need

  2. Hi, firstly I would like to say that I found this blog very helpfull and useful for those who want to learn VHDL. I am not very familiar with the VHDL environment and have got several questions about the code above. I would really appreciate it if you answer my questions in a detailed way.

    1. Why did you create a money_table? I mean what is the use of the code “type t_money_table is array(0 to 1) of integer range 1 to 5;
    constant money_table : t_money_table := (1, 5);”

    2. Why did you defined signals such as r_price_product , r_price_product_counter, w_money_value, and r_refund? And what is the use of this signals?

    3. I could not understand the use of the code “w_money_value <= money_table(0) when (i_money_value='0') else money_table(1);" What do you mean by convert input money selector to current money value?

    1. Hi Perry, thank you for your feedback.
      A1) the use of “type t_money_table” is to define a type in order to create a table of prices that you can found int the constant “money_table”
      A2) the use of these signal is reported in Figure 5. These are the signal used by the control logic as reported in Figure6
      A3) the input selector is a signal used to select a value. In this case when i_money_value=’0′ we decided the internal coding as 1$ i.e. money_table(0); when i_money_value=’1′ we decided the internal coding as 5$ i.e. money_table(1);

    1. just add the state un the enumeration type:
      type t_control_logic_fsm is (
      ST_S1 ,
      ST_S2 ,
      ST_S3 ,
      ST_S4 ,
      ST_S5 ,
      .. ,

      ST_S10 );

      and then add the CASE statement

  3. I was about to write vhdl for a FSM control circuit,. Not for a vending machine but your how-to provides good example to follow. Thanks a lot

  4. hi there, Im new to this. I understand there are inputs so how will the constraints be set in terms of input output?

    1. you have to read VHDL, understand it and then write the diagram 🙂
      Generally, you have to write a diagram and then code the FSM.
      Some synthesis tools perform the FSM extraction and provide the diagram, you can start from this

  5. my question is if there is a tool which can convert VHDL code to FSM
    in details job of these tool analyse the VHDL code(compiler) and draw FSM diagram (CAD tool)

Leave a Reply

Your email address will not be published. Required fields are marked *