Tuesday, December 18, 2007

State Machine

There are many ways to describe FSMs. A traditional FSM representation incorporates Mealy and Moore machines, as in the following figure:

You may have several processes (1, 2 or 3) in your description, depending upon how you consider and decompose the different parts of the preceding model. Following is an example of the Moore Machine with Asynchronous Reset, "RESET".

  • 4 states: s1, s2, s3, s4
  • 5 transitions
  • 1 input: "x1"
  • 1 output: "outp"

This model is represented by the following bubble diagram:

Related Constraints

Related constraints are:

  • FSM_extract
  • FSM_encoding
  • FSM_fftype
  • ENUM_encoding

FSM with 1 Process

Please note, in this example output signal "outp" is a register.

VHDL

Following is the VHDL code for an FSM with a single process.

library IEEE;  
use IEEE.std_logic_1164.all;

entity fsm is
port ( clk, reset, x1 : IN std_logic;
outp : OUT std_logic);
end entity;
architecture beh1 of fsm is
type state_type is (s1,s2,s3,s4);
signal state: state_type ;
begin
process (clk,reset)
begin
if (reset ='1') then
state <=s1; outp<='1';
elsif (clk='1' and clk'event) then
case state is
when s1 => if x1='1' then state <= s2;
else state <= s3;
end if;
outp <= '1';
when s2 => state <= s4; outp <= '1';
when s3 => state <= s4; outp <= '0';
when s4 => state <= s1; outp <= '0';
end case;
end if;
end process;
end beh1;

Verilog

Following is the Verilog code for an FSM with a single process.

module fsm (clk, reset, x1, outp);  
input clk, reset, x1;
output outp;
reg outp;

reg [1:0] state;
parameter s1 = 2'b00; parameter s2 = 2'b01;
parameter s3 = 2'b10; parameter s4 = 2'b11;

always@(posedge clk or posedge reset)
begin
if (reset)
begin
state = s1; outp = 1'b1;
end
else
begin
case (state)
s1: begin
if (x1==1'b1) state = s2;
else state = s3;
outp = 1'b1;
end
s2: begin
state = s4; outp = 1'b1;
end
s3: begin
state = s4; outp = 1'b0;
end
s4: begin
state = s1; outp = 1'b0;
end
endcase
end
end
endmodule

FSM with 2 Processes

To eliminate a register from the "outputs", you can remove all assignments "outp <=..." from the Clock synchronization section.

This can be done by introducing two processes as shown in the following figure.

VHDL

Following is VHDL code for an FSM with two processes.

library IEEE;  
use IEEE.std_logic_1164.all;

entity fsm is
port ( clk, reset, x1 : IN std_logic;
outp : OUT std_logic);
end entity;
architecture beh1 of fsm is
type state_type is (s1,s2,s3,s4);
signal state: state_type ;
begin
process1: process (clk,reset)
begin
if (reset ='1') then state <=s1;
elsif (clk='1' and clk'Event) then
case state is
when s1 => if x1='1' then state <= s2;
else state <= s3;
end if;
when s2 => state <= s4;
when s3 => state <= s4;
when s4 => state <= s1;
end case;
end if;
end process process1;

process2 : process (state)
begin
case state is
when s1 => outp <= '1';
when s2 => outp <= '1';
when s3 => outp <= '0';
when s4 => outp <= '0';
end case;
end process process2;
end beh1;

Verilog

Following is the Verilog code for an FSM with two processes.

module fsm (clk, reset, x1, outp);  
input clk, reset, x1;
output outp;
reg outp;

reg [1:0] state;
parameter s1 = 2'b00; parameter s2 = 2'b01;
parameter s3 = 2'b10; parameter s4 = 2'b11;

always @(posedge clk or posedge reset)
begin
if (reset)
state = s1;
else
begin
case (state)
s1: if (x1==1'b1) state = s2;
else state = s3;
s2: state = s4;
s3: state = s4;
s4: state = s1;
endcase
end
end

always @(state)
begin
case (state)
s1: outp = 1'b1;
s2: outp = 1'b1;
s3: outp = 1'b0;
s4: outp = 1'b0;
endcase
end
endmodule

FSM with 3 Processes

You can also separate the NEXT State function from the State Register:

Separating the NEXT State function from the State Register provides the following description:

VHDL

Following is the VHDL code for an FSM with three processes.

library IEEE;  
use IEEE.std_logic_1164.all;

entity fsm is
port ( clk, reset, x1 : IN std_logic;
outp : OUT std_logic);
end entity;
architecture beh1 of fsm is
type state_type is (s1,s2,s3,s4);
signal state, next_state: state_type ;
begin
  process1: process (clk,reset)  
begin
if (reset ='1') then
state <=s1;
elsif (clk='1' and clk'Event) then
state <= next_state;
end if;
end process process1;

process2 : process (state, x1)
begin
case state is
when s1 => if x1='1' then
next_state <= s2;
else
next_state <= s3;
end if;
when s2 => next_state <= s4;
when s3 => next_state <= s4;
when s4 => next_state <= s1;
end case;
end process process2;

process3 : process (state)
begin
case state is
when s1 => outp <= '1';
when s2 => outp <= '1';
when s3 => outp <= '0';
when s4 => outp <= '0';
end case;
end process process3;
end beh1;

Verilog

Following is the Verilog code for an FSM with three processes.

module fsm (clk, reset, x1, outp);  
input clk, reset, x1;
output outp;
reg outp;

reg [1:0] state;
reg [1:0] next_state;
parameter s1 = 2'b00; parameter s2 = 2'b01;
parameter s3 = 2'b10; parameter s4 = 2'b11;

always @(posedge clk or posedge reset)
begin
if (reset) state = s1;
else state = next_state;
end

always @(state or x1)
begin
case (state)
s1: if (x1==1'b1) next_state = s2;
else next_state = s3;
s2: next_state = s4;
s3: next_state = s4;
s4: next_state = s1;
endcase
end

always @(state)
begin
case (state)
s1: outp = 1'b1;
s2: outp = 1'b1;
s3: outp = 1'b0;
s4: outp = 1'b0;
endcase
end
endmodule

State Registers

State Registers must to be initialized with an asynchronous or synchronous signal. XST does not support FSM without initialization signals. Please refer to the "Registers" section of this chapter for templates on how to write Asynchronous and Synchronous initialization signals.

In VHDL the type of a state register can be a different type: integer, bit_vector, std_logic_vector, for example. But it is common and convenient to define an enumerated type containing all possible state values and to declare your state register with that type.

In Verilog, the type of state register can be an integer or a set of defined parameters. In the following Verilog examples the state assignments could have been made like this:

parameter [3:0] 
s1 = 4'b0001,
s2 = 4'b0010,
s3 = 4'b0100,
s4 = 4'b1000;
reg [3:0] state;

These parameters can be modified to represent different state encoding schemes.

Next State Equations

Next state equations can be described directly in the sequential process or in a distinct combinational process. The simplest template is based on a Case statement. If using a separate combinational process, its sensitivity list should contain the state signal and all FSM inputs.

FSM Outputs

Non-registered outputs are described either in the combinational process or concurrent assignments. Registered outputs must be assigned within the sequential process.

FSM Inputs

Registered inputs are described using internal signals, which are assigned in the sequential process.

State Encoding Techniques

  • One-Hot
  • Gray
  • Compact
  • Johnson
  • Sequential
  • User

One-Hot

One-hot encoding is the default encoding scheme. Its principle is to associate one code bit and also one flip-flop to each state. At a given clock cycle during operation, one and only one state variable is asserted. Only two state variables toggle during a transition between two states. One-hot encoding is very appropriate with most FPGA targets where a large number of flip-flops are available. It is also a good alternative when trying to optimize speed or to reduce power dissipation.

Gray

Gray encoding guarantees that only one state variable switches between two consecutive states. It is appropriate for controllers exhibiting long paths without branching. In addition, this coding technique minimizes hazards and glitches. Very good results can be obtained when implementing the state register with T flip-flops.

Compact

Compact encoding, consists of minimizing the number of state variables and flip-flops. This technique is based on hypercube immersion. Compact encoding is appropriate when trying to optimize area.

Johnson

Like Gray, Johnson encoding shows benefits with state machines containing long paths with no branching.

Sequential

Sequential encoding consists of identifying long paths and applying successive radix two codes to the states on these paths. Next state equations are minimized.



Powered by ScribeFire.

No comments: