|
|
|
|
|
Encoding State Machines
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.
Using Binary Encoding
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 5-5 State Machine Bubble Diagram
Binary Encoded State Machine VHDL Example
The following is a binary encoded state machine VHDL example.
-------------------------------------------------
-- Example of a binary encoded state machine --
-------------------------------------------------
use IEEE.std_logic_unsigned.all;
port (CLOCK, RESET : in STD_LOGIC;
SINGLE, MULTI, CONTIG: out STD_LOGIC);
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";
SYNC_PROC: process (CLOCK, RESET)
elsif (CLOCK'event and CLOCK = '1') then
COMB_PROC: process (CS, A, B, C, D, E)
elsif (A and B and not C) then
Binary Encoded State Machine Verilog Example
/////////////////////////////////////////////////
// Example of a binary encoded state machine //
/////////////////////////////////////////////////
module binary (CLOCK, RESET, A, B, C, D, E, SINGLE, MULTI, CONTIG);
// Declare the symbolic names for states
// Declare current state and next state variables
always @ (posedge CLOCK or posedge RESET)
always @ (CS or A or B or C or D or D or E)
Using Enumerated Type Encoding
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.
Enumerated Type Encoded State Machine VHDL Example
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'; . . .Enumerated Type Encoded State Machine Verilog Example
/////////////////////////////////////////////////// // ENUM.V Version 1.0 // // Example of an enumerated encoded state machine// // May 2001 // /////////////////////////////////////////////////// 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 . . .Using One-Hot Encoding
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.
One-hot Encoded State Machine VHDL Example
use IEEE.std_logic_unsigned.all;
port (CLOCK, RESET : in STD_LOGIC;
SINGLE, MULTI, CONTIG: out STD_LOGIC);
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 ";
SYNC_PROC: process (CLOCK, RESET)
elsif (CLOCK'event and CLOCK = '1') then
COMB_PROC: process (CS, A, B, C, D, E)
elsif (A and B and not C) then
One-hot Encoded State Machine Verilog Example
///////////////////////////////////////////////// // ONE_HOT.V Version 1.0 // // Example of a one-hot encoded state machine ' // // Xilinx HDL Synthesis Design Guide for FPGAs // // May 2001 // ////////////////////////////////////////////////// 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 . . .Accelerating FPGA Macros with One-Hot Approach
Most synthesis tools provide a setting for finite state machine (FSM) encoding. This setting will prompt synthesis tools to automatically extract state machines in your design and perform special optimizations to achieve better performance. The default option for FSM encoding is "One-Hot" for most synthesis tools. However, this setting can be changed to other encoding such as binary, grey, sequential, etc.
In FPGA Express, FSM encoding is set to "One-Hot" by default. To change this setting, select Synthesis-> Options -> Project Tab. Available options are: One-Hot, Binary, and Zero One-Hot.
In LeonardoSpectrum, FSM encoding is set to "Auto" by default which differs depending on Bit Width of your state machine. To change this setting to a specific value, select Input tab. Available options are: Binary, One-Hot, Random, Gray, and Auto.
In Synplify, the Symbolic FSM Complier option can be accessed from the main GUI. When set, the FSM Compiler extracts the state machines as symbolic graphs, and then optimizes them by re-encoding the state representations and generating a better logic optimization starting point for the state machines. This usually results in one-hot encoding. However, you may override the default on a register by register bases with the syn_encoding directive/attribute. Available options are: One-Hot, Gray, Sequential, and Safe.
In XST, FSM encoding is set to Auto by default. Available options are: Auto, Compact, Gray, Johnson, Sequential, and User.
Note XST will only recognize enumerated encoding if the encoding option is set to User.
Summary of Encoding Styles
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.
Initializing the State Machine
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.
- VHDL Example
SYNC_PROC: process (CLOCK, RESET) begin if (RESET='1') then CS <= s1;- Verilog Example
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).
|
|
|
