Do not restore the remainder divider

Do not restore the remainder divider

Do not restore the remainder divider

Basic algorithm

The basic algorithm of the divider without restoring the remainder comes from the restoring divider. The difference is that when the remainder becomes negative, it does not stop to restore the remainder but continues to run the iteration, and adds the shifted divisor to the iteration instead of subtracting the shifted. Divisor, the basic algorithm is as follows

  1. Shift the divisor to the left to be exactly greater than the dividend
  2. If the remainder is positive: the remainder is subtracted from the shifted divisor; if the remainder is negative: the remainder is added to the shifted divisor;
  3. If the current remainder is positive, the result of this bit is 1, otherwise it is 0, and the divisor is shifted one bit to the right
  4. Repeat 2, 3, knowing that the divisor after shifting is smaller than the original divisor

RTL code

module norestore_divider #(
    parameter WIDTH = 4
)(
    input clk,//Clock
    input rst_n,//Asynchronous reset active low

    input [WIDTH * 2-1:0]dividend,
    input [WIDTH-1:0]divisor,

    input din_valid,

    output reg[2 * WIDTH-1:0]dout,
    output [WIDTH-1:0]remainder
);

//parameter JUDGE = 2 ** (2 * WIDTH);

reg [2 * WIDTH:0]remainder_r;
reg [3 * WIDTH-1:0]divisor_move;
reg [WIDTH-1:0]divisor_lock;
reg [2 * WIDTH:0]judge;
always @ (*) begin
    if(remainder_r[2 * WIDTH] == 1'b0) begin
        judge = remainder_r-divisor_move;
    end else begin
        judge = remainder_r + divisor_move;
    end
end

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        {remainder_r,divisor_lock,divisor_move,dout} <='b0;
    end else begin
        if(din_valid == 1'b1) begin//lock input data
            remainder_r[WIDTH * 2-1:0] <= dividend;
            remainder_r[2 * WIDTH] <='b0;
            divisor_move[3 * WIDTH-1:2 * WIDTH] <= divisor;
            divisor_move[2 * WIDTH-1:0] <='b0;
            divisor_lock <= divisor;
            dout <='b0;
        end else if((divisor_move>'{remainder_r}) && (dout =='b0)) begin
        //Start calculation conditions
            remainder_r <= remainder_r;
            dout <='b0;
            divisor_move <= divisor_move >> 1;
            divisor_lock <= divisor_lock;
        end else if(divisor_move >='{divisor_lock}) begin
            if(remainder_r[2 * WIDTH] == 1'b0) begin
                remainder_r <= judge;
                if(judge[2 * WIDTH] =='b0) begin
                    dout <= {dout[2 * WIDTH-2:0],1'b1};
                end else begin
                    dout <= {dout[2 * WIDTH-2:0],1'b0};
                end
            end else begin
                remainder_r <= judge;
                if(judge[2 * WIDTH] =='b0) begin
                    dout <= {dout[2 * WIDTH-2:0],1'b1};
                end else begin
                    dout <= {dout[2 * WIDTH-2:0],1'b0};
                end
            end
            divisor_move <= divisor_move >> 1;
            divisor_lock <= divisor_lock;
        end else if(remainder_r[2 * WIDTH-1] == 1'b1) begin
        //Adjust the remainder
            remainder_r <= remainder_r + divisor_lock;
            dout <= dout;
            divisor_lock <= divisor_lock;
            divisor_move <= divisor_move;
        end else begin
            remainder_r <= remainder_r;
            divisor_lock <= divisor_lock;
            divisor_move <= divisor_move;
            dout <= dout;
        end
    end
end

assign remainder = remainder_r[WIDTH-1:0];

endmodule

testing platform

module tb_divider (
);

parameter WIDTH = 4;

logic clk;//Clock
logic rst_n;//Asynchronous reset active low
logic [2 * WIDTH-1:0]dividend;
logic [WIDTH-1:0]divisor;

logic din_valid;

logic [2 * WIDTH-1:0]dout;
logic [WIDTH-1:0]remainder;

norestore_divider #(
    .WIDTH(WIDTH)
) dut (
    .clk(clk),//Clock
    .rst_n(rst_n),//Asynchronous reset active low

    .dividend(dividend),
    .divisor(divisor),

    .din_valid(din_valid),

    .dout(dout),
    .remainder(remainder)
);

initial begin
    clk ='b0;
    forever begin
        #50 clk = ~clk;
    end
end

initial begin
    rst_n = 1'b1;
    # 5 rst_n ='b0;
    #10 rst_n = 1'b1;
end

logic [2 * WIDTH-1:0]dout_exp;
logic [WIDTH-1:0]remainder_exp;
initial begin
    {dividend,divisor,din_valid} ='b0;
    forever begin
        @(negedge clk);
        dividend = (2 * WIDTH)'($urandom_range(0,2 ** (2 * WIDTH)));
        divisor = (WIDTH)'($urandom_range(1,2 ** WIDTH-1));
        din_valid = 1'b1;

        remainder_exp = dividend% divisor;
        dout_exp = (dividend-remainder_exp)/divisor;

        repeat(5 * WIDTH) begin
            @(negedge clk);
            din_valid ='b0;
        end
        if((remainder == remainder_exp) && (dout_exp == dout)) begin
            $display("successfully");
        end else begin
            $display("failed");
            $stop;
        end
    end
end

endmodule
Reference: https://cloud.tencent.com/developer/article/1110618 does not restore the remainder divider-Cloud + Community-Tencent Cloud