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:

Once ** x** and

**are known,**

*y***can be defined as:**

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

From equation (3) can be inferred that the quotient ** a** can be calculated guessing one bit at a time in

*log*iterations.

_{2}(x)The division algorithm can be explained as follows: if ** x-(y << i)>0** at the

*i-th*iteration then the

*i-th*bit of

**is 1 and**

*a*_{i}**, otherwise**

*x = x-(y << i)***.**

*a*_{i}= 0## 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 *a _{i} = 0*. For

*i=2*,

*x > (y << i)*and

*(y << i)*is removed from

*x*making

*x=16*and

*a*. In the same way, for

_{i}= 1*i=1*,

*x=6*and

*a*, and finally, when

_{i}= 1*i=0*,

**reached the value 7 and**

*a**x=1*, that is itself the remainder of the division.

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; iReady <= 0; oValid <= 0; end else begin case(state) INIT: begin i <= NBITS-1; iReady <= 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 if(oReady)begin oValid <= 0; state <= INIT; end else state <= SEND; end endcase end end endmodule

`include "divider.sv" parameter NBITS = 8; module top; logic clock, reset; logic [NBITS-1:0] A,B; logic [NBITS-1:0]quotient, remainder; logic iReady, iValid, oReady, oValid; 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; oReady <= 0; state <= S1; end else case(state) S1: begin A = 8'd123; B = 8'd11; iValid <= 1; oReady <= 1; if(iReady) state <= S2; end S2: begin if(oValid)begin $display(A,B,quotient, remainder); $finish(); end end endcase end endmodule

Also available in GitHub.