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.
![](https://surf-vhdl.com/wp/wp-content/uploads/2015/11/FSM-Mealy.png)
Figure 2 schematizes the Moore FSM.
![Moore FSM schematic view](https://surf-vhdl.com/wp/wp-content/uploads/2015/11/FSM-Moore.png)
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](https://surf-vhdl.com/wp/wp-content/uploads/2015/11/FSM-visual-representation.png)
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](https://surf-vhdl.com/wp/wp-content/uploads/2015/11/FSM-visual-representation-state-out.png)
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](https://surf-vhdl.com/wp/wp-content/uploads/2015/12/Vending-Machine-Architecture.png)
- The product selector block is aimed to provide the current product selection.
- The money check block provides the current amount of money inserted into the machine
- The product delivery block provides the product selected in case of the amount of money inserted is enough to take the product
- 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](https://surf-vhdl.com/wp/wp-content/uploads/2015/11/Vending-Machine-FSM.png)
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:
I could not understand the functions of o_product_delivery_sel_ena and i_product_sel_valid. Can you explain them?
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
It is used to select which product the machine have to deliver
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.
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
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?
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);
what is the condition that makes i_money_value_valid=1?
it is an input signal used to validate the input “i_money_value”
will that be always going to be ‘1’
How do i create a vhdl code for an 11 state S0-S10 moore fsm please
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
Am especially no sure what to at case r_st_present when i have 11 states
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
thank you for your feedback, I appreciate it a lot!
ciao
If you don’t mind can you share your testbench?
send me an email
hi there, Im new to this. I understand there are inputs so how will the constraints be set in terms of input output?
I don’t understand the question, can you reword?
how to do the opposite way???
I mean converting VHDL code to FSM
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
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)
you can use Altera or Xilinx layout tool