Restore the remainder divider

Restore the remainder divider

Restore the remainder divider

Algorithm Description

The recovery remainder divider is a commonly used divider. The process is very similar to the manual division method. The process is

  1. Shift the divisor to the left until it is greater than the dividend
  2. Perform the operation of subtracting the dividend from the dividend to obtain the remainder, and shift the quotient by 1 bit to the left, and add 1 to the space
  3. If the remainder is greater than 0, the divisor is shifted by 1 bit to the right. If the remainder is less than 0, the remainder is added to the current divisor, the last position of the quotient is 0, and the divisor is shifted by 1 bit to the right
  4. Repeat to 2 until the divisor is smaller than the original divisor

RTL code

The RTL code uses a large number of ifsentences to complete the above algorithm description, among which

  • In order to ensure that the shifted divisor is greater than the dividend, the divisor is directly placed in the first WIDTH bit of a bit-wide WIDTH*3 register
  • divisor_move >= '{divisor_lock}Used to stop when the shift divisor is less than the original divisor
  • (divisor_move > '{remainder_r}) && (dout == 'b0)Used to start saving the result when the first 1 appears
module restore_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
);

reg [2 * WIDTH:0]remainder_r;
reg [3 * WIDTH-1:0]divisor_move;
reg [WIDTH-1:0]divisor_lock;
always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
       //initialization
        {remainder_r,divisor_lock,divisor_move,dout} <='b0;
    end else begin
        if(din_valid == 1'b1) begin 
           //Latch the input, 3 times the width of WIDTH is used to ensure that the shifted divisor is greater than the dividend
            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 condition
             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//Perform subtraction
                remainder_r <= remainder_r-divisor_move;
                dout <= {dout[2 * WIDTH-2:0],1'b1};
               //divisor_move <= divisor_move >> 1;
                divisor_lock <= divisor_lock;
                if(remainder_r >= divisor_move) begin
                    divisor_move <= divisor_move >> 1;
                end else begin
                    divisor_move <= divisor_move;
                end
            end else begin//Restore the remainder
                remainder_r <= remainder_r + divisor_move;
                dout <= {dout[2 * WIDTH-1:1],1'b0};
                divisor_move <= divisor_move >> 1;
                divisor_lock <= divisor_lock;
            end
        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

The test platform reuses the platform of the shiftsub divider and adds the function of "stop on error"

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;

restore_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/1110716 Recovery remainder divider-Cloud + Community-Tencent Cloud