Division by Multiplication

Occasionally, a value will need to be divided by a non-power of two.  Using the division cores from coregen is an option.  Certainly it is a good option if area isn’t a concern but a quick design time is.  Another option is to use a multiplier.  This option uses less resources, and offers a lower latency.

As an example, consider the operation x/10.  This is the same as x * 0.1.  The issue is that 0.1 doesn’t have an exact representation in 2’s complement binary.  It must be truncated at some point, which means a small amount of error will occur.  For integer division, this error should be less than 1 LSB. A simple script can be written to determine the shortest value such that the error is less than 1 LSB.

max_val = 2**16
div = 10
N = int(math.ceil(math.log(div,2)))

done = 0
goal = math.floor(max_val / div)
while done == 0:
  conv = int((2**N / div) -1)    #ensures a low estimate
  tmp  = (conv * max_val) / 2**N
  if tmp == goal:
    done = 1
  else:
    N += 1

print hex(conv)

For this example, a 16b unsigned value can be multiplied by a value of 0x3332, which is a 14b unsigned value.  In this example, .  The output for various constant widths were:

• 6548 for a constant of 0x0665.  This is low by 5.
• 6550 for a constant of 0x0CCB.  This is low by 3.
• 6552 for a constant of 0x1998.  This is low by 1.
• 6553 for a constant of 0x3332.  This is correct.

The remainder can be found in one of two ways.  The first is to multiply the above result by 10, a number that does have a 2’s complement representation, and then subtract this from the initial argument.  This performs .  The operation is easy, as multiplication and addition are things FPGAs are good at.

The second method works by looking at the LSB’s of the multiplication.  If the length of the representation for 0.1 is sufficiently long, these LSB’s will fall into 10 non-overlapping ranges.  Further, the range will be based on the remainder.  This allows a handful of these LSBs to be used to map to the remainder.  This will avoid the need to use a DSP slice for the remainder determination.

This method will require a larger constant be used for the multiplication.  This is because sub-LSB precision is required.  In this example, an 18b unsigned value would be needed.  For an FPGA, there will typically be fixed-width multipliers.  Thus, for such cases, the wider multiplication might not be an issue.  This is often the case when a number needs to be divided by a small divisor.  For large divisors, the sub-LSB precision becomes and issue, and a second multiplier becomes a better choice.