VHDL coding tips and tricks: VHDL: Synthesisable code for Dividing two Unsigned numbers

Wednesday, March 17, 2010

VHDL: Synthesisable code for Dividing two Unsigned numbers

THIS CODE WAS UPDATED ON 19th MARCH 2024!

    Dividing an unsigned number by another in VHDL isnt that simple. The code will synthesis only if the divisor is a power of 2, otherwise it will only work in simulation and not in synthesis.

    That is why we need to implement a divider from scratch. There are several algorithms available for this purpose. I have chosen Restoring Division algorithm in this article.
    
    The divider is written in the format of a VHDL procedure. It takes two variables of unsigned type as inputs and two variables of unsigned type as outputs. 

procedure  divide(variable a,b : in unsigned; variable quotient, remainder : out unsigned) is

First input is the dividend and second one is the divisor, while first output is for the quotient and the second one is for the remainder. All these four inputs and outputs should be of the same size for the divider to work correctly.

If you want to know how this algorithm works in general, read this article: Restoring Division algorithm.

I have written the procedure for the divider and used it directly in a testbench code. Along with testing the divider, the testbench also shows how you can use this procedure in your own project. Let me share the code with you.

Unsigned Division in VHDL with testbench:


--library declarations
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use ieee.math_real.all;
 
--entity for testbenches are always empty
entity tb_divide is
end tb_divide;
 
architecture behavior of tb_divide is 
 
--procedure for dividing two unsigned numbers.
--'a' is the dividend, 'b' is the divisor, quotient and remainder are the results.
 procedure  divide(variable a,b : in unsigned; variable quotient, remainder : out unsigned) is
    --'a1' will contain the quotient, but is initialized with the dividend
    variable a1 : unsigned(a'length-1 downto 0) := a;  
    variable b1 : unsigned(b'length-1 downto 0) := b;  
    variable p1 : unsigned(b'length downto 0):= (others => '0');  --this will contain the remainder
    variable i : integer:=0;  --loop index for iterations.
    begin
        for i in 0 to b'length-1 loop  --iterate N times for a N bit number
            p1(b'length-1 downto 1) := p1(b'length-2 downto 0); --left shift remainder.
            p1(0) := a1(a'length-1); --msb of a1 is passed to lsb of remainder.
            a1(a'length-1 downto 1) := a1(a'length-2 downto 0); --left shift a.
            p1 := p1-b1; --subtract b from remainder.
            if(p1(b'length) ='1') then  --what is the msb of remainder.
                a1(0) :='0'; 
                p1 := p1+b1;  --if its 1, add back b to remainder
            else
                a1(0) :='1';  --if its 0, set lsb of a1 as high.
            end if;
        end loop;
        --assign the final results.
        quotient := a1;
        remainder := p1(a'length-1 downto 0);    --ignore the msb of p1.    
end procedure;  --END of procedure
    
constant N : integer := 8;  --size of the operands and results.
signal a8,b8,quotient,remainder : unsigned(N-1 downto 0);  

begin
 
-- Stimulus process
stim_proc: process
    variable seed1, seed2 : integer := 1;
    variable rand : real;
    variable int_rand : integer;
    variable a,b,q,r : unsigned(N-1 downto 0); 
begin
    for i in 0 to 20 loop
        --generate a random number for a.
        --Value of 'rand' is between 0 and 1. 
        --Multiply 'rand' by 2^N and then round down to get an integer.
        uniform(seed1, seed2, rand);  
        int_rand := integer(trunc(rand*real(2**N))); 
        a := to_unsigned(int_rand,N);
        --generate a random number for b.
        uniform(seed1, seed2, rand);  
        int_rand := integer(trunc(rand*real(2**N)));
        b := to_unsigned(int_rand,N);
        --call the 'divide' procedure. All inputs and outputs are variables here.
        divide(a,b,q,r);
        --check if the result is correct.
        --if the result is correct, a = b*quotient + remainder;
        assert a = b*q+r report "incorrect result";
        --assign the operands and results to signals so that we can see it in the simulation waveform.
        a8 <= a;
        b8 <= b;
        quotient <= q;
        remainder <= r;
        --wait a bit before trying a new set of inputs. 
        --Otherwise we wont be able to see the different iterations in the simulation waveform.
        wait for 10 ns;
    end loop; 
    wait;  --wait endlessly. We are done with testing!
end process;

end;


Note :- This divide procedure is synthesizable. Note that this code does NOT work for negative numbers, though it can be tweaked a bit to make it work for negative numbers.

Simulation Waveform:


simulation waveform for division of two unsigned number in vhdl


 

31 comments:

  1. is this function working for std_logic type???

    ReplyDelete
  2. is it possible to do division or modulus operation in xilinx ise without using any function or any user own logic codes???

    ReplyDelete
  3. @rourab : Why do you want to divide std_logic types. You can then use some other simple code to get the result.
    The division operator available in vhdl has some limitations.But in Xilinx, you can use the "divider generator" IP core for division if you want.

    ReplyDelete
  4. I have used divider operator('/') in ISE tool in vhdl code. the test bench is fine, but when im going to implement it on fpga board its giving error. it is saying the divider must be power of two . why ?

    ReplyDelete
  5. @rourab : it happens. Use this function for division.

    ReplyDelete
  6. thank you for reply.
    actually i want modulus(%) operation. I have already implemented your function on hardware(vertex 5), i just add a extra line
    "m1:=a-(a1*b);" where m1 hold the modulus value.
    but particularly this line (a subtraction and multiplication) take extra resources on FPGA board for large data width input. So i want to avoid this line. I am not going through in your algorithm. Using this algorithm is there any way where i can find modulus value directly

    ReplyDelete
  7. @rourab: there is a "mod" operator in vhdl for doing the modulo operation on integers. You can use that.

    ReplyDelete
  8. I have tried all the things, every thing is fine in testbench, but in case of implemantation purpose these operators like mod, divider are not working. you can try it .. could you modify your algorithm?

    ReplyDelete
  9. @rourab :I think it should be working. The above code does what it is supposed to do.

    For your purpose I suggest you the "mod" operator available in numeric_std library. All the source and destination operands should be unsigned.

    function "mod" (L, R: UNSIGNED) return UNSIGNED;

    Google for "mod" operator and you will find lot of examples.

    ReplyDelete
  10. library IEEE;
    use IEEE.STD_LOGIC_1164.ALL;
    use IEEE.STD_LOGIC_ARITH.ALL;
    use IEEE.STD_LOGIC_UNSIGNED.ALL;
    use ieee.numeric_std.all;

    ---- Uncomment the following library declaration if instantiating
    ---- any Xilinx primitives in this code.
    --library UNISIM;
    --use UNISIM.VComponents.all;
    entity motor is --constrained in ucf file
    Generic ( n : positive := 4);
    Port (
    clk : in std_logic; --spartan 3 e
    input_data : in std_logic_vector((n-1) downto 0);
    decrypted_data : inout std_logic_vector((n-1) downto 0)
    );
    end motor;

    architecture Behavioral of motor is

    signal base : unsigned ((n-1) downto 0):="1010";
    signal temp : unsigned ((n-1) downto 0);
    begin

    temp<= unsigned(input_data) mod base;
    decrypted_data<=std_logic_vector(temp);
    end Behavioral;

    I have tried this code
    the error is
    "mod can not have such operands in this context"

    ReplyDelete
  11. @rourab : Use only numeric_std. And dont use std_logic_vector.
    And write a simple code to test the use of mod. You are complicating it with so many type conversions.

    ReplyDelete
  12. Now i have used
    --------------------------------
    library IEEE;
    use IEEE.STD_LOGIC_1164.ALL;
    use ieee.numeric_std.all;
    --------------------------------
    --and ports are
    ---------------------------
    Port (
    --clk : in unsigned; --spartan 3 e
    input_data : in unsigned((n-1) downto 0);
    decrypted_data : inout unsigned((n-1) downto 0)
    );
    -----------------------------------
    --a signal
    ---------------------------------
    signal base : unsigned ((n-1) downto 0):="1010";
    ---------------------------------------------
    and i have written
    decrypted_data<= input_data mod base;
    ---------------------------------------
    testbench is fine but when im trying to implement it, its saying
    "Operator must have constant modulo operand."
    when i declare the base signal as constant
    its saying
    "The modulo should be a power of 2"
    what should i do??

    ReplyDelete
  13. @rourab : try "rem" instead of mod and see what happens.
    which version of ISE are you using?

    ReplyDelete
  14. Im using ise 11.1
    i have tried rem,
    its saying
    "Operator must have constant operands or first operand must be power of 2"

    ReplyDelete
  15. I think your tool doesnt support the mod operator fully.

    I am not sure about this, but can you use the above code by making the following change:
    return a1; REPLACE IT WITH return p1;

    If this also doesnt work then contact me through the "contact me" page.

    ReplyDelete
  16. this works fine vipin.
    Vipin now i have have problem.
    i want to use this function as a separate block.
    i habe written following code.
    entity motor is --constrained in ucf file
    Generic ( n : positive := 3);
    Port (
    clk : in std_logic; --spartan 3 e

    dividend : in std_logic_vector((n-1) downto 0);
    divisor : in std_logic_vector((n-1) downto 0);

    remainder : out std_logic_vector((n-1) downto 0)
    );
    end motor;

    architecture Behavioral of motor is

    signal a : unsigned((n-1) downto 0):= (others => '0');
    signal b : unsigned((n-1) downto 0):= (others => '0');

    --================================================================
    signal p1_out : unsigned(divisor'length downto 0):= (others => '0');
    signal a1 : unsigned(dividend'length-1 downto 0):=unsigned(dividend);
    signal b1 : unsigned(divisor'length-1 downto 0):=unsigned(divisor);
    signal p1 : unsigned(divisor'length downto 0):= (others => '0');
    begin

    main: process(clk )

    variable i : integer:=0;

    begin

    if(rising_edge(clk)) then

    for i in 0 to divisor'length-1 loop
    p1(divisor'length-1 downto 1) <= p1(divisor'length-2 downto 0);
    p1(0) <= a1(dividend'length-1);
    a1(dividend'length-1 downto 1) <= a1(dividend'length-2 downto 0);
    p1 <= p1-b1;
    if(p1(divisor'length-1) ='1') then
    a1(0) <='0';
    p1 <= p1+b1;
    else
    a1(0) <='1';
    end if;

    end loop;

    end if;
    p1_out<=p1;


    end process main;
    remainder<=std_logic_vector(p1_out((divisor'length-1) downto 0));


    end Behavioral;

    ===========================================
    i replace all of the variable by signal.
    but i didnt get the desired result
    p1, a1 and b1 did not get the any value. why this is happening??

    ReplyDelete
  17. Hi vipin,

    I tried this function in my Design. Unfortunately, it doesn't give the correct value..

    I have 2 questions..

    1. variable p1 : unsigned(b'length downto 0):= (others => '0');

    Is the length declaration correct here?

    2. if(p1(b'length-1) ='1') then
    What this means? The Restoring algorithm has no condition like this..

    Thank you

    ReplyDelete
  18. 1.The varibale size pi is absolutely fine.
    2. If the width of B input is 'n' then
    "if(p1(b'length-1) ='1')" it check the (n-1) for logic '1'

    ReplyDelete
  19. @rourab...

    Thanks for the reply. It works good now..

    But, the function c <= divide ( a , b ), works only when a and b are fixed values.

    I tried generating random no.s of a and b of same width, the function doesn't provide the correct output...

    ReplyDelete
  20. @swami:but i have implemented this code successfully with random no. in that case i would prefer to check ur code,
    @vipin: could u help me about my problem?

    ReplyDelete
  21. @rourab : are you having problems with changing variables to signals? this is because variables gets updated immediately and signals after a delta delay.
    to make it work with signals you can do one thing. Re-write the code in the form of a state machine.Each assignment or calculation happens in one clock cycle or in one state of the state machine.

    ReplyDelete
  22. @vipin
    Obviously I will implement the design using state machine. But here i have very basic qusetion about harware designig. I may be sounded like a fool. If i write this design using state machine it will take sevaral clocks,design will be slow. Here in a single clock the design will execute less no. of operations compare to "without state machine designing"(i,e in fuctions). In that case what will be changed in resouces utilization? could FPGA reuse the slices which were used in previous clock cycle?

    ReplyDelete
  23. @rourab : state machines will lead to less throughput and but less resources.

    ReplyDelete
  24. @all: help to me creat arithmetic paperlined block and this block use division 3 numbers 8 bit. Thank you very much.

    ReplyDelete
  25. @Vipin: How to get the reminder of the fractional value.

    ReplyDelete
  26. Thanks guys, you helped me so much, you have super blog :)

    ReplyDelete
  27. I tried ur code..but it was showing error,i could not arrange codes properly may be,can tell me the steps to arrange the codes?

    ReplyDelete
  28. guys does any one can post their suggeston
    ....where 256x256 array values need to implented over an fgpa

    ReplyDelete
    Replies
    1. You can store image values in Text file and then you can use it over FPGA.

      Delete
  29. Sir I have tried to implement your above given code, but it is not working.Will You please help me for the same.Thank you in advace.

    ReplyDelete
  30. I changed it a little bit for different sizes:

    --variable b1 : unsigned(a'length-1 downto 0):=b;
    variable b1_1 : unsigned(a'length-b'length-1 downto 0) := (others => '0');
    variable b1_2 : unsigned(b'length-1 downto 0) := b;
    variable b1 : unsigned(a'length-1 downto 0) := (b1_1 & b1_2);

    ReplyDelete