Hardware Division

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 a_i 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 log₂(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 a_i is 1 and x = x-(y << i), otherwise a_i = 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 a_i = 0. For i=2, x > (y << i) and (y << i) is removed from x making x=16 and a_i = 1. In the same way, for i=1, x=6 and a_i = 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;
            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

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;
        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

SystemVerilog code for the divider testbench

Also available in GitHub.