Hardware Division

A fairly simple Algorithm

Posted by Nelson Campos on July 04, 2016

Although it is a very basic operation, the hardware implementation of the division algorithm is a difficult task. Unlike what happens in software, where there is already a division operator, a hardware division module must be done with even more elementary calculations.

A division operation can be defined and rewritten as follows:

equation (1): x: dividend, y: divider, a: quotient, r: remainder

Once x and y are known, a can be defined as:

equation (2): a defined with N bits, where ai is the i-th bit of a

Putting equation (2) into (1) we get the following expressions:

equation (3)

From equation (3) can be inferred that the quotient a can be calculated guessing one bit at a time in log2(x) iterations.

The division algorithm can be explained as follows: if x-(y << i)>0 at the i-th iteration then the i-th bit of ai is 1 and x = x-(y << i), otherwise ai = 0.

Hardware Divison Algorithm

An illustrative example

As an example to illustrate how the division algorithm works, let's make x=36 and y=5, as can be seen in Table 1. Note that for i equals to 7, 6, 5, 4 and 3, x < (y << i) and ai = 0. For i=2, x > (y << i) and (y << i) is removed from x making x=16 and ai = 1. In the same way, for i=1, x=6 and ai = 1, and finally, when i=0, a reached the value 7 and x=1, that is itself the remainder of the division.

table 1: x=36 and y=5

You want to test the algorithm? Check out the SystemVerilog implementation of divider module and its testbench:

```module divider #(parameter NBITS = 8)
(input logic [NBITS-1:0] A,B,
input logic clock, reset, oReady, iValid,
output logic iReady, oValid,
output logic [NBITS-1:0]quotient, remainder);

enum logic [1:0] {INIT, CALC, SEND} state;
logic [(NBITS<<1)-1:0] A_aux, B_aux;
logic [3:0]i;

always_ff @(posedge clock)begin
if(reset)begin
i <= 0;
A_aux <= '0;
B_aux <= '0;
quotient <= '0;
state <= INIT;
oValid <= 0;
end

else begin
case(state)
INIT: begin
i <= NBITS-1;
oValid <= 0;
A_aux <= A;
B_aux <= B;
state <= CALC;
end

CALC: begin
if(i < NBITS)begin
if(A_aux >= (B_aux<<i))begin
A_aux <= A_aux-(B_aux<<i);
quotient[i] <= 1;
end
else quotient[i] <= 0;

\$display(i, quotient, A_aux);
i <= i-1;
end

else begin
remainder <= A_aux;
state <= SEND;
oValid <= 1;
end
end

SEND: begin
oValid <= 0;
state <= INIT;
end
else state <= SEND;
end
endcase
end
end

endmodule
```
SystemVerilog code for division Algorithm
````include "divider.sv"

parameter NBITS = 8;

module top;

logic clock, reset;
logic [NBITS-1:0] A,B;
logic [NBITS-1:0]quotient, remainder;

enum logic {S1, S2} state;

initial begin
clock = 0;
reset = 1;
#20 reset = 0;
end

always #5 clock = !clock;

divider #(NBITS) div(.*);

always_ff @(posedge clock)begin
if(reset)begin
iValid <= 0;
state <= S1;
end
else case(state)
S1: begin
A = 8'd123;
B = 8'd11;
iValid <= 1;
state <= S2;
end

S2: begin
if(oValid)begin
\$display(A,B,quotient, remainder);
\$finish();
end
end
endcase
end

endmodule
```
SystemVerilog code for the divider testbench

Also available in GitHub.