Finite state machine (FSM) is one of the first topics taught in any digital design course, yet coding one is not as easy as first meets the eye. There are Moore and Mealy state machines, encoded and one-hot state encoding, one or two or three always block coding styles. Recently I was reviewing a coworker’s RTL code and came across a SystemVerilog one-hot state machine coding style that I was not familiar with. Needless to say, it became a mini research topic resulting in this blog post.
When coding state machines in Verilog or SystemVerilog, there are a few general guidelines that can apply to any state machine:
- If coding in Verilog, use parameters to define state encodings instead of ‘define macro definition. Verilog ‘define macros have global scope; a macro defined in one module can easily be redefined by a macro with the same name in a different module compiled later, leading to macro redefinition warnings and unexpected bugs.
- If coding in SystemVerilog, use enumerated types to define state encodings.
- Always define a parameter or enumerated type value for each state so you don’t leave it to the synthesis tool to choose a value for you. Otherwise it can make for a very difficult ECO when it comes time to reverse engineer the gate level netlist.
- Make curr_state and next_state declarations right after the parameter or enumerated type assignments. This is simply clean coding style.
- Code all sequential always block using nonblocking assignments (<=). This helps guard against simulation race conditions.
- Code all combinational always block using blocking assignments (=). This helps guard against simulation race conditions.
SystemVerilog enumerated types are especially useful for coding state machines. An example of using an enumerated type as the state variable is shown below.
typedef enum {
IDLE = 2'b00,
ACTIVE = 2'b01,
DONE = 2'b10,
XX = 'x
} state_t;
state_t curr_state, next_state;
Notice that enumerated types allow X assignments. Enumerated types can be displayed as names in simulator waveforms, which eliminates the need of a Verilog trick to display the state name in waveform as a variable in ASCII encoding.
One-hot refers to how each of the states is encoded in the state vector. In a one-hot state machine, the state vector has as many bits as number of states. Each bit represents a single state, and only one bit can be set at a time—one-hot. A one-hot state machine is generally faster than a state machine with encoded states because of the lack of state decoding logic.
SystemVerilog and Verilog has a unique (pun intended) and efficient coding style for coding one-hot state machines. This coding style uses what is called a reverse case statement to test if a case item is true by using a case header of the form case (1’b1). Example code is shown below:
enum {
IDLE = 0,
READ = 1,
DLY = 2,
DONE = 3
//} state, next; // Original not completely correct code
} state_index_t;
logic [3:0] state, next; // Corrected. Thanks John!
// Sequential state transition
always_ff @(posedge clk or negedge rst_n)
if (!rst_n) begin
state <= '0; // default assignment
state[IDLE] <= 1'b1;
end
else
state <= next;
// Combinational next state logic
always_comb begin
next = '0;
unique case (1'b1)
state[IDLE] : begin
if (go)
next[READ] = 1'b1;
else
next[IDLE] = 1'b1;
end
state[READ] : next[ DLY] = 1'b1;
state[ DLY] : begin
if (!ws)
next[DONE] = 1'b1;
else
next[READ] = 1'b1;
end
state[DONE] : next[IDLE] = 1'b1;
endcase
end
// Make output assignments
always_ff @(posedge clk or negedge rst_n)
...
In this one-hot state machine coding style, the state parameters or enumerated type values represent indices into the state and next vectors. Synthesis tools interpret this coding style efficiently and generates output assignment and next state logic that does only 1-bit comparison against the state vectors. Notice also the use of always_comb and always_ff SystemVerilog always statements, and unique case to add some run-time checking.
An alternate one-hot state machine coding style to the “index-parameter” style is to completely specify the one-hot encoding for the state vectors, as shown below:
enum {
IDLE = 4'b0001,
READ = 4'b0010,
DLY = 4'b0100,
DONE = 4'b1000
} state, next;
According to Cliff Cummings’ 2003 paper, this coding style yields poor performance because the Design Compiler infers a full 4-bit comparison against the state vector, in effect defeating the speed advantage of a one-hot state machine. However, the experiments conducted in this paper were done in 2003, and I suspect synthesis tools have become smarter since then.
State machines may look easy on paper, but are often not so easy in practice. Given how frequently state machines appear in designs, it is important for every RTL designer to develop a consistent and efficient style for coding them. One-hot state machines are generally preferred in applications that can trade-off area for a speed advantage. This article demonstrated how they can be coded in Verilog and SystemVerilog using a unique and very efficient “reverse case statement” coding style. It is a technique that should be in every RTL designer’s arsenal.
What are your experiences with coding one-hot state machines? Do you have another coding style or synthesis results to share? Leave a comment below!
Hi Jason,
I am enjoying reading your blog, but I believe you are missing something from your one-hot reverse-case example above. In Cliff’s paper, the enumerated type is used as an index to a vector – you neglected to copy this part over. I believe the correct code would look like this:
enum {
IDLE = 0,
READ = 1,
DLY = 2,
DONE = 3
} state_index_t;
logic [3:0] state, next;
with the vector declaration in place the rest of the example above should work OK.
Hi John, thanks for your comment! You’re correct that in Cliff’s paper the enumerated type is used as an index into the one-hot vector. In my original code above I was sloppy and mixed the value of the enumerated type (0, 1, 2, 3) with the type itself. While I did test the original code and it simulated correctly, I’m sure a linting tool would give a warning about the improper usage. I have made a correction to the code above.
Hi Jason,
Great post. I have seen improved performance with one hot reverse case statements as well.
One comment I would have is that the default assignment for “next” should be a valid case especially since we don’t have a default case statement. In the case of a bit being flipped because of some rare condition you’ll be able to recover. Something like this:
// Combinational next state logic
always_comb begin
next = ‘0;
next[IDLE] = 1’b1; // ADDED
unique case (1’b1)
state[IDLE] : begin
if (go) begin
next = ‘0; // ADDED
next[READ] = 1’b1;
end else begin
next = ‘0; // ADDED
next[IDLE] = 1’b1;
end
end
Thanks, Amol, for your suggestion. I understand your reasoning to have a valid case (like IDLE) be the default transition for safety. Personally I don’t code that way as I think a bit flip anywhere in the chip is considered fatal, and even if the affected state machine returns to IDLE, it will likely have become out of sync with other logic and state machines. However, I have coworkers who code in the way you suggested as well.
There is a subtle point that may cause your code to not behave in the way intended. Due to the use of “unique case” in the code, I think for any unspecified cases (e.g. if a bit flip causes the state vector to become 4’b0000; 4’b0000 is not a case that is listed in the case statement), the synthesis tool is free to infer any logic (specifically to the “next” vector), so there’s no guarantee the default “next[IDLE]=1’b1” wouldn’t be overridden by other logic the synthesis tool inferred. See my post on SystemVerilog unique keyword.
Interesting. I had a “typo” in my code recently that caused the case_expression to be one not listed in the case statement and I did observe odd behavior from what I would have expected. So I guess having the default “next[IDLE]=1’b1” is probably not that useful here. 🙂
This is a synthetic example I would assume but want to get your feedback on preserving X-propagation. Bugs in the state machine next state logic or outside the state machine driving the input signals “go” and “ws” can be hidden by the current way of coding (using if-else and also default assigned to 0). Killing x-prop can cause “simulation vs. synthesis mismatch”, which can be pretty fatal. Consider this improvement:
// Combinational next state logic
always_comb begin
//next = ‘0; // Comment out; see added default in case statement instead
unique case (1’b1)
state[IDLE] : begin
// Ensures x-prop if go === x
next[READ] = go == 1’b1;
next[IDLE] = go == 1’b0;
end
state[READ] : next[ DLY] = 1’b1;
state[ DLY] : begin
// Ensures x-prop if ws === x
next[DONE] = ws == 1’b0;
next[READ] = ws == 1’b1;
end
state[DONE] : next[IDLE] = 1’b1;
// Add default to propagate Xs for unhandled states or if state reg went X itself
default: next <= 'x;
endcase
end
Hi VK, thanks for your comment! When you say the code “kills x-prop”, I think you mean that if “ws” or “go” input has the value of X, then the “if(x)-else” coding style will take on the “else” case, rather than also corrupting the outputs (in this case the “next” vector)? Yes you’re right, and I’ll admit I’ve coded this kind of bug before! Recently our team has turned on the Synopsys VCS x-propagation feature to detect this kind of problem. It corrupts the output even with this “if-else” coding style (see my post on x-prop). If that’s not available, then yes, the code you propose will also do the job. Previously I also coded a “default: next <= 'x" in my state machines, but the RTL linting tool we use complains about this, so I've moved away from this style. VCS x-prop will also catch this kind of problem.
I just realized you are not driving every bit of “next” in the case statement, so you would need to have the default next = ‘0 at the beginning as you did originally. That would not kill x-prop anyways since the default in the case statement would override it if needed.
Hello Jason,
Thanks for the post. It really helped me to understand more about OneHot FSMs.
The statement on Cliff’s paper in 2003 is not entirely true. we can handle that case by adding a unique key word. In the meantime concern raised by VK is great and worth looking into. with both of this I would like you to consider the following code which will give you the same synthesis result.
Advantages being
1) state vector is enum, hence waveform visualization is better
2) does propagate x, in case FSM assignment is buggy
3) simpler and easy to read
typedef enum logic [3:0] {
IDLE = 4’b0001,
READ = 4’b0010,
DLY = 4’b0100,
DONE = 4’b1000,
SX = 4’x
} state_t;
state_t state, next;
// Sequential state transition
always_ff @(posedge clk or negedge rst_n)
if (!rst_n)
state <= IDLE;
else
state <= next;
// Combinational next state logic
always_comb begin
next = SX;
unique case (state)
IDLE : begin
if (go)
next = READ;
else
next = IDLE;
end
READ : next = DLY;
DLY : begin
if (!ws)
next = DONE;
else
next = READ;
end
DONE : next = IDLE;
endcase
end
// Make output assignments
always_ff @(posedge clk or negedge rst_n)
…
Thanks for your comments! Yes I had been intending to make an update to this page for while, especially about your first point on waveform display of the state vector. After simulating my coworker’s code in the original coding style, I also realized simulators do not visualize state vectors written this way very well. I would agree that specifying the one-hot state encoding in the enum type should be equivalent and will display better. Your proposed code is indeed how I would write a one-hot state machine using SystemVerilog today!
Hi Jason
Reffering to the last comment by shailesh, do you still suggests using “reverse case method” for FSM ? is it worth the less-readable code?
or that shailesh’s code will do the same w/o infers the full bit comparison? this code is much more initiuative, but what about performence?
I have not had a chance to look closely at the synthesized netlist of a one-hot encoded state machine written with enumerated type and regular case statement. I believe with today’s compiler technology it should synthesize the same as the reverse case statement method (i.e. optimized to do single state bit comparisons). I coded my most recent design this way based on this belief. I’ll let you know when I can verify exactly the gates that Design Compiler synthesized 🙂
Thanks for the article, Jason. Your articles have helped answer many questions I’ve had. My colleague and I were discussing about this recently and a question came up – Are reverse case statements useful at all in plain Verilog (not System Verilog) if one isn’t allowed to use synthesis pragmas such as ‘parallel_case’? Unlike System Verilog, Verilog doesn’t have the ‘unique’ keyword.
Put in another way, the question is what really happens when one codes a reverse case statement in Verilog with no ‘parallel_case’ directive. Does synthesis assume that the input to the case-statement is not parallel and hence not one-hot and hence infer priority logic? I’d love to hear your thoughts.
I think if coded correctly, the reverse case statement FSM coding style should automatically create a case statement that is parallel, without requiring the ‘parallel_case’ directive. Since each state is represented by a unique number, each case expression is effectively comparing 1 unique register bit against 1’b1. Therefore no overlap between the different case expressions should be possible, which matches the definition of parallel case.