Verilog Coding Tips and Tricks: A Verilog Function for finding SQUARE ROOT

Thursday, November 2, 2017

A Verilog Function for finding SQUARE ROOT

In Verilog, there are no built-in operator to find the square root of a number. There are algorithms for doing this, but you have to write the code from scratch.

Here, I want to share a Verilog function for finding the square root of a binary number. The function is based on "Non-Restoring Square Root algorithm". You can learn more about the algorithm from this paper. The function takes a 32 bit input number and returns a 16 bit square root. The block diagram of the algorithm is given below:

     Here D is the input number. R is the remainder of the operation for non-perfect squares. Q contains the square root of 'D'.

The Verilog function along with the testbench code is given below:

module testbench;

reg [15:0] sqr;

//Verilog function to find square root of a 32 bit number.
//The output is 16 bit.
function [15:0] sqrt;
    input [31:0] num;  //declare input
    //intermediate signals.
    reg [31:0] a;
    reg [15:0] q;
    reg [17:0] left,right,r;    
    integer i;
    //initialize all the variables.
    a = num;
    q = 0;
    i = 0;
    left = 0;   //input to adder/sub
    right = 0;  //input to adder/sub
    r = 0;  //remainder
    //run the calculations for 16 iterations.
    for(i=0;i<16;i=i+1) begin 
        right = {q,r[17],1'b1};
        left = {r[15:0],a[31:30]};
        a = {a[29:0],2'b00};    //left shift by 2 bits.
        if (r[17] == 1) //add if r is negative
            r = left + right;
        else    //subtract if r is positive
            r = left - right;
        q = {q[14:0],!r[17]};       
    sqrt = q;   //final assignment of output.
endfunction //end of Function

//simulation-Apply inputs.
    initial begin
        sqr = sqrt(32'd4000000);    #100;
        sqr = sqrt(32'd96100);  #100;
        sqr = sqrt(32'd25); #100;
        sqr = sqrt(32'd100000000);  #100;
        sqr = sqrt(32'd33); #100;
        sqr = sqrt(32'd3300);   #100;
        sqr = sqrt(32'd330000); #100;
        sqr = sqrt(32'd3300000000); #100;

Simulation waveform:

The code was synthesised and simulated using Xilinx ISE 14.6.

From the waveform, you can see that, for perfect squares we get the exact square root as result. But for other inputs, there is an error of +/- 1. 

Another way to increase the precision is adding multiples of two zeros to the right of input.

Notice the last 4 inputs in the testbench.

Actual Square root of 33 = 5.7445, But we get 5.
Further for input, 3300 we get 57 as output. Adding 2 zeros we get one fractional digit in the output.
Further for input, 330000 we get 574 as output. Adding 4 zeros we get two fractional digits in the output.
Further for input, 3300000000 we get 57445 as output. Adding 8 zeros we get four fractional digits in the output.

No comments:

Post a Comment