Building a GCD Datapath and FSM Controller on FPGA: A Step-by-Step RTL Design Lab

Introduction to GCD RTL Design on FPGA

In this lab, you will implement the RTL design of a Greatest Common Divisor (GCD) for two 4-bit numbers on an FPGA using Verilog. The GCD is a classic algorithm that finds the largest integer dividing both numbers. The design follows a structured approach: a datapath handles arithmetic operations and storage, while a finite state machine (FSM) controller orchestrates the sequence. This tutorial provides a step-by-step guide to building the datapath with structural Verilog and the controller with behavioral Verilog, following the FSM template from previous labs. By the end, you will understand how to connect these modules in a top-level entity and simulate the design.

Datapath Design: Structural Verilog

The datapath performs all computations and stores intermediate values. It consists of registers (clocked) and combinational components (subtractor, multiplexer, comparator, etc.). All non-register components must be purely combinational. The datapath receives control signals from the FSM (like load enables) and sends status signals back (e.g., X_neq_Y, X_lt_Y).

Key Datapath Components

• Registers (DFF with enable): Store the current values of X and Y. They are clocked and have an enable signal from the FSM to load new values. A reset signal initializes them.
• Subtractor: Computes X - Y or Y - X. Since we have 4-bit numbers, the subtractor can be implemented using a 4-bit adder with two's complement.
• Comparator (less-than): Outputs 1 if X < Y, 0 otherwise. This is used to decide which subtraction to perform.
• Comparator (not-equal): Outputs 1 if X != Y, 0 if equal. This is the condition to continue the loop.
• Multiplexer (MUX): Selects which value to load into a register (e.g., initial input or subtraction result).

Example: Register Module

module dff_en (input clk, rst, en, input [3:0] d, output reg [3:0] q);
    always @(posedge clk or posedge rst) begin
        if (rst) q <= 4'b0;
        else if (en) q <= d;
    end
endmodule

Example: Not-Equal Comparator

module neq (input [3:0] a, b, output neq_out);
    assign neq_out = (a != b) ? 1'b1 : 1'b0;
endmodule

Similarly, implement a less-than comparator (lt) and a subtractor (sub). Note that the subtractor can be built from an adder with inverted inputs and a carry-in of 1.

Control Path: Moore FSM in Behavioral Verilog

The FSM controller generates control signals based on the current state and the datapath status signals. It follows a Moore machine model where outputs depend only on the current state. The states correspond to steps in the Euclidean algorithm: IDLE, LOAD_X, LOAD_Y, COMPARE, SUBTRACT_X, SUBTRACT_Y, DONE. The FSM uses parameters for state encoding.

Example FSM Template

module fsm_gcd (input clk, rst, start, X_neq_Y, X_lt_Y, output reg load_X, load_Y, sel_sub, output reg done);
    parameter [2:0] IDLE = 3'd0, LOAD_X = 3'd1, LOAD_Y = 3'd2, COMPARE = 3'd3, SUB_X = 3'd4, SUB_Y = 3'd5, DONE = 3'd6;
    reg [2:0] state, next_state;
    always @(posedge clk or posedge rst) begin
        if (rst) state <= IDLE;
        else state <= next_state;
    end
    always @(*) begin
        next_state = state;
        case (state)
            IDLE: if (start) next_state = LOAD_X;
            LOAD_X: next_state = LOAD_Y;
            LOAD_Y: next_state = COMPARE;
            COMPARE: begin
                if (!X_neq_Y) next_state = DONE;
                else if (X_lt_Y) next_state = SUB_Y;
                else next_state = SUB_X;
            end
            SUB_X: next_state = COMPARE;
            SUB_Y: next_state = COMPARE;
            DONE: if (!start) next_state = IDLE;
        endcase
    end
    always @(*) begin
        {load_X, load_Y, sel_sub, done} = 4'b0;
        case (state)
            LOAD_X: load_X = 1;
            LOAD_Y: load_Y = 1;
            SUB_X: sel_sub = 1; // X = X - Y
            SUB_Y: sel_sub = 0; // Y = Y - X (or use another signal)
            DONE: done = 1;
        endcase
    end
endmodule

Note: The actual control signals depend on your datapath design. For example, you may need separate enables for X and Y registers, and a MUX select to choose between initial input and subtraction result.

Top-Level Module: GCD_top

The top-level module instantiates the datapath and control path, connecting their ports. It also includes the clock, reset, start, and output signals.

module GCD_top (input clk, rst, start, input [3:0] A, B, output [3:0] GCD, output done);
    wire load_X, load_Y, sel_sub, X_neq_Y, X_lt_Y;
    wire [3:0] X_out, Y_out;
    datapath dp (.clk(clk), .rst(rst), .load_X(load_X), .load_Y(load_Y), .sel_sub(sel_sub), .A(A), .B(B), .X_out(X_out), .Y_out(Y_out), .X_neq_Y(X_neq_Y), .X_lt_Y(X_lt_Y));
    fsm_gcd fsm (.clk(clk), .rst(rst), .start(start), .X_neq_Y(X_neq_Y), .X_lt_Y(X_lt_Y), .load_X(load_X), .load_Y(load_Y), .sel_sub(sel_sub), .done(done));
    assign GCD = (done) ? X_out : 4'b0; // output when done
endmodule

Simulation and Testing

Write a test bench to verify the design. Test with pairs like (8,12) -> GCD=4, (7,5) -> GCD=1, (15,5) -> GCD=5. Observe the waveforms to ensure the FSM transitions correctly and the datapath computes the GCD. Pay attention to the timing of load enables relative to the clock edge. A common trick is to use opposite clock edges for the FSM and datapath to avoid race conditions, but a single clock with proper enable timing works too.

Conclusion

This tutorial walked you through building a GCD design on FPGA using structural Verilog for the datapath and behavioral Verilog for the FSM controller. By following the modular approach, you can extend this design to larger bit widths or more complex algorithms. The key is to separate control and data paths, making the design easier to debug and reuse. Good luck with your lab submission!