Restoring Division Verilog Code

 Restoring Division Algorithm is one of the division algorithms used for performing division in digital systems. Let us see how to write the Verilog code for Restoring Division method in FSM format.

Algorithm:

Registers used: A, M, Q, n (counter)

Step 1: Load the initial values for the registers. 

A = 0 (Accumulator), Qres = 0, M = Divisor, Q = Dividend and n is the count value which equals the number of bits of dividend.

Step 2: Shift left {A,Q}. 

Step 3: Perform A = A - M.

Step 4: Check the sign bit of A. If 0, goto step 5. If 1, goto step 6.

Step 5: Set LSB of Q as 0. Goto step 7.     

Step 6: Set LSB of Q as 1. Restore the value of A which was present before the subtraction.

Step 7: Decrement count. 

Step 8: Check if counter value n is zero. If yes, goto next step. Else, goto step 3.

Step 9: Stop

Flowchart:

Example Operation:

Consider the following: Dividend = 15 (place in Q) and Divisor = 8 (place in M)

Count n = 4

Verilog Code Logic:

Here, we are going to implement the Restoring Division algorithm for 4-bit operands in an FSM format with completely synthesizable Verilog Code.

Inputs:

clk, rst, X, Y (2 operands to be multiplied), start (This pulse indicates start of computation)

Outputs:

quot (Quotient), rem (Remainder) and valid (This pulse indicates the availability of final answer)

1. In IDLE state, we wait for the start pulse. Upon its arrival, move to START state.
2. In START state, we follow the same algorithm and perform the computations using verilog logic as long as counter < 3. (Incrementing counter is used)
3. Upon counter completion, we send out valid pulse and goto IDLE state. 

Verilog Code:

module Rest_div(clk,rst,start,X,Y,valid,quot,rem);

input clk;
input rst;
input start;
input [3:0]X,Y;
output [3:0]quot,rem;
output valid;

reg [7:0] Z,next_Z,Z_temp,Z_temp1;
reg next_state, pres_state;
reg [1:0] count,next_count;
reg valid, next_valid;

parameter IDLE = 1'b0;
parameter START = 1'b1;

assign rem = Z[7:4];
assign quot = Z[3:0];

always @ (posedge clk or negedge rst)
begin
if(!rst)
begin
  Z          <= 8'd0;
  valid      <= 1'b0;
  pres_state <= 1'b0;
  count      <= 2'd0;
end
else
begin
  Z          <= next_Z;
  valid      <= next_valid;
  pres_state <= next_state;
  count      <= next_count;
end
end

always @ (*)
begin 
case(pres_state)
IDLE:
begin
next_count = 2'b0;
next_valid = 1'b0;
if(start)
begin
    next_state = START;
    next_Z     = {4'd0,X};
end
else
begin
    next_state = pres_state;
    next_Z     = 8'd0;
end
end

START:
begin
next_count = count + 1'b1;
Z_temp     = Z << 1;
Z_temp1    = {Z_temp[7:4]-Y,Z_temp[3:0]};
next_Z     = Z_temp1[7] ? {Z_temp[7:4],Z_temp[3:1],1'b0} : 
                          {Z_temp1[7:4],Z_temp[3:1],1'b1};
next_valid = (&count) ? 1'b1 : 1'b0; 
next_state = (&count) ? IDLE : pres_state;	
end
endcase
end
endmodule

Testbench:

module Rest_div_tb;

reg clk,rst,start;
reg [3:0]X,Y;
wire [3:0]quot,rem;
wire valid;

always #5 clk = ~clk;

Rest_div inst (clk,rst,start,X,Y,valid,quot,rem);

initial
$monitor($time,"X=%d, Y=%d, valid=%d, quot=%d, rem=%d ",X,Y,valid,quot,rem);

initial
begin
X=15;Y=8;clk=1'b1;rst=1'b0;start=1'b0;
#10 rst = 1'b1;
#10 start = 1'b1;
#10 start = 1'b0;
@valid
#10 X=10;Y=2;start = 1'b1;
#10 start = 1'b0;
end      
endmodule

Simulation Result:

Conclusions:

The Restoring Division Algorithm implemented in this format can be implemented on FPGA devices.

Number of clock cycles taken to produce the output depends on the counter value. 

The number of bits of the incoming operands and outputs can also be increased to perform division with larger numbers.