2

I've implemented a division algorithm on an FPGA using the long division algorithm. My implementation does not use pipelining, but works iteratively and requires very few logic elements since the algorithm mainly consists of a single subtraction and some shift registers.

For a signed version of the component I just use the absolute values of the inputs and negate the result as required. This works as expected, but negating two's complement numbers does require adding '1' after inverting all bits, which results in 3 full adders in the design. This results in roughly twice as many logic elements for a signed divider compared to an unsigned one.

Is there a way to adjust the long division algorithm, so it directly works with negative numbers? I've already figured out that I can include the '+1' for the denominator during the main subtraction by using a borrow bit. I haven't found out how to handle the numerator or how to directly produce a result with the correct sign.

sebi707
  • 201
  • 1
  • 1
  • [self promotion]I wrote a bit about non-restoring signed and unsigned division. It's fairly complex : http://temlib.org/site/?p=351 – TEMLIB Apr 09 '19 at 19:48
  • Add one more state to your controller and re-use the adder you already have in an extra cycle to do the extra increment? – The Photon Apr 09 '19 at 20:00
  • 2
    Can your substractor substract -1 to add +1? – bobflux May 08 '21 at 13:33
  • Without a block diagram or essential parts of the VHDL code it is hard to follow why you would need more than *one* adder/subtracter. An incrementer does not need a full adder. – greybeard Jan 20 '23 at 06:46

1 Answers1

0

I don't think you can get away without more logic gates. Consider 16-bit signed divider:

  • -16384 / -1 = 16384
  • -32768 / -1 = overflow

(-32768 is a valid two's complement 16-bit signed integer).

It's situations like this when microcode seems very alluring...

anrieff
  • 5,199
  • 1
  • 27
  • 46
  • I'm (currently) not concerned with the difference in bit width. When converting 16-bit signed values to unsigned I still use 16 bits. I'm more interested in avoiding these costly conversions/negations. – sebi707 Apr 09 '19 at 19:38
  • Yes, but you cannot represent your (signed) output. It does not matter what sort of trickery you use to avoid those costly conversions/negations, because the result doesn't fit in the output register, unless you make it one bit larger. – anrieff Apr 09 '19 at 20:35
  • Typically -32768 / -1 = -32768 (i.e. it's allowed to overflow even though it gives the wrong answer) – user253751 Apr 10 '19 at 04:15
  • That's not the case on the x86. – anrieff Apr 10 '19 at 06:53