Given a dividend ‘a, and a divisor ‘b\', the restoring division algorithm calcul

Question

Given a dividend ‘a, and a divisor ‘b', the restoring division algorithm calculates the quotient ‘q, and the remainder ‘r' such that a = b x q + r and b, by subtracting b from the partial remainder (initially the MSB of a). If the result of the subtraction is not negative, we set the quotient bit to 1. Otherwise, b is added back to the result to restore the partial remainder. Then we shift the partial remainder with the remaining bits of ‘a' to the left by one bit for the calculation of the next quotient bit. This procedure is repeated until all the bits of 'a' are shifted out. Figure 1 shows the schematic diagram of a restoring divider. There are three registers: reg b, reg_r, and reg_ q, for storing the divisor b, a remainder r, and quotient q respectively. Initially, reg g stores the dividend a. A subtracter is used to subtract b from the partial remainder. The MSB of the output of the subtracter is used to determine whether the result of the subtraction is negative or not. The multiplexer over reg_q is used to load a initially and to shift the content of reg q (a and q) to the left later. The multiplexer over reg r implements the restoring. If the result of the subtraction is negative, the multiplexer selects the original partial remainder. Otherwise, it selects the result of the subtraction. At each iteration, one bit of q is obtained from the sign bit of the subtracter result and written to the LSB of the reg_q.

Explanation / Answer

module divider_circuit (
   input clk,
   input rst,
   input [31:0] a,
   input [15:0] b,
   output [15:0] r,
   output [31:0] q
);


reg [15:0] reg_b, reg_r;
reg [31:0] reg_q;
reg [5:0] count;
wire [16:0] sub_result;

always @ (posedge clk)
  begin
   if (rst)
   begin
   reg_b <= b;
reg_q <= a;
   reg_r <= 16'd0;
count <= 6'd32;
   end
   else if (count != 6'd0)
   begin
   count <= count - 1;
   reg_b <= b;
   reg_q <= {reg_q[30:0], ~sub_result[16]};
   reg_r <= sub_result[16] ? reg_r : sub_result;
   end
  
  end

assign sub_result = {reg_q[31],reg_r} - {1'b0,reg_b};
assign r = reg_r;
assign q = reg_q;


endmodule

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.