How to Divide an Integer by Constant in VHDL

How to Divide an Integer by Constant in VHDL

The division algorithm is a demanding algorithm in terms of area resources inside a hardware device.

division

There are several algorithms that can be used to implement division in fixed point arithmetic optimized for hardware implementation.

The FPGA vendors provide optimized IP core that you can use to divide two number. 

Altera provides the”lpm_divide Megafunction”, Xilinx “LogiCORE IP DividerGenerator”.

These algorithms are demanding in terms of area/timing FPGA resources, depending on the number of bits involved in the division. If you need very fast division algorithm (few clock cycle per division result) the hardware implementation requires a lot of hardware resources.

Vice versa, there are serial algorithms that require moderate area resource but need many clock cycles.

Division in fixed point

The division should be avoided in hardware if not strictly necessary. There is a simple trick that can be used if you need to divide a number by a constant. The trick is to use a multiplication instead of a division.

Multiplication??  Yes, if you need to perform

A/B you have to simply implement A * (1/B).

Ok, I’m not joking. Let’s try to understand better with an example

435/17 = 25

we get the same result multiplying and dividing by, for example, 32.768 (2^15)

435 x (32.768/17) / 32.768 =

435 x (1.927) / 32.768 =

838.462 / 32.768 = 25

The division by 32.768 is simply implemented by right shift of 15 positions. In this case there is no need to perform division, we need to perform only a multiplication and right shift by a constant number of bits.

As you can guess, the accuracy of the result of the division depends directly from the number of bits we use to quantize the divider.

In fact, if we use 6 bit (2^6=64) the result will be:

435 x (64/17) / 64 =

435 x (3) / 64 = 20

Generally speaking, remember that if we multiply N-bit by M-bit numbers, the result will be (M+N) bit number.

In the example, A has N-Bit, B has M-Bit.

The result will be N+M, but we need to shift right by M-Bit in order to divide by 2^M. Using VHDL the implementation should be something like this:

constant const_val : unsigned(14 downto 0) := to_unsigned(1927,15);

signal val_in               : unsigned( 7 downto 0);
signal valIn_x_const_val    : unsigned(22 downto 0);
signal val_out              : unsigned( 7 downto 0);

begin
  valIn_x_const_val <= val_in * const_val;
-- right shift by 15
  val_out           <= valIn_x_const_val(22 downto 15);

end;

 

One more thing…

 

When we want to divide by integer, we can have a more accurate result implementing a rounding, i.e. adding 0,5 to the floating point result, before performing the truncation:

integer(435/17) = integer(25,588)

the result is nearest to 26 than 25, so performing:

integer(435/17 + 0,5) = integer(26,088) = 26

In VHDL (or fixed point representation) 0,5 is represented by 2^(M-1) if M is the number of bits representing the constant we want to divide to.

For the example if M=15:

435 * (32.768/17) / 32.768 =

435 * 1.927 / 32.768

using rounding:

integer((435 * 1.927) + 2^14) >> 15 =

integer(838.245 + 16.384) >> 15 =

854.629 >> 15 = 26

 

where “>> 15” means right shift by 15 position, i.e. equivalent to integer division by 2^15

 

In this case 15 bit of quantization plus rounding is a good approximation of the integer division. The VHDL code can be something like:

constant const_val       : unsigned(14 downto 0) := to_unsigned(1927,15);

signal val_in              : unsigned(7 downto 0);
signal valIn_x_const_val   : unsigned(22 downto 0);
signal val_out             : unsigned(7 downto 0);

begin

  -- ONLY TRUNCATION
  valIn_x_const_val <= val_in * const_val;
  val_out           <= valIn_x_const_val(22 downto 15);

  -- ROUNDING
  valIn_x_const_val <= val_in * const_val + (2**14);
  val_out           <= valIn_x_const_val(22 downto 15);

end;

 

 

If you appreciated this post, please help us to share it with your friend.

[social_sharing style=”horizontal” fb_like_url=”https://surf-vhdl.com/how-to-divide-an-integer-by-constant-in-vhdl” fb_color=”light” fb_lang=”en_US” fb_text=”like” fb_button_text=”Share” tw_lang=”en” tw_url=”https://surf-vhdl.com/how-to-divide-an-integer-by-constant-in-vhdl” tw_button_text=”Share” g_url=”https://surf-vhdl.com/how-to-divide-an-integer-by-constant-in-vhdl” g_lang=”en-US” g_button_text=”Share” linkedin_url=”https://surf-vhdl.com/how-to-divide-an-integer-by-constant-in-vhdl” linkedin_lang=”en_US” alignment=”center”]

If you need to contact us, please write to: surf.vhdl@gmail.com

We appreciate any of your comment, please post below:

12 thoughts to “How to Divide an Integer by Constant in VHDL”

  1. To avoid divider to calculate 435/17,
    I understand we are doing 435 * (32.768/17) / 32.768 = 435 * 1.927 / 32.768

    We still got to divide 32.768/17. How is this done without divider?
    I see I am missing some basic concept here.
    Please clarify.

    Thanks
    Ln

    1. 32.768 = 2^15
      this means that you are performing a quantization of 1/17 using 15 bits.
      the last division by 32.768 is performed by a right shift of 15 bit

    2. I had the same doubt in first instance, but if you look at the code, the division is not implement IN the code. Instead, it’s assigned to the constant “const_val” directly: to_unsigned(1927,15).
      Hope it clarifies a little bit.

  2. Thank you for this post. I was wondering how you picked the number 32.768 (2^15) to quantize the divider? Shall one test many nr until you reach a suitable one or there is a way to pick a specific number?

    1. because in this post I quantized the number using 15 bit.
      If you need to quantize at 8 bit you shall use 2^8=256

  3. Very good post and general content, thanks for sharing!

    One question, given the above code (truncate one) if we divide like in the example 435/17 we’ve got:

    constant const_val : unsigned(14 downto 0) := to_unsigned(17,15);

    signal val_in : unsigned( 11 downto 0);
    signal valIn_x_const_val : unsigned(36 downto 0);
    signal val_out : unsigned( 11 downto 0);
    begin
    valIn_x_const_val <= val_in * const_val;
    — right shift by 15
    val_out <= valIn_x_const_val(36 downto 21);
    end;

    If val_in will be 435 then the val_out result will be 0.

    What I'm doing wrong?

    1. if you quantize 17 with 15 bit the result is

      435*(32768/17)/32768=
      (435*1927)/32768 = 838245/32768 = 25 (this division is a simply 15 bit right shift)

      NOTE
      The right shift is valid ONLY if you are quantizing using a power of two

Leave a Reply

Your email address will not be published. Required fields are marked *