non_restoring_divider.v

/**
 * Non-Restoring Divider
 * 
 * This module implements a non-restoring division algorithm for unsigned integer
 * division. The non-restoring algorithm is an efficient method that avoids the
 * restoration step required in restoring division, making it faster and more
 * hardware-friendly.
 * 
 * Key Features:
 * - Unsigned division: Divides two unsigned integers
 * - Non-restoring algorithm: More efficient than restoring division
 * - Iterative computation: Performs division in WIDTH iterations
 * - Error detection: Detects division by zero
 * - Pipelined-ready: Can be extended for pipelined operation
 * 
 * Non-Restoring Division Algorithm:
 * - Similar to long division, but doesn't restore on negative results
 * - Instead, continues with negative remainder and adjusts quotient
 * - Each iteration: shift remainder left, bring down next dividend bit
 * - If remainder >= divisor: subtract divisor, set quotient bit to 1
 * - If remainder < divisor: keep remainder, set quotient bit to 0
 * 
 * Algorithm Steps:
 * 1. Initialize: quotient = 0, remainder = 0
 * 2. For each bit of dividend (MSB to LSB):
 *    a. Shift remainder left, bring down next dividend bit
 *    b. If remainder >= divisor: remainder = remainder - divisor, quotient bit = 1
 *    c. Else: quotient bit = 0
 * 3. Final remainder and quotient are the results
 * 
 * Use Cases:
 * - Arithmetic units in processors
 * - Digital signal processing
 * - Fixed-point arithmetic
 * - Mathematical computations
 * 
 * @param WIDTH Width of dividend, divisor, quotient, and remainder (default: 8 bits)
 * 
 * @input clk Clock signal
 * @input rst_n Active-low reset signal
 * @input start Start division operation (pulse to begin)
 * @input dividend[WIDTH-1:0] Dividend (number to be divided)
 * @input divisor[WIDTH-1:0] Divisor (number to divide by)
 * @output quotient[WIDTH-1:0] Quotient result
 * @output remainder[WIDTH-1:0] Remainder result
 * @output valid Result valid flag (high when division complete)
 * @output busy Division in progress flag
 * @output error Error flag (high if divisor is zero)
 */
module non_restoring_divider #(
    parameter WIDTH = 8
)(
    input wire clk,
    input wire rst_n,
    input wire start,
    input wire [WIDTH-1:0] dividend,
    input wire [WIDTH-1:0] divisor,
    output reg [WIDTH-1:0] quotient,
    output reg [WIDTH-1:0] remainder,
    output reg valid,
    output reg busy,
    output reg error
);

    // State definitions
    localparam IDLE = 0;
    localparam DIVIDE = 1;
    localparam DONE = 2;
    
    // Define the counter width to accommodate any chosen WIDTH parameter
    localparam COUNTER_WIDTH = $clog2(WIDTH+1);
    
    // Internal registers
    reg [1:0] state;
    reg [WIDTH-1:0] div_reg; // Register to hold divisor
    reg [WIDTH-1:0] quot; // Register to build quotient
    reg [WIDTH-1:0] rem; // Register to hold remainder
    reg [COUNTER_WIDTH-1:0] iter; // Iteration counter sized according to WIDTH
    
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            state <= IDLE;
            busy <= 0;
            valid <= 0;
            error <= 0;
            quotient <= 0;
            remainder <= 0;
            div_reg <= 0;
            quot <= 0;
            rem <= 0;
            iter <= 0;
        end else begin
            case (state)
                IDLE: begin
                    valid <= 0;
                    error <= 0;
                    busy <= 0;
                    
                    if (start) begin
                        if (divisor == 0) begin
                            error <= 1;
                        end else begin
                            busy <= 1;
                            div_reg <= divisor;
                            
                            // Initialize registers for division
                            quot <= 0;
                            rem <= 0;
                            iter <= WIDTH[$clog2(WIDTH+1)-1:0];  // Verilog-2005 compatible: assign lower bits
                            
                            state <= DIVIDE;
                        end
                    end
                end
                
                DIVIDE: begin
                    // ============================================================
                    // Division Iteration
                    // ============================================================
                    if (iter > 0) begin
                        // ============================================================
                        // Shift and Bring Down Next Bit
                        // ============================================================
                        // Left shift remainder and bring down next dividend bit
                        // This is equivalent to: remainder = (remainder << 1) | dividend_bit
                        rem <= {rem[WIDTH-2:0], dividend[iter-1]};
                        
                        // ============================================================
                        // Compare and Update
                        // ============================================================
                        // Check if current remainder (with new bit) >= divisor
                        if ({rem[WIDTH-2:0], dividend[iter-1]} >= div_reg) begin
                            // ============================================================
                            // Subtract Divisor
                            // ============================================================
                            // Remainder is large enough: subtract divisor
                            rem <= {rem[WIDTH-2:0], dividend[iter-1]} - div_reg;
                            // Set quotient bit to 1
                            quot <= {quot[WIDTH-2:0], 1'b1};
                        end else begin
                            // ============================================================
                            // Keep Remainder
                            // ============================================================
                            // Remainder is too small: keep it as is
                            // Set quotient bit to 0
                            quot <= {quot[WIDTH-2:0], 1'b0};
                        end
                        
                        // ============================================================
                        // Decrement Iteration Counter
                        // ============================================================
                        iter <= iter - 1;
                    end else begin
                        // ============================================================
                        // Division Complete
                        // ============================================================
                        // All iterations complete: output results
                        quotient <= quot;
                        remainder <= rem;
                        valid <= 1;      // Assert valid flag
                        busy <= 0;      // Clear busy flag
                        state <= DONE;  // Transition to DONE state
                    end
                end
                
                DONE: begin
                    // Stay in done until next start
                    if (start) begin
                        valid <= 0;
                        state <= IDLE;
                    end
                end
                
                default: state <= IDLE;
            endcase
        end
    end
endmodule