|
|
|
|
|
The traditional methods used to generate state machine logic result in highly-encoded states. State machines with highly-encoded state variables typically have a minimum number of flip-flops and wide combinatorial functions. These characteristics are acceptable for PAL and gate array architectures. However, because FPGAs have many flip-flops and narrow function generators, highly-encoded state variables can result in inefficient implementation in terms of speed and density.
One-hot encoding allows you to create state machine implementations that are more efficient for FPGA architectures. You can create state machines with one flip-flop per state and decreased width of combinatorial logic. One-hot encoding is usually the preferred method for large FPGA-based state machine implementation. For small state machines (fewer than 8 states), binary encoding may be more efficient. To improve design performance, you can divide large (greater than 32 states) state machines into several small state machines and use the appropriate encoding style for each.
Three design examples are provided in this section to illustrate the three coding methods (binary, enumerated type, and one-hot) you can use to create state machines. All three examples contain the same Case statement. To conserve space, the complete Case statement is only included in the binary encoded state machine example; refer to this example when reviewing the enumerated type and one-hot examples.
Some synthesis tools allow you to add an attribute, such as type_encoding_style, to your VHDL code to set the encoding style. This is a synthesis vendor attribute (not a Xilinx attribute). Refer to your synthesis tool documentation for information on attribute-driven state machine synthesis.
Note: The bold text in each of the three examples indicates the portion of the code that varies depending on the method used to encode the state machine.
The state machine bubble diagram in the following figure shows the operation of a seven-state machine that reacts to inputs A through E as well as previous-state conditions. The binary encoded method of coding this state machine is shown in the VHDL and Verilog examples that follow. These design examples show you how to take a design that has been previously encoded (for example, binary encoded) and synthesize it to the appropriate decoding logic and registers. These designs use three flip-flops to implement seven states.
Figure 4.5 State Machine Bubble Diagram-------------------------------------------------
-- BINARY.VHD Version 1.0 --
-- Example of a binary encoded state machine --
-- May 1997 --
-------------------------------------------------
Library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
entity binary is
port (CLOCK, RESET : in STD_LOGIC;
A, B, C, D, E: in BOOLEAN;
SINGLE, MULTI, CONTIG: out STD_LOGIC);
end binary;
architecture BEHV of binary is
type STATE_TYPE is (S1, S2, S3, S4, S5, S6, S7);
attribute ENUM_ENCODING: STRING;
attribute ENUM_ENCODING of STATE_TYPE:type is "001 010 011 100 101 110 111";
signal CS, NS: STATE_TYPE;
begin
SYNC_PROC: process (CLOCK, RESET)
begin
if (RESET='1') then
CS <= S1;
elsif (CLOCK'event and CLOCK = '1') then
CS <= NS;
end if;
end process; --End REG_PROC
COMB_PROC: process (CS, A, B, C, D, E)
begin
case CS is
when S1 =>
MULTI <= '0';
CONTIG <= '0';
SINGLE <= '0';
if (A and not B and C) then
NS <= S2;
elsif (A and B and not C) then
NS <= S4;
else
NS <= S1;
end if;
when S2 =>
MULTI <= '1';
CONTIG <= '0';
SINGLE <= '0';
if (not D) then
NS <= S3;
else
NS <= S4;
end if;
when S3 =>
MULTI <= '0';
CONTIG <= '1';
SINGLE <= '0';
if (A or D) then
NS <= S4;
else
NS <= S3;
end if;
when S4 =>
MULTI <= '1';
CONTIG <= '1';
SINGLE <= '0';
if (A and B and not C) then
NS <= S5;
else
NS <= S4;
end if;
when S5 =>
MULTI <= '1';
CONTIG <= '0';
SINGLE <= '0';
NS <= S6;
when S6 =>
MULTI <= '0';
CONTIG <= '1';
SINGLE <= '1';
if (not E) then
NS <= S7;
else
NS <= S6;
end if;
when S7 =>
MULTI <= '0';
CONTIG <= '1';
SINGLE <= '0';
if (E) then
NS <= S1;
else
NS <= S7;
end if;
end case;
end process; -- End COMB_PROC
end BEHV;
/////////////////////////////////////////////////
// BINARY.V Version 1.0 //
// Example of a binary encoded state machine //
// May 1997 //
/////////////////////////////////////////////////
module binary (CLOCK, RESET, A, B, C, D, E,
SINGLE, MULTI, CONTIG);
input CLOCK, RESET;
input A, B, C, D, E;
output SINGLE, MULTI, CONTIG;
reg SINGLE, MULTI, CONTIG;
// Declare the symbolic names for states
parameter [2:0]
S1 = 3'b001,
S2 = 3'b010,
S3 = 3'b011,
S4 = 3'b100,
S5 = 3'b101,
S6 = 3'b110,
S7 = 3'b111;
// Declare current state and next state variables
reg [2:0] CS;
reg [2:0] NS;
// state_vector CS
always @ (posedge CLOCK or posedge RESET)
begin
if (RESET == 1'b1)
CS = S1;
else
CS = NS;
end
always @ (CS or A or B or C or D or D or E)
begin
case (CS)
S1 :
begin
MULTI = 1'b0;
CONTIG = 1'b0;
SINGLE = 1'b0;
if (A && ~B && C)
NS = S2;
else if (A && B && ~C)
NS = S4;
else
NS = S1;
end
S2 :
begin
MULTI = 1'b1;
CONTIG = 1'b0;
SINGLE = 1'b0;
if (!D)
NS = S3;
else
NS = S4;
end
S3 :
begin
MULTI = 1'b0;
CONTIG = 1'b1;
SINGLE = 1'b0;
if (A || D)
NS = S4;
else
NS = S3;
end
S4 :
begin
MULTI = 1'b1;
CONTIG = 1'b1;
SINGLE = 1'b0;
if (A && B && ~C)
NS = S5;
else
NS = S4;
end
S5 :
begin
MULTI = 1'b1;
CONTIG = 1'b0;
SINGLE = 1'b0;
NS = S6;
end
S6 :
begin
MULTI = 1'b0;
CONTIG = 1'b1;
SINGLE = 1'b1;
if (!E)
NS = S7;
else
NS = S6;
end
S7 :
begin
MULTI = 1'b0;
CONTIG = 1'b1;
SINGLE = 1'b0;
if (E)
NS = S1;
else
NS = S7;
end
endcase
end
endmodule
The recommended encoding style for state machines depends on which synthesis tool you are using. Some synthesis tools encode better than others depending on the device architecture and the size of the decode logic. You can explicitly declare state vectors or you can allow your synthesis tool to determine the vectors. Xilinx recommends that you use enumerated type encoding to specify the states and use the Finite State Machine (FSM) extraction commands to extract and encode the state machine as well as to perform state minimization and optimization algorithms. The enumerated type method of encoding the seven-state machine is shown in the following VHDL and Verilog examples. The encoding style is not defined in the code, but can be specified later with the FSM extraction commands. Alternatively, you can allow your compiler to select the encoding style that results in the lowest gate count when the design is synthesized. Some synthesis tools automatically find finite state machines and compile without the need for specification.
Note: Refer to the previous VHDL and Verilog Binary Encoded State Machine examples for the complete Case statement portion of the code.
Library IEEE;
use IEEE.std_logic_1164.all;
entity enum is
port (CLOCK, RESET : in STD_LOGIC;
A, B, C, D, E: in BOOLEAN;
SINGLE, MULTI, CONTIG: out STD_LOGIC);
end enum;
architecture BEHV of enum is
type STATE_TYPE is (S1, S2, S3, S4, S5, S6, S7);
signal CS, NS: STATE_TYPE;
begin
SYNC_PROC: process (CLOCK, RESET)
begin
if (RESET='1') then
CS <= S1;
elsif (CLOCK'event and CLOCK = '1') then
CS <= NS;
end if;
end process; --End SYNC_PROC
COMB_PROC: process (CS, A, B, C, D, E)
begin
case CS is
when S1 =>
MULTI <= '0';
CONTIG <= '0';
SINGLE <= '0';
.
.
.
/////////////////////////////////////////////////////
// ENUM.V Version 1.0 //
// Example of an enumerated encoded state machine //
// May 1997 //
///////////////////////////////////////////////////
module enum (CLOCK, RESET, A, B, C, D, E,
SINGLE, MULTI, CONTIG);
input CLOCK, RESET;
input A, B, C, D, E;
output SINGLE, MULTI, CONTIG;
reg SINGLE, MULTI, CONTIG;
// Declare the symbolic names for states
parameter [2:0]
S1 = 3'b000,
S2 = 3'b001,
S3 = 3'b010,
S4 = 3'b011,
S5 = 3'b100,
S6 = 3'b101,
S7 = 3'b110;
// Declare current state and next state variables
reg [2:0] CS;
reg [2:0] NS;
// state_vector CS
always @ (posedge CLOCK or posedge RESET)
begin
if (RESET == 1'b1)
CS = S1;
else
CS = NS;
end
always @ (CS or A or B or C or D or D or E)
begin
case (CS)
S1 :
begin
MULTI = 1'b0;
CONTIG = 1'b0;
SINGLE = 1'b0;
if (A && ~B && C)
NS = S2;
else if (A && B && ~C)
NS = S4;
else
NS = S1;
end
.
.
.
One-hot encoding allows you to create state machine implementations that are more efficient for FPGA architectures. One-hot encoding is usually the preferred method for large FPGA-based state machine implementation.
The following examples show a one-hot encoded state machine. Use this method to control the state vector specification or when you want to specify the names of the state registers. These examples use one flip-flop for each of the seven states. If you are using FPGA Express, use enumerated type, and avoid using the “when others” construct in the VHDL case statement. This construct can result in a very large state machine.
Note: Refer to the previous VHDL and Verilog Binary Encoded State Machine examples for the complete Case statement portion of the code. See the “Accelerate FPGA Macros with One-Hot Approach” appendix for a detailed description of one-hot encoding and its applications.
Library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
entity one_hot is
port (CLOCK, RESET : in STD_LOGIC;
A, B, C, D, E: in BOOLEAN;
SINGLE, MULTI, CONTIG: out STD_LOGIC);
end one_hot;
architecture BEHV of one_hot is
type STATE_TYPE is (S1, S2, S3, S4, S5, S6, S7);
attribute ENUM_ENCODING: STRING;
attribute ENUM_ENCODING of STATE_TYPE: type is "0000001 0000010 0000100 0001000 0010000 0100000 1000000 ";
signal CS, NS: STATE_TYPE;
begin
SYNC_PROC: process (CLOCK, RESET)
begin
if (RESET='1') then
CS <= S1;
elsif (CLOCK'event and CLOCK = '1') then
CS <= NS;
end if;
end process; --End SYNC_PROC
COMB_PROC: process (CS, A, B, C, D, E)
begin
case CS is
when S1 =>
MULTI <= '0';
CONTIG <= '0';
SINGLE <= '0';
if (A and not B and C) then
NS <= S2;
elsif (A and B and not C) then
NS <= S4;
else
NS <= S1;
end if;
.
.
.
////////////////////////////////////////////////////
// ONE_HOT.V Version 1.0 //
// Example of a one-hot encoded state machine //
// Xilinx HDL Synthesis Design Guide for FPGAs //
// May 1997 //
////////////////////////////////////////////////
module one_hot (CLOCK, RESET, A, B, C, D, E,
SINGLE, MULTI, CONTIG);
input CLOCK, RESET;
input A, B, C, D, E;
output SINGLE, MULTI, CONTIG;
reg SINGLE, MULTI, CONTIG;
// Declare the symbolic names for states
parameter [6:0]
S1 = 7'b0000001,
S2 = 7'b0000010,
S3 = 7'b0000100,
S4 = 7'b0001000,
S5 = 7'b0010000,
S6 = 7'b0100000,
S7 = 7'b1000000;
// Declare current state and next state variables
reg [2:0] CS;
reg [2:0] NS;
// state_vector CS
always @ (posedge CLOCK or posedge RESET)
begin
if (RESET == 1'b1)
CS = S1;
else
CS = NS;
end
always @ (CS or A or B or C or D or D or E)
begin
case (CS)
S1 :
begin
MULTI = 1'b0;
CONTIG = 1'b0;
SINGLE = 1'b0;
if (A && ~B && C)
NS = S2;
else if (A && B && ~C)
NS = S4;
else
NS = S1;
end
.
.
.
In the three previous examples, the state machine's possible states are defined by an enumeration type. Use the following syntax to define an enumeration type.
type type_name is (enumeration_literal {, enumeration_literal} );
After you have defined an enumeration type, declare the signal representing the states as the enumeration type as follows.
type STATE_TYPE is (S1, S2, S3, S4, S5, S6, S7);
signal CS, NS: STATE_TYPE;
The state machine described in the three previous examples has seven states. The possible values of the signals CS (Current_State) and NS (Next_State) are S1, S2, ... , S6, S7.
To select an encoding style for a state machine, specify the state vectors. Alternatively, you can specify the encoding style when the state machine is compiled. Xilinx recommends that you specify an encoding style. If you do not specify a style, your compiler selects a style that minimizes the gate count. For the state machine shown in the three previous examples, the compiler selected the binary encoded style: S1=“000”, S2=”001”, S3=”010”, S4=”011”, S5=”100”, S6=”101”, and S7=”110”.
You can use the FSM extraction tool to change the encoding style of a state machine. For example, use this tool to convert a binary-encoded state machine to a one-hot encoded state machine.
Note: Refer to your synthesis tool documentation for instructions on how to extract the state machine and change the encoding style.
The following table summarizes the synthesis results from the different methods used to encode the state machine in the three previous VHDL and Verilog state machine examples. The results are for an XC4005EPC84-2 device
Note: The Timing Analyzer was used to obtain the timing results in this table.
| Comparison | One-Hot | Binary | Enum (One-hot) |
|---|---|---|---|
| Occupied CLBs | 6 | 9 | 6 |
| CLB Flip-flops | 6 | 3 | 7 |
| PadToSetup | 9.4 ns (3a) | 13.4 ns (4) | 9.6 ns (3) |
| ClockToPad | 15.1 ns (3) | 15.1 ns (3) | 14.9 ns (3) |
| ClockToSetup | 13.0 ns (4) | 13.9 ns (4) | 10.1 ns (3) |
| a. The number in parentheses represents the CLB block level delay. | |||
The binary-encoded state machine has the longest ClockToSetup delay. Generally, the FSM extraction tool provides the best results because the compiler reduces any redundant states and optimizes the state machine after the extraction.
When creating a state machine, especially when you use one-hot encoding, add the following lines of code to your design to ensure that the FPGA is initialized to a Set state.
SYNC_PROC: process (CLOCK, RESET)
begin
if (RESET='1') then
CS <= s1;
always @ (posedge CLOCK or posedge RESET)
begin
if (RESET == 1'b 1)
CS = S1;
Alternatively, you can assign an INIT=S attribute to the initial state register to specify the initial state. Refer to your synthesis tool documentation for information on assigning this attribute.
In the Binary Encode State Machine example, the RESET signal forces the S1 flip-flop to be preset (initialized to 1) while the other flip-flops are cleared (initialized to 0).