What is an FSM?

Finite State Machine - a circuit that moves through defined states based on inputs.

Used for: controllers, protocols, sequencers, pattern detectors.

Moore vs Mealy

Moore Example

Mealy Example

FSM Design Steps

1. Understand the problem
2. Draw state diagram
3. Choose state encoding
4. Write state transition table
5. Implement in Verilog

Example: Sequence Detector (101)

Detect the pattern "101" in a serial input stream.

State Diagram

State Transition Table

Verilog Implementation

module seq_detector_101 (
    input      clk, rst_n,
    input      din,
    output reg detected
);
    // State encoding
    localparam IDLE = 2'b00;
    localparam S1   = 2'b01;
    localparam S2   = 2'b10;
    
    reg [1:0] state, next_state;
    
    // State register (sequential)
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            state <= IDLE;
        else
            state <= next_state;
    end
    
    // Next state logic (combinational)
    always @(*) begin
        next_state = state;  // Default: stay
        case (state)
            IDLE: next_state = din ? S1 : IDLE;
            S1:   next_state = din ? S1 : S2;
            S2:   next_state = din ? S1 : IDLE;
        endcase
    end
    
    // Output logic (Mealy - depends on state AND input)
    always @(*) begin
        detected = (state == S2) && din;
    end
endmodule

State Encoding

Binary Encoding

3 states need 2 bits:
IDLE = 2'b00
S1   = 2'b01
S2   = 2'b10

Pros: Minimum flip-flops
Cons: More combinational logic

One-Hot Encoding

3 states need 3 bits (one per state):
IDLE = 3'b001
S1   = 3'b010
S2   = 3'b100

Pros: Faster, simpler next-state logic
Cons: More flip-flops

Gray Encoding

Adjacent states differ by 1 bit:
IDLE = 2'b00
S1   = 2'b01
S2   = 2'b11
S3   = 2'b10

Pros: Reduces glitches
Cons: Limited to specific sequences

FSM Design Template

module fsm_template (
    input      clk, rst_n,
    input      [N-1:0] inputs,
    output reg [M-1:0] outputs
);
    // State declaration
    localparam STATE_A = 0;
    localparam STATE_B = 1;
    localparam STATE_C = 2;
    
    reg [1:0] state, next_state;
    
    // 1. State Register (sequential)
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n)
            state <= STATE_A;  // Reset state
        else
            state <= next_state;
    end
    
    // 2. Next State Logic (combinational)
    always @(*) begin
        next_state = state;  // Default
        case (state)
            STATE_A: begin
                if (condition1)
                    next_state = STATE_B;
            end
            STATE_B: begin
                if (condition2)
                    next_state = STATE_C;
                else
                    next_state = STATE_A;
            end
            STATE_C: begin
                next_state = STATE_A;
            end
            default: next_state = STATE_A;
        endcase
    end
    
    // 3. Output Logic
    // Moore style (based on state only):
    always @(*) begin
        case (state)
            STATE_A: outputs = ...;
            STATE_B: outputs = ...;
            STATE_C: outputs = ...;
            default: outputs = ...;
        endcase
    end
endmodule

Practical Example: Traffic Light Controller

module traffic_light (
    input      clk, rst_n,
    output reg [2:0] light  // {RED, YELLOW, GREEN}
);
    localparam RED    = 2'd0;
    localparam GREEN  = 2'd1;
    localparam YELLOW = 2'd2;
    
    reg [1:0] state;
    reg [3:0] timer;
    
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            state <= RED;
            timer <= 0;
        end else begin
            timer <= timer + 1;
            case (state)
                RED: begin
                    if (timer == 10) begin  // 10 clocks
                        state <= GREEN;
                        timer <= 0;
                    end
                end
                GREEN: begin
                    if (timer == 8) begin   // 8 clocks
                        state <= YELLOW;
                        timer <= 0;
                    end
                end
                YELLOW: begin
                    if (timer == 2) begin   // 2 clocks
                        state <= RED;
                        timer <= 0;
                    end
                end
            endcase
        end
    end
    
    // Output logic (Moore)
    always @(*) begin
        case (state)
            RED:    light = 3'b100;
            GREEN:  light = 3'b001;
            YELLOW: light = 3'b010;
            default: light = 3'b100;
        endcase
    end
endmodule