Engineering Technology State Machines in VHDL Dr. H.v.d.Biggelaar Dr. H.v.d.Biggelaar / Mar3-Ver2 / March 22, 2000 1 State Machines Moore Mealy Dr. H.v.d.Biggelaar / Mar3-Ver2 / 2 arst='1' arst='1' n y y y q<="0.." q<=d
d register n n y ps<=s0 n ps<=ns state machine similarities between the clocking of a bank of flip-flops and the flip-flops in a state machine Dr. H.v.d.Biggelaar / Mar3-Ver2 / 3 si cntra enaa<='1' qa[ ] sj enaa cnta
clka n cnta='1' y sk cntrb enab<='1' qb[ ] sl enab clkb n cntb cntb='1' y sm An example of an FSM used as a controller for two counters Dr. H.v.d.Biggelaar / Mar3-Ver2 / 4 case ps is x
s0 s0 x x s1 x y s1 x y s2 x=1 n x=0 n when s0 => if x='1' then ns<=s0; else ns<=s1; end if; when s1 => if x='0 then ns<=s1; else
ns<=s2; end if; when s2 => ns<=s0; s2 x when others => ns<=s0; end case; Dr. H.v.d.Biggelaar / Mar3-Ver2 / 5 pseq: process(ps); begin case ps is when s0 => q<="010"; ns<=s1; when s1 => q<="111"; ns<=s2; when s2 => q<="011"; ns<=s3; when s3 => q<="100"; ns<=s0; when others =>
q<="000"; ns<=s0; end case; end process pseq; Advantages of using a state machine to implement this type of counter: 1. The count sequence (2-7-3-4) can be easily changed. 2. The number of counts (4) can be easily changed by adding states. 3. The code is easy to understand. Dr. H.v.d.Biggelaar / Mar3-Ver2 / 6 Data Types Enumerated (user-defined): This is a list of values generated by the designer. Their synthesis is application-specific. The values of the elements in the list start at 0 at the left ( and increment by one from there. Particularly useful in state machines. Example: type states is (idle, detect, send, receive); signal prsnt, next: states; Note: Boolean and bit are also enumerated types, defined by the IEEE standard. type Boolean is (false, true); type bit is (0, 1); Dr. H.v.d.Biggelaar / Mar3-Ver2 / 7
State machines Moore Machines A finite state machine in which the outputs change only due to a change of state Mealy Machines A finite state machine in which the outputs can change asynchronously i.e., an input can cause an output to change immediately Dr. H.v.d.Biggelaar / Mar3-Ver2 / 8 Moore state machine implementations (1) Outputs decoded from state bits Combinatorial decode Outputs are decoded combinatorially from the current state outputscomb = f(present state) Inputs Logic State Registers Dr. H.v.d.Biggelaar / Mar3-Ver2 / Output Logic
Outputs 9 Moore state machine implementations (2) Outputs decoded from state bits Registered decode Outputs are registered; decode of outputs is in parallel with decode of next state outputsreg = f(previous state, inputs) Inputs Next State Logic State Registers Current State Output Logic Dr. H.v.d.Biggelaar / Mar3-Ver2 / Output Registers Outputs 10 Moore State Machine Implementations (3)
Outputs encoded within state bits Example: State Output 1 Output 2 State Encoding s1 0 0 00 s2 1 0 01 s3 0 1 10
Note: Both bits of the state encoding are used as outputs Inputs Logic State Registers Dr. H.v.d.Biggelaar / Mar3-Ver2 / Outputs 11 --fsm1.vhd in ~hvdb\ library ieee; use ieee.std_logic_1164.all; entity fsm1 is port(arst,clk,x:in std_logic; q:out std_logic_vector(1 downto 0)); end entity fsm1; architecture a_fsm1 of fsm1 is type states is (s0,s1,s2); signal ns,ps: states; begin pclk: process(arst,clk) begin if arst='1' then ps<=s0; elsif rising_edge(clk) then ps<=ns; end if; end process pclk;
pseq: process(x,ps) begin case ps is when s0 => q<="00"; if x='0' then ns<=s0; else ns<=s1; end if; when s1 => q<="01"; if x='1' then ns<=s1; else ns<=s2; end if; when s2 => q<="10"; if x='0' then ns<=s2; else ns<=s0; end if; when others => q<="00"; ns<=s0; end case; end process pseq; end architecture a_fsm1; Complete code for a Moore machine with outputs q1 and q0 that reflect the value of the state variable.
Dr. H.v.d.Biggelaar / Mar3-Ver2 / 12 --fsm2.vhd in ~hvdb\ library ieee; use ieee.std_logic_1164.all; entity fsm2 is port(arst,clk,x:in std_logic; q:out std_logic_vector(1 downto 0)); end entity fsm2; architecture a_fsm2 of fsm2 is type states is (s0,s1,s2); signal ps: states; begin pfsm: process(arst,clk) begin if arst='1' then ps<=s0; elsif rising_edge(clk) then case ps is when s0 => if x='0' then ps<=s0; else ps<=s1; end if; when s1 => if x='1' then ps<=s1; else ps<=s2;
end if; when s2 => if x='0' then ps<=s2; else ps<=s0; end if; when others => ps<=s0; end case; end if; end process pfsm; with ps select q<="00" when "01" when "10" when "00" when s0, s1, s2, others; end architecture a_fsm2; Complete code for the same Moore machine as in the previous example, but with a single process. Dr. H.v.d.Biggelaar / Mar3-Ver2 / 13 One-Hot Encoding One state per flip-flop:
in FPGA-type architectures reduces the next state logic requires fewer levels of logic cells enables high-speed state machines (> 100MHz). in CPLD-type architectures reduces the number of product terms can eliminate expander product terms (i.e. reduce delays, and increase operating speed). but, uses more macrocells and there may not be enough Flip-Flops Dr. H.v.d.Biggelaar / Mar3-Ver2 / 14 --fsm3.vhd in ~hvdb\ library ieee; use ieee.std_logic_1164.all; when s1 => q<="010"; if x='1' then ns<=s1; else ns<=s2; end if; when s2 => q<="100"; if x='0' then ns<=s2; else ns<=s0; end if; when others => q<="111";
ns<=s0; end case; end process pseq; entity fsm3 is port(arst,clk,x:in std_logic; q:out std_logic_vector(2 downto 0)); end entity fsm3; architecture a_fsm3 of fsm3 is signal ps,ns: std_logic_vector(2 downto 0); constant s0: std_logic_vector(2 downto 0):="001"; constant s1: std_logic_vector(2 downto 0):="010"; constant s2: std_logic_vector(2 downto 0):="100"; begin pclk: process(arst,clk) begin if arst='1' then ps<=s0; elsif rising_edge(clk) then ps<=ns; end if; end process pclk; pseq: process(x,ps) begin case ps is when s0 => q<="001"; if x='0' then ns<=s0; else ns<=s1; end if; end architecture a_fsm3;
Note that the values of the constants are chosen by the designer and thus are not limited to a one-hot sequence. For instance to minimize power, one may prefer a Gray code. Again the same Moore machine but this time with one-hot encoding Dr. H.v.d.Biggelaar / Mar3-Ver2 / 15 Mealy Machines Outputs may change with a change of state OR with a change of inputs. Mealy outputs are non-registered because they are functions of the present inputs State Registers Inputs Logic Dr. H.v.d.Biggelaar / Mar3-Ver2 / Outputs 16 s0 n
ASM chart of a Mealy machine The only output z is 1 when the machine is in state s1 AND the input x is 1. x='1' y s1 n x='1' y z<='1' Dr. H.v.d.Biggelaar / Mar3-Ver2 / 17 -- fsm4.vhd in ~hvdb\ library ieee; use ieee.std_logic_1164.all; entity fsm4 is port(x,clk:in std_logic; z:out std_logic); end entity fsm4; architecture a_fsm4 of fsm4 is type state is(s0,s1); signal ns,ps: state; begin pclk: process(clk) begin if rising_edge(clk) then ps<=ns;
end if; end process pclk; pseq: process(x,ps) begin case ps is when s0 => if x='0' then ns<=s0; else ns<=s1; end if; when s1 => if x='1' then ns<=s0; else ns<=s1; end if; end case; end process pseq; z<='1' when ps=s1 and x='1' else '0'; end architecture a_fsm4; Complete code for a Mealy machine with only a conditional output. Dr. H.v.d.Biggelaar / Mar3-Ver2 / 18 This simulation is not very useful. It does not show how z depends on the input x and the state. Dr. H.v.d.Biggelaar / Mar3-Ver2 / 19
-- fsm4.vhd in ~hvdb\ library ieee; use ieee.std_logic_1164.all; entity fsm4 is port(x,clk:in std_logic; z:out std_logic q:out std_logic_vector(1 downto 0)); end entity fsm4; architecture a_fsm4 of fsm4 is type state is(s0,s1); signal ns,ps: state; begin pclk: process(clk) begin if rising_edge(clk) then ps<=ns; end if; end process pclk; pseq: process(x,ps) begin case ps is when s0 => if x='0' then ns<=s0; else ns<=s1; end if; when s1 => if x='1' then ns<=s0; else ns<=s1;
end if; end case; end process pseq; z<='1' when ps=s1 and x='1' else '0'; with ps select q<=00 when s0, 10 when s1, 11 when others; end architecture a_fsm4; The same Mealy machine but with output q added to show the value of the state variable. Dr. H.v.d.Biggelaar / Mar3-Ver2 / 20 This simulation is better. Its clear now that z is a 1 only when x is a 1 AND the FSM is in state s1. However, the transitions of x take place only on the active edge of the clock, so you cannot tell if the response to the change in x is synchronous or asynchronous. Dr. H.v.d.Biggelaar / Mar3-Ver2 / 21 By just moving the transition of x from coinciding with a leading edge of the clock to a level portion, it becomes obvious that when x goes from 1 to 0, the output z changes immediately, so that action is asynchronous. Dr. H.v.d.Biggelaar / Mar3-Ver2 / 22 F = B.A + B.rdy
B F = B.A.rdy + B.A.wr + B.A.rdy A Do you really want to do this? Dr. H.v.d.Biggelaar / Mar3-Ver2 / 23 ROM-Centered Design top entity outputs inputs ROM cen reg clock Dr. H.v.d.Biggelaar / Mar3-Ver2 / 24 ROM-Centered Design fsmrom pwait req d(0) d(1)
ROM16x4 a(2) d(2) a(3) d(3) q0_i reset clock ack ret a(0) a(1) q1_i d1_i d0_i q1 d1 q0 d0 reg2 rst clk Dr. H.v.d.Biggelaar / Mar3-Ver2 / 25 State T able for the W ait-State G enerator ROM addr 2
3 0 1 4 6 5 7 8 9 10 11 B 0 0 0 0 0 0 0 0 1 1 1 1 p r e s e n t s t a te A req pwait 0 1 0 0
1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 n e x t s ta t e
B A 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 ret 0 0 1 1 1 1
0 0 0 0 0 0 ack ROM dat a 0 0 0 0 0 0 1 1 0 0 0 0 0 0 6 6 6 6 9 9 0
0 0 0 Example: for addr = 0, the data is 0110 (B-A-ret-ack) or 6 (hex) Dr. H.v.d.Biggelaar / Mar3-Ver2 / 26 And And thats thats IT IT for for State State Machines Machines Dr. H.v.d.Biggelaar / Mar3-Ver2 / 27
