12.7 Finite-State Machine Synthesis

12.7  Finite-State Machine Synthesis

There are three ways to synthesize a finite-state machine ( FSM ):

  1. Omit any special synthesis directives and let the logic synthesizer operate on the state machine as though it were random logic. This will prevent any reassignment of states or state machine optimization. It is the easiest method and independent of any particular synthesis tool, but is the most inefficient approach in terms of area and performance.
  2. Use directives to guide the logic synthesis tool to improve or modify state assignment. This approach is dependent on the software that you use.
  3. Use a special state-machine compiler, separate from the logic synthesizer, to optimize the state machine. You then merge the resulting state machine with the rest of your logic. This method leads to the best results but is harder to use and ties your code to a particular set of software tools, not just the logic synthesizer.

Most synthesis tools require that you write a state machine using a certain style—a special format or template. Synthesis tools may also require that you declare an FSM, the encoding, and the state register using a synthesis directive or special software command. Common FSM encoding options are:

  • Adjacent encoding assigns states by the minimum logic difference in the state transition graph. This normally reduces the amount of logic needed to decode each state. The minimum number of bits in the state register for an FSM with n states is log 2 n . In some tools you may increase the state register width up to n to generate encoding based on Gray codes.
  • One-hot encoding sets one bit in the state register for each state. This technique seems wasteful. For example, an FSM with 16 states requires 16 flip-flops for one-hot encoding but only four if you use a binary encoding. However, one-hot encoding simplifies the logic and also the interconnect between the logic. One-hot encoding often results in smaller and faster FSMs. This is especially true in programmable ASICs with large amounts of sequential logic relative to combinational logic resources.
  • Random encoding assigns a random code for each state.
  • User-specified encoding keeps the explicit state assignment from the HDL.
  • Moore encoding is useful for FSMs that require fast outputs. A Moore state machine has outputs that depend only on the current state (Mealy state machine outputs depend on the current state and the inputs).

You need to consider how the reset of the state register will be handled in the synthesized hardware. In a programmable ASIC there are often limitations on the polarity of the flip-flop resets. For example, in some FPGAs all flip-flop resets must all be of the same polarity (and this restriction may or may not be present or different for the internal flip-flops and the flip-flops in the I/O cells). Thus, for example, if you try to assign the reset state as '0101' , it may not be possible to set two flip-flops to '0' and two flip-flops to '1' at the same time in an FPGA. This may be handled by assigning the reset state, resSt , to '0000' or '1111' and inverting the appropriate two bits of the state register wherever they are used.

You also need to consider the initial value of the state register in the synthesized hardware. In some reprogrammable FPGAs, after programming is complete the flip-flops may all be initialized to a value that may not correspond to the reset state. Thus if the flip-flops are all set to '1' at start-up and the reset state is '0000' , the initial state is '1111' and not the reset state. For this reason, and also to ensure fail-safe behavior, it is important that the behavior of the FSM is defined for every possible value of the state register.

12.7.1 FSM Synthesis in Verilog

The following FSM model uses paired processes . The first process synthesizes to sequential logic and the second process synthesizes to combinational logic:

`define resSt 0

`define S1 1

`define S2 2

`define S3 3

module StateMachine_1 (reset, clk, yOutReg);

input reset, clk; output yOutReg;

reg yOutReg, yOut; reg [1:0] curSt, nextSt;

always @( posedge clk or posedge reset)

begin :Seq //Compass statemachine oneHot curSt

if (reset == 1)

begin yOut = 0; yOutReg = yOut; curSt = `resSt; end

else begin

case (curSt)

`resSt:yOut = 0;`S1:yOut = 1;`S2:yOut = 1;`S3:yOut = 1;

default :yOut = 0;

endcase

yOutReg = yOut; curSt = nextSt; // ... update the state.

end

end

always @(curSt or yOut) // Assign the next state:

begin :Comb

case (curSt)

`resSt:nextSt = `S3; `S1:nextSt = `S2;

`S2:nextSt = `S1; `S3:nextSt = `S1;

default :nextSt = `resSt;

endcase

end

endmodule

