Finite State Machines
Output = f(present state) – Moore machine
Output = f(present state, Input) – Mealy machine
It is recommended that the upper and lower sections should be considered separately.
The lower section can be molded as:
PROCESS (res, clk)
BEGIN
IF (res='1') THEN
present_state <= state0;
ELSIF (clock'EVENT AND clk='1') THEN
present_state <= next_state;
END IF;
END PROCESS;
Where state0 is the initial state after reset.
The top portion is a purely combinational circuit, and does not depend on the clock. Variations are possible for this portion, but it is typically implement as one or two processes. In the case of using two processes, one process is use to compute the next case and the other is used to compute the output. In the one process method, both the next state and the output are computed in the same process.
Example consider the FSM shown below:
------
ENTITY simple_fsm IS
PORT ( a, b, d, clk, rst: IN BIT;
x:OUT BIT);
END simple_fsm;
------
ARCHITECTURE simple_fsm OF simple_fsm IS
TYPE state IS (stateA, stateB);
SIGNAL pr_state, nx_state: state;
BEGIN
----- Lower section: ------
PROCESS (rst, clk)
BEGIN
IF (rst='1') THEN
pr_state <= stateA;
ELSIF (clk'EVENT AND clk='1') THEN
pr_state <= nx_state;
END IF;
END PROCESS;
------Upper section: ------
PROCESS (a, b, d, pr_state)
BEGIN
CASE pr_state IS
WHEN stateA =>
x <= a;
IF (d='1') THEN nx_state <= stateB;
ELSE nx_state <= stateA;
END IF;
WHEN stateB =>
x <= b;
IF (d='1') THEN nx_state <= stateA;
ELSE nx_state <= stateB;
END IF;
END CASE;
END PROCESS;
END simple_fsm;
Finite State Machines (FSM’s) / Algorithmic State Machines (ASM)
Pseudo HDL description.
If reset then goto S0.
S0: Detected = 0, If Din =1 goto S1.
S1: Detected = 0, If Din = 0 goto S2.
S2: If Din = 0 Detected = 0, goto and D
else Detected = 1, goto S0.
LiBRARY IEEE; USE IEEE.std_logic_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
ENTITY EXFSM IS
PORT (CLK : IN STD_LOGIC;
RESET : IN STD_LOGIC;
X : IN STD_LOGIC;
Z : OUT STD_LOGIC );
END ENTITY EXFSM;
PROCESS(CLK, RESET)
BEGIN
IF (RESET = '1') THEN
State <= S0;
ELSIF CLK’event and CLK = ‘0’ THEN
State <= Next_State;
END IF;
END PROCESS;
ARCHITECTURE arch OF EXFSM IS
TYPE A_State IS (S0, S1, S2);
SIGNAL State, Next_State : A_State;
BEGIN
PROCESS(State, X)
BEGIN
CASE State IS
WHEN S0 =>
IF X = '0' THEN
Next_State <= S0;
Z <= '0';
ELSE
Next_State <= S1;
Z <= '0';
END IF;
WHEN S1 =>
IF X = '1' THEN
Next_State <= S1;
Z <= '0';
ELSE
Next_State <= S2;
Z <= '0';
END IF;
WHEN S2 =>
IF X = '1' THEN
Next_State <= S1;
Z <= '1';
ELSE
Next_State <= S0;
Z <= '0';
END IF;
END CASE;
END PROCESS;
END arch;-
Ex. Build a FSM that produces an output of ‘1’ after the 4th enabled clock on startup and on the 5th enabled clock thereafter. The output remains ‘1’ for a total of three enabled clocks and then return to ‘0’.
ENTITY VENCNT IS
GENERIC(N: integer := 5; M: integer := 1);
PORT (CLK: IN STD_LOGIC;
EN: IN STD_LOGIC;
TP : OUT STD_LOGIC := '0'
);
END ENTITY VENCNT;
ARCHITECTURE fsm of VENCNT is
TYPE A_State IS (S0, S1, S2, S3, S4, S5, S6, S7, S8);
SIGNAL State, Next_State : A_State;
BEGIN
PROCESS(CLK)
BEGIN
IF falling_edge(CLK) THEN
State <= Next_State;
END IF;
END PROCESS;
PROCESS(State, EN)
BEGIN
CASE State IS
WHEN S0 =>
TP <= '0';
IF EN = '0' THEN
Next_State <= S0;
ELSE
Next_State <= S1;
END IF;
WHEN S1 =>
TP <= '0';
IF EN = '0' THEN
Next_State <= S1;
ELSE
Next_State <= S2;
END IF;
WHEN S2 =>
TP <= '0';
IF EN = '0' THEN
Next_State <= S2;
ELSE
Next_State <= S3;
END IF;
WHEN S3 =>
TP <= '0';
IF EN = '0' THEN
Next_State <= S3;
ELSE
Next_State <= S4;
END IF;
WHEN S4 =>
TP <= '1';
IF EN = '0' THEN
Next_State <= S4;
ELSE
Next_State <= S5;
END IF;
WHEN S5 =>
TP <= '1';
IF EN = '0' THEN
Next_State <= S5;
ELSE
Next_State <= S6;
END IF;
WHEN S6 =>
TP <= '1';
IF EN = '0' THEN
Next_State <= S6;
ELSE
Next_State <= S7;
END IF;
WHEN S7 =>
TP <= '0';
IF EN = '0' THEN
Next_State <= S7;
ELSE
Next_State <= S8;
END IF;
WHEN S8 =>
TP <= '0';
IF EN = '0' THEN
Next_State <= S8;
ELSE
Next_State <= S4;
END IF;
END CASE;
END PROCESS;
end fsm;
15
An example from EGRE 426. Ignore the outputs and consider only the states.
15
NPKIPS_CU
LiBRARY IEEE;
USE work.ALL;
USE IEEE.std_logic_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
use pkg_npkips.all;
ENTITY CU IS
PORT (CLK : IN STD_LOGIC;
RES : IN STD_LOGIC;
OP : in STD_LOGIC_VECTOR(5 downto 0);
S : OUT A_STATE
);
END ENTITY CU;
ARCHITECTURE arch OF CU IS
SIGNAL STATE, Next_State : A_State;
BEGIN
S <= STATE;
PROCESS(State, op)
BEGIN
CASE State IS
WHEN S0 =>
Next_State <= S1;
WHEN S1 =>
CASE OP IS
WHEN op_lw | op_sw =>
Next_State <= S2;
WHEN op_R_type =>
Next_State <= S6;
WHEN op_BEQ =>
Next_State <= S5;
WHEN op_J =>
Next_State <= S9;
WHEN others =>
NEXT_STATE <= S0;
END CASE;
WHEN S2 =>
IF OP = op_lw then
Next_State <= S3;
ELSE
Next_State <= S5;
END IF;
WHEN S3 =>
NEXT_STATE <= S4;
WHEN S4 | S5 | S7 | S8 | S9 =>
NEXT_STATE <= S0;
WHEN S6 =>
NEXT_STATE <= S7;
WHEN others =>
Next_State <= S0;
END CASE;
END PROCESS;
PROCESS(CLK, RES)
BEGIN
IF (RES = '1') THEN
State <= S0;
ELSIF clk'event and clk = '1' THEN
State <= Next_State;
END IF;
END PROCESS;
END arch;
The package PKG_NPKIPS.VHD
-- PKG_NPKIPS.VHD Version 1.1
LIBRARY IEEE;
USE work.all;
USE IEEE.Std_Logic_1164.all;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
PACKAGE pkg_npkips IS
TYPE A_State IS (S0, S1, S2, S3, S4, S5, S6,
S7, S8, S9 );
SUBTYPE Opcode is STD_LOGIC_vector(5 downto 0);
SUBTYPE Func is STD_LOGIC_vector(5 downto 0);
-- Mapping of instructions to opcodes. See Apendix A.
CONSTANT Op_lw :Opcode := B"100011";
CONSTANT Op_sw :Opcode := B"101011";
CONSTANT Op_beq :Opcode := B"000100";
CONSTANT Op_addi :Opcode := B"001000";
CONSTANT Op_andi :Opcode := B"001100";
CONSTANT Op_ori :Opcode := B"001101";
CONSTANT Op_xori :Opcode := B"001110";
CONSTANT Op_slti :Opcode := B"001010";
CONSTANT Op_or :Opcode := B"000000";
CONSTANT Op_slt :Opcode := B"000000";
CONSTANT Op_j :Opcode := B"000010";
CONSTANT Op_R_type :Opcode := B"000000";
CONSTANT Func_add :Func := B"000000";
CONSTANT Func_sub :Func := B"010010";
CONSTANT Func_and :Func := B"000100";
CONSTANT Func_or :Func := B"010101";
CONSTANT Func_slt :Func := B"011010";
CONSTANT Func_null :Func := B"000000";
CONSTANT Func_jr :Func := B"001000";
CONSTANT Func_xor :Func := B"100110";
CONSTANT Func_nor :Func := B"100111";
END PACKAGE pkg_npkips;
tb_cu.vhd
------
-- tb_cu.vhd - Test bench for npkips cu.
------
LiBRARY IEEE;
USE work.ALL;
USE IEEE.std_logic_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
use pkg_npkips.all;
ENTITY TB IS
END ENTITY TB;
ARCHITECTURE TEST of TB is
signal Reset: std_logic := '1';
signal CLK: std_logic := '0';
signal S: A_STATE;
signal op: std_logic_vector(5 downto 0);
Type Inst_type is (J, BEQ, R_Type, LW, SW);
signal inst: inst_type;
BEGIN
U1: ENTITY work.cu(arch)
PORT MAP
( CLK => CLK,
RES => Reset,
OP => OP,
S => S
);
CLK <= not CLK after 5 ns when Reset = '0' else '0';
Reset <= '0' after 10 ns;
process
begin
op <= op_lw;
wait on S;
wait until s = s0;
op <= op_sw;
wait on S;
wait until s = s0;
op <= op_j;
wait on S;
wait until s = s0;
op <= op_R_type;
wait on S;
wait until s = s0;
op <= op_beq;
wait on S;
wait until s = s0;
end process;
process(op)
begin
case op is
when op_lw => inst <= LW;
when op_sw => inst <= sw;
when op_R_type => inst <= R_type;
when op_J => inst <= J;
when op_beq => inst <= BEQ;
when others => null;
end case;
end process;
END ARCHITECTURE TEST;
15