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.
There are several algorithms that can be used to implement division in fixed point arithmetic optimized for hardware implementation.

FPGA vendors provide optimized IP cores that you can use to divide two numbers. Altera provides the ”lpm_divide Megafunction”, while Xilinx provides the “LogiCORE IP DividerGenerator”.
These algorithms are demanding in terms of area and timing FPGA resources, depending on the number of bits involved in the division. Implementing a standard division usually creates long combinational paths that severely limit the maximum clock frequency of your design, while also consuming a huge amount of LUTs. If you need a very fast division algorithm (a few clock cycles per division result) the hardware implementation requires a lot of hardware resources.
Vice versa, there are serial algorithms that require moderate area resources but need many clock cycles.

The Multiplication Trick for Fixed-Point Arithmetic

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 this 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 a right shift of 15 positions. In this case, there is no need to perform division; we need to perform only a multiplication and a right shift by a constant number of bits.

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

In fact, if we use 6 bits (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 an (M+N)-bit number.

Hardware Tip: When choosing the quantization size (M), keep in mind the architecture of your target FPGA. Modern FPGAs have dedicated DSP slices (e.g., 18×18 or 25×18 multipliers). Choosing values for N and M that fit entirely inside a single DSP block will result in a highly optimized, single-cycle operation without consuming extra logic elements.

In the example, A has N bits and B has M bits. 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;

Improving Accuracy: Truncation vs. Rounding

When we want to divide by an integer, we can achieve a more accurate result by 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 closer 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 by.

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 positions, i.e., equivalent to integer division by 2^15.

In this case, 15 bits 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;

Conclusion

By converting a costly hardware division into a simple multiplication followed by a bit-shift, you can save massive amounts of logic resources and improve the overall timing of your FPGA design. Just remember to carefully evaluate the required accuracy to choose the optimal number of quantization bits.