Synopsys uses separate pseudocomments to define the states and state vector as in the following example:

module StateMachine_2 (reset, clk, yOutReg);

input reset, clk; output yOutReg; reg yOutReg, yOut;

parameter [1:0] //synopsys enum states

resSt = 2'b00, S1 = 2'b01, S2 = 2'b10, S3 = 2'b11;

reg [1:0] /* synopsys enum states */ curSt, nextSt;

//synopsys state_vector curSt

always @( posedge clk or posedge reset) begin

if (reset == 1)

begin yOut = 0; yOutReg = yOut; curSt = resSt; end

else begin

case (curSt) resSt:yOut = 0;S1:yOut = 1;S2:yOut = 1;S3:yOut = 1;

default :yOut = 0; endcase

yOutReg = yOut; curSt = nextSt; end

end

always @(curSt or yOut) begin

case (curSt)

resSt:nextSt = S3; S1:nextSt = S2; S2:nextSt = S1; S3:nextSt = S1;

default :nextSt = S1; endcase

end

endmodule

To change encoding we can assign states explicitly by altering lines 3 4 to the following, for example:

parameter [3:0] //synopsys enum states

resSt = 4'b0000, S1 = 4'b0010, S2 = 4'b0100, S3 = 4'b1000;

12.7.2 FSM Synthesis in VHDL

The first architecture that follows is a template for a Moore state machine:

library IEEE; use IEEE.STD_LOGIC_1164. all ;

entity SM1 is

port (aIn, clk : in Std_logic; yOut: out Std_logic);

end SM1;

architecture Moore of SM1 is

type state is (s1, s2, s3, s4);

signal pS, nS : state;

begin

process (aIn, pS) begin

case pS is

when s1 => yOut <= '0'; nS <= s4;

when s2 => yOut <= '1'; nS <= s3;

when s3 => yOut <= '1'; nS <= s1;

when s4 => yOut <= '1'; nS <= s2;

end case ;

end process ;

process begin

-- synopsys etc.

--compass Statemachine adj pS

wait until clk = '1'; pS <= nS;

end process ;

end Moore;

An example input, aIn , is included but not used in the next state assignments. A reset is also omitted to further simplify this example.

An FSM compiler extracts the state machine. Some companies use FSM compilers that are separate from the logic synthesizers (and priced separately) because the algorithms for FSM optimization are different from those for optimizing combinational logic. We can see what is happening by asking the Compass synthesizer to write out intermediate results. The synthesizer extracts the FSM and produces the following output in a state-machine language used by the tools:

sm sm1_ps_sm;

inputs; outputs yout_smo; clock clk;

STATE S1 { let yout_smo=0 ; } --> S4;

STATE S2 { let yout_smo=1 ; } --> S3;

STATE S3 { let yout_smo=1 ; } --> S1;

STATE S4 { let yout_smo=1 ; } --> S2;

end

You can use this language to modify the FSM and then use this modified code as an input to the synthesizer if you wish. In our case, it serves as documentation that explains the FSM behavior.

Using one-hot encoding generates the following structural Verilog netlist ( dfntnb is positive-edge–triggered D flip-flop, and nd03d0 is a three-input NAND):

dfntnb sm_ps4(.D(sm_ps1_Q),.CP(clk),.Q(sm_ps4_Q),.QN(sm_ps4_QN));

dfntnb sm_ps3(.D(sm_ps2_Q),.CP(clk),.Q(sm_ps3_Q),.QN(sm_ps3_QN));

dfntnb sm_ps2(.D(sm_ps4_Q),.CP(clk),.Q(sm_ps2_Q),.QN(sm_ps2_QN));

dfntnb sm_ps1(.D(sm_ps3_Q),.CP(clk),.Q(sm_ps1_Q),.QN(\sm_ps1.QN ));

nd03d0 i_6(.A1(sm_ps4_QN),.A2(sm_ps3_QN),.A3(sm_ps2_QN), .ZN(yout_smo));

