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.
If you want a full-width, no-overflow-possible result, a simple approach would be:
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.