Archives for the month of: January, 2012

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

Advertisements

Latches Inferred

This blog is named after a frustrating warning message which is sometimes encountered during synthesis of Verilog code. This blog post explains what that warning means, why you may encounter it, and how to remedy the situation.

What is a Latch

A latch, like a flip-flop, is a kind of state-element in digital circuits. While a flip-flop captures the input and propagates it to the output upon clock edges, however, the latch captures the input at all times while the clock is high and only while the clock is high. This is known as its “transparent” state (since the input flows directly to the output; the output side of the latch can “see” the input). When the clock is low, the latch is in its “opaque” state (since the input does not propagate to output; the output side cannot “see” the input). During the opaque state, the output remains at whatever value was on the input of the latch at the time the clock went low. In this way it is similar to a negative-edge triggered flip-flop. The only difference between them is that the latch also propagates input to output at all other times when the clock is high, not just before a negative edge. Below is a waveform to help make the functionality of a latch more clear:

Waveform of a D Latch

Waveform of a D Latch

The schematic symbol for a latch is show below:

Gated D Latch

Gated D Latch

How to Code a Latch in Verilog

Below is some Verilog-1995 code which properly codes a latch:

module latch(output q, input d, input gate);
    reg q;
    wire d, gate;
    always @(gate, d) begin
        if(gate)
            q <= d;
    end
endmodule

In this case, the clock would be connected to the gate. Below is a SystemVerilog implementation of a latch:

module latch(output logic q, input logic d, input logic gate);
    always_latch begin
        if(gate)
        q <= d;
    end
endmodule

When the gate is a logic 1, the input propagates to the output. When the clock is low, it remains the same, by default. The simulator makes no changes to the variable if the gate is low and thus this is the behavior of the code when synthesized into an actual design.

How to Avoid Coding a Latch in Verilog

If you get a “latches inferred” warning, chances are, you probably don’t want it. Latch-based designs have certain advantages (they are smaller than flip-flops and can be used to create a faster design using a principle called time-borrowing), but are comparatively rare.

In order to avoid having latches in your design, you must follow one of the golden rules of combinational logic:

All combinational outputs must be assigned for every possible input pattern.

The implication this has for coding is:

Assign all combinational outputs for every possible control-flow path through an always block.

What this means is that whatever conditions exist which cause you to execute certain lines of code in your always block, all outputs must be specified in order to qualify as combinational logic. The latch code above violates this principle because if gate is a logic 0, q is left unspecified. As a result, the simulator leaves it equal to its current (i.e. past) value – which implies memory or state, not combinational logic.

For a more in-depth explanation of latches and this warning message, see: http://www.doulos.com/knowhow/fpga/latches/

This is a fresh start at a blog about Verilog! The goal of this blog is to provide insightful tips and tricks to those grappling with digital design in both Verilog and SystemVerilog. I also plan to make posts about interesting projects I am working on or discoveries I make.

I (currently) a senior in Electrical and Computer Engineering at Carnegie Mellon University with a focus in digital logic design. I have taken several courses with projects written in Verilog and SystemVerilog including:

18-240: Structure and Design of Digital Systems
18-341: Logic Design Using Simulation, Synthesis, and Verification Techniques
18-340: Digital Computation
18-447: Introduction to Computer Architecture

My projects for these classes include the Mastermind game  for the Spartan 3 FPGA, a gate-level implementation of a 32-bit IEEE floating-point unit, a partial USB 2.0 device controller, and a MIPS architecture. For Build18, a student-run ECE-project organization at CMU, I plan to help design a game of tetris which will run on the Xilinx Virtex-V FPGA and will use a PS/2 keyboard and supply VGA output.

In addition, this spring will be my second semester working as a teaching assistant for 18-240. Students of this class in particular may find the contents of this to be helpful – at least that is my hope :)