FSM Design Techniques

This post is about a paper entitled “Synthesizable Finite State Machine Design Techniques using the new SystemVerilog 3.0 Enhancements” written by Clifford E. Cummings. Though this paper is a bit dated (published in 2003), it contains a lot of interesting and helpful information about FSM design. I highly recommend reading the paper in full (not including the title page, References section, and the code listings at the end, it is just over 33 pages). If you don’t have time for that, however, I provide a brief summary of the paper and list some of the more interesting things I learned from it.

Summary

The paper begins by discussing several coding styles for FSMs written in Verilog-1995. Several coding goals are identified, such as being compact and easy to debug, which leads to several coding guidelines. In section 2, the author reviews six standard Verilog FSM coding styles of which four are recommended and two are discouraged. Schematics and corresponding code are given for a simple FSM example. In sections 3, 4, and 5 the author considers three additional more complex FSMs, showing their state transition diagrams. He contrasts the number of lines of code required to implement each of these FSMs in a recommend coding style and a discouraged coding style. Section 6 presents a graph plotting lines of code for each of the four FSMs for each of the six coding styles. Section 7 presents timing and area synthesis benchmarks for each of the four FSMs. Section 8 shows the timing and area improvements provided by the use of a few Design Compiler optimization flags. Sections 9 and 10 discuss improvements introduced by Verilog-2001 and SystemVerilog respectively.

New One-Hot Coding Style

I learned a completely new way to implement one-hot finite state machines. The paper refers to this approach as index-parameter style. This method defines state parameters as consecutive integers which serve as bit indexes into the state register rather than defining states as the full one-hit bit patterns. It then uses a reverse case statement of the form case(1’b1) as in the following code excerpt:

parameter IDLE = 0,
          READ = 1,
          DLY  = 2,
          DONE = 3;

always @(state or go or ws) begin
    next = 4'b0;
    case (1'b1) // synopsys parallel_case
        state[IDLE] : if (go)  next[READ] = 1'b1;
        else                   next[IDLE] = 1'b1;
        state[READ] :          next[ DLY] = 1'b1;
        state[ DLY] : if (!ws) next[DONE] = 1'b1;
        else                   next[READ] = 1'b1;
        state[DONE] :          next[IDLE] = 1'b1;
    endcase
end

As the paper goes on to show, the use of this coding style results in faster and smaller designs than the coding style in which the states are defined as full one-hot bit patterns like so:

parameter IDLE = 4'b0001,
          READ = 4'b0010,
          DLY  = 4'b0100,
          DONE = 4'b1000;

This style requires comparing lengthy bit patterns as opposed to simply each individual bit against 1. Consequently, it requires more gates, which means more time and area.

Two Always Block is Best

I learned that using two always blocks (one combinational block for the output and next state logic and one sequential block for the state register) tends to be at least as good if not better than one always block (which implicitly contains the next state and output logic within the single sequential block for the next state) and the three always block (which separates the output logic and next state logic into their own combinational blocks) coding styles with regard to area and timing analysis. Fortunately this is already my preferred coding style for FSMs but it is good to know!

.name Port Connections

Not only does SystemVerilog include .* implicit port connection capability, it also supports .name convention. This convention is the same as .name(name) but saves typing when the name of the port within the instantiated module matches the name within the module in which it is instantiated.

‘x, ‘z, ‘0, and ‘1 assignments

SystemVerilog introduces syntax for assigning all 1’s, all 0’s, all X’s, and all Z’s to bit vectors of arbitrary length. For example:

foo <= ‘1;

will assign all 1’s to foo regardless of its bitwidth. Likewise for ‘x, ‘z and ‘0.

Other Important Points

The paper also points out several good elements of coding style which every Verilog coder should know:

• Always provide default next state and output logic assignments above your case statements.
• Using x’s when possible to improve optimization and assist in debugging (an unexpected transition to state ‘x is a red flag).
• Use parameters rather than `define macros when possible.

And of course:

• Code all sequential always blocks using non-blocking assignments.
• Code all combinational always blocks using blocking assignments.

Clifford E. Cummings

Cliff Cummings, President of Sunburst Design, Inc., is an independent EDA consultant and trainer with 21 years of ASIC, FPGA and system design experience and 11 years of Verilog, synthesis and methodology training experience.

Mr. Cummings, a member of the IEEE 1364 Verilog Standards Group (VSG) since 1994, is the only Verilog and SystemVerilog trainer to co-develop and co-author the IEEE 1364-1995 Verilog Standard, IEEE 1364-2001 Verilog Standard, IEEE 1364.1-2002 Verilog RTL Synthesis Standard and the Accellera SystemVerilog 3.0 Standard.

Mr. Cummings holds a BSEE from Brigham Young University and an MSEE from Oregon State University.

Email address: cliffc@sunburst-design.com