How to create a finite state machine in Verilog

This article describes the basics of finite state machines and shows a practical way to implement them in the Verilog hardware description language.

Finite state machines, or FSMs for short, are one of the most ubiquitous operating models in both hardware and software systems. Almost every useful digital system can be defined as a finite state machine, so it's good to learn as much as possible about this useful system pattern.

Finite state machines in digital circuits

There are many ways to describe a finite state machine, but the two most popular are state diagrams and state tables. Examples of both representations are shown in Figure 1.

Figure 1. An FSM displayed as a state diagram and state table. The legend in the upper left corner shows the state variables A and B, as well as the input x and output y.

Note that this FSM has one input signal x and one output signal y, which makes it a Mealy state machine. This FSM can be implemented using the traditional approach taught in digital design courses, which revolves around generating stimulus logic for the flip-flops that implement the state variables. This logic is designed based on the stimulus table for the chosen flip-flop type, i.e., SR, D, JK, or T.

When we apply this technique to the FSM in Figure 1, we get some version of the following implementation.

Figure 2. Implementation of an example FSM using JK flip-flops.

For more information on state machines, you may want to read David Williams' article Implementing Finite State Machines in VHDL.

How Verilog Helps

So if you want to implement a state machine like the one in Figure 1 in Verilog, how do you do it? At what stage in the design process should Verilog take over?

While it is possible to manually design the entire system, all the way down to the schematic in Figure 2, and then write the code in Verilog, this is not the most popular way to solve the problem. A worse approach would be to describe every single gate in the schematic, including the gates that make up the flip-flops! Your system may work in some way if you describe everything at the gate level, but this leaves no room for the compiler to optimize your design to meet your actual needs, which may be more concerned with timing and power than just correctness.

Remember: the reason for using a hardware description language is to take advantage of the synthesis compiler you'll be using, and like any compiler, the more freedom you give it, the more likely you are to produce an optimal implementation.

So a smart starting point is a state table. You simply instruct the Verilog machine what to do in each state, not which gates or flip-flops to use.

In Verilog, an excellent construct for state machines is the Case statement. The body of each case should check the state variable and its expected behavior. The following code snippet shows this structure.

case (state)

STATE_0: // Code for State 0

STATE_1: // Code for State 1

//   ...

STATE_N: // Code for State N

endcase

So, using our example, this is the implementation of the state machine shown in Figure 1. Note that the output y is a combinatorial function.

module MyFSM(

input clk,

input x,

output y);

reg [1:0] state;

assign y = state[1] & state[0] & x;

always @ (negedge clk)

case (state)

2’b00: state <= x?2’b01:2’b00;

2’b01: state <= x?2’b10:2’b00;

2’b10: state <= x?2’b11:2’b00;

2’b11: state <= 2’b00;

endcase

endmodule