(Each example shows only the logic cells and their interconnection in the Verilog structural netlists.) The synthesizer has assigned one flip-flop to each of the four states to form a 4-bit state register. The FSM output (renamed from yOut to yout_smo by the software) is taken from the output of the three-input NAND gate that decodes the outputs from the flip-flops in the state register.

Using adjacent encoding gives a simpler result,

dfntnb sm_ps2(.D(i_4_ZN),.CP(clk), .Q(\sm_ps2.Q ),.QN(sm_ps2_QN));

dfntnb sm_ps1(.D(sm_ps1_QN),.CP(clk),.Q(\sm_ps1.Q ),.QN(sm_ps1_QN));

oa04d1 i_4(.A1(sm_ps1_QN),.A2(sm_ps2_QN),.B(yout_smo),.ZN(i_4_ZN));

nd02d0 i_5(.A1(sm_ps2_QN), .A2(sm_ps1_QN), .ZN(yout_smo));

( oa04d1 is an OAI21 logic cell, nd02d0 is a two-input NAND). In this case binary encoding for the four states uses only two flip-flops. The two-input NAND gate decodes the states to produce the output. The OAI21 logic cell implements the logic that determines the next state. The combinational logic in this example is only slightly more complex than that for the one-hot encoding, but, in general, combinational logic for one-hot encoding is simpler than the other forms of encoding.

Using the option 'moore' for Moore encoding, we receive the following message from the FSM compiler:

The states were assigned these codes:

0?? : S1       100 : S2       101 : S3       110 : S4

The FSM compiler has assigned three bits to the state register. The first bit in the state register is used as the output. We can see more clearly what has happened by looking at the Verilog structural netlist:

dfntnb sm_ps3(.D(i_6_ZN),.CP(clk),.Q(yout_smo),.QN(sm_ps3_QN));

dfntnb sm_ps2(.D(sm_ps3_QN),.CP(clk),.Q(sm_ps2_Q),.QN(\sm_ps2.QN ));

dfntnb sm_ps1(.D(i_5_ZN),.CP(clk),.Q(sm_ps1_Q),.QN(\sm_ps1.QN ));

nr02d0 i_5(.A1(sm_ps3_QN),.A2(sm_ps2_Q),.ZN(i_5_ZN));

nd02d0 i_6(.A1(sm_ps1_Q),.A2(yout_smo),.ZN(i_6_ZN));

The output, yout_smo , is now taken directly from a flip-flop. This means that the output appears after the clock edge with no combinational logic delay (only the clock-to-Q delay). This is useful for FSMs that are required to produce outputs as soon as possible after the active clock edge (in PCI bus controllers, for example).

The following code is a template for a Mealy state machine:

library IEEE; use IEEE.STD_LOGIC_1164. all ;

entity SM2 is

port (aIn, clk : in Std_logic; yOut: out Std_logic);

end SM2;

architecture Mealy of SM2 is

type state is (s1, s2, s3, s4);

signal pS, nS : state;

begin

process (aIn, pS) begin

case pS is

when s1 => if (aIn = '1')

then yOut <= '0'; nS <= s4;

else yOut <= '1'; nS <= s3;

end if ;

when s2 => yOut <= '1'; nS <= s3;

when s3 => yOut <= '1'; nS <= s1;

when s4 => if (aIn = '1')

then yOut <= '1'; nS <= s2;

else yOut <= '0'; nS <= s1;

end if ;

end case ;

end process ;

process begin

wait until clk = '1' ;

--Compass Statemachine oneHot pS

pS <= nS;

end process ;

end Mealy;


Chapter start ] [ Previous page ] [ Next page ]

Trimble
Teledyne Optech
CADalog.com - Countless CAD add-ons, plug-ins and more.



Internet Business Systems © 2016 Internet Business Systems, Inc.
595 Millich Dr., Suite 216, Campbell, CA 95008
+1 (408)-337-6870 — Contact Us, or visit our other sites:
AECCafe - Architectural Design and Engineering EDACafe - Electronic Design Automation TechJobsCafe - Technical Jobs and Resumes  MCADCafe - Mechanical Design and Engineering ShareCG - Share Computer Graphic (CG) Animation, 3D Art and 3D Models
  Privacy Policy