From Problem Statement to Code

Finite State Machines (FSMs) are everywhere in digital design, from traffic lights to complex communication protocols. Translating a descriptive problem into a well-structured FSM feels tricky. How do you go from reading a set of conditions to drawing a state diagram and finally writing Verilog code?

In this blog, I’ll walk you through a step-by-step approach to solving an FSM problem — breaking down the signals, defining states, designing transitions, and implementing the logic in a clean and efficient way. If you’ve ever struggled with FSM design or just want to sharpen your problem-solving skills, this is for you! Let’s dive in.

Consider a finite state machine that is used to control some type of motor. The FSM has inputs x and y, which come from the motor, and produces outputs f and g, which control the motor. There is also a clock input called clk and a reset input called resetn. The FSM has to work as follows. As long as the reset input is asserted, the FSM stays in a beginning state, called state A. When the reset signal is de-asserted, then after the next clock edge the FSM has to set the output f to 1 for one clock cycle. Then, the FSM has to monitor the x input. When x has produced the values 1, 0, 1 in three successive clock cycles, then g should be set to 1 on the following clock cycle. While maintaining g = 1 the FSM has to monitor the y input. If y has the value 1 within at most two clock cycles, then the FSM should maintain g = 1 permanently (that is, until reset). But if y does not become 1 within two clock cycles, then the FSM should set g = 0 permanently (until reset).

Let’s take it step by step. First, we need to consider the global signals: a clock and an active-low reset (resetn). The system should start in state ‘A’ when resetn is asserted (low). Once resetn is released (high), the FSM should transition to the next state, which we'll call state ‘B’.

As mentioned in the problem, we need to set the output ‘f’ to 1, but only for a single clock cycle. To achieve this, we extend the FSM by adding another state. In the next positive clock edge, the system will transition to this new state where the output ‘f’ returns to 0, ensuring that ‘f’ is high for just one cycle.

After reaching state C, we need to start monitoring the input x for the sequence 101. When this sequence is detected, the FSM should transition to a new state where the output g = 1.

Initially, I considered using two flip-flops to continuously track the last two values of x and compare them upon reaching state C. However, since the problem specifies detecting 101 over successive clock cycles, this approach isn’t sufficient. Instead, we need to introduce three new states to properly implement a 101-sequence detector.

Additionally, I’ve updated the state naming convention to avoid conflicts between the FSM state names and the module’s input and output signals.

Now, it is mentioned that while keeping the value of ‘g’ high, we need to monitor ‘y’ for two consecutive clock cycles. This means we need to introduce an additional state — a sort of dummy state — to hold ‘g’ at 1 while also tracking the previous clock cycle’s value of ‘y’.

Get DhanwanthVarala’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Since the problem states that “if y has the value 1 within at most two clock cycles, then the FSM should maintain g = 1 permanently,” we need to modify our state machine accordingly.

To achieve this, we add a dummy state named ‘J’, which holds ‘g’ at 1 while checking ‘y’. Then, we introduce two more states: ‘K’ and ‘L’. State ‘K’ ensures ‘g’ remains permanently at 1 if the condition is met, while state ‘L’ ensures ‘g’ is permanently set to 0 otherwise.

With our state machine fully designed, it’s time to implement it in code. To keep things as simple as possible, I have structured the Moore machine using three always blocks:

1. A sequential always block to handle state transitions.
2. A combinational always block as a next-state decoder.
3. A third always block to assign outputs based on the state.

Some might argue that the output logic could be implemented using assign statements, but using a case statement made the implementation much clearer and easier to manage.

module top_module (
    input clk,
    input resetn,    // active-low synchronous reset
    input x,
    input y,
    output f,
    output g
); 
    parameter A=0,B=1,C=2,D=3,E=4,I=5,J=6,K=7,L=8;
    reg [3:0] s,ns;
    reg y1;
    
    always@(posedge clk)begin
        y1 <= y;
    end
    
    always@(posedge clk)begin
        if(!resetn) s <= A;
        else s <= ns;
    end
    
    always@(*)begin
        case(s)
            A: ns = (resetn) ? B : A;
            B: ns = C;
            C: ns = x ? D : C;
            D: ns = x ? D : E;
            E: ns = x ? I : C;
            I: ns = J;
            J: ns = ({y,y1}==2'b00) ? L : K;
            K: ns = (!resetn) ? A : K;
            L: ns = (!resetn) ? A : L;
        endcase
    end
    
    always@(posedge clk)begin
        case(ns)
            A: begin f=0;g=0; end
            B: begin f=1;g=0; end
            C: begin f=0;g=0; end
            D: begin f=0;g=0; end
            E: begin f=0;g=0; end
            I: begin f=0;g=1; end
            J: begin f=0;g=1; end
            K: begin f=0;g=1; end
            L: begin f=0;g=0; end
        endcase
    end

endmodule

In conclusion, I’ve shared my approach to designing and coding the FSM in a way that I find easy to understand. I’m still learning, so feel free to point out anything that can be improved or done differently. I’ll keep learning and come back with more interesting blogs in the future.

More to come. See you soon.
~Dhanwanth.