0
$\begingroup$

I’m working on an FPGA design where I want to build a multiplier of some larger size using the provided $N \times N$ hardware multipliers. By using the long multiplication algorithm I’ve managed to get unsigned multiplications working, but I’m struggling with the extension to signed two's complement integers.

Basically the long multiplication for signed integers seems to work similar to unsigned ones. Partial products involving the MSB must calculated using signed multiplications but for the LSB unsigned multiplications can be used. Further when summing up the partial products they must be properly sign extended. This sign extension is the detail I’m struggling with, because it doesn’t map well to hardware and I want to avoid it. I’ve found this example for binary multiplication which seems to use some trick to skip this sign extension.

I believe there must be a way to translate this binary multiplication trick to long multiplication using $N$-bit blocks. When synthesizing a larger multiplication for an FPGA using the provided libraries, the generated hardware also seems to skip this sign extension and instead tweak some intermediate results.

$\endgroup$
  • $\begingroup$ Which input and output widths do you need to work with? Multiplying two $n$-bit inputs to give an $n$-bit result, and ignoring overflows, actually works the same for unsigned and two's complement. You only need special sign handling if you want to produce a product that's wider than the inputs. $\endgroup$ – Henning Makholm Sep 26 '18 at 18:53
  • $\begingroup$ When multiplying an $M$-bit and $N$-bit number I want the full $M+N$-bit result. $\endgroup$ – sebi707 Sep 26 '18 at 18:55
0
$\begingroup$

If you want a full-width, no-overflow-possible result, a simple approach would be:

  • Convert each of the inputs to sign-magnitude representation separately (by conditionally negating it),
  • Multiply the magnitudes together, now as unsigned numbers,
  • Negate the product if the input signs were different.

Alternatively, if we let $\hat a$ mean the two's complement number $a$ with its topmost bit flipped and the result interpreted as an unsigned number, we have $$ \hat a = a + 2^{n-1} \quad\iff\quad a = \hat a - 2^{n-1} $$ so $$ a\cdot b = (\hat a - 2^{n-1})\cdot(\hat b - 2^{m-1}) = \hat a \cdot \hat b - 2^{m-1} \hat a - 2^{n-1} \hat b + 2^{n+m-2} $$ where you can compute $\hat a \cdot \hat b$ using your unsigned multiplier and then subtract the other terms afterwards.

$\endgroup$
  • $\begingroup$ Not exactly what I'm looking for. Both your approaches are somewhat expensive because they operate on the full bit width of the inputs/outputs. $\endgroup$ – sebi707 Sep 26 '18 at 19:39
  • $\begingroup$ @sebi707: You'll be doing that many times already during the existing multiplication step. $\endgroup$ – Henning Makholm Sep 26 '18 at 19:42
  • $\begingroup$ During the multiplication I only do additions in the size of $2N$ (given an $N \times N$ hardware multiplier). E.g. a $4N \times 2N$ multiplication would be 8 of those additions. Converting to sign-magnitude would require 6 additional. $\endgroup$ – sebi707 Sep 26 '18 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.