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.

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

We appreciate any of your comment, please post below:

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

Leave a Reply

Your email address will not be published.