COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Signed multiplication 135458

• Email
• Follow

```hi

Can anyone tell me how can i multiply two signed numbers in FPGA.
How the logic is really implemented..
ie., if i multiply two signed numbers are they multiplying the
positive number and the 2's complement (if the number is negative)
directly ..?
Or are they really changing the negative number to positive and do
normal multiplication and appends the sign accordingly..?
And is the positive number, and its 2's complement form same always...?
```
 0
Reply krsheshu (12) 9/8/2008 6:11:21 AM

See related articles to this posting

```On 8 Sep, 07:11, knight <krshe...@gmail.com> wrote:
> hi
>
> Can anyone tell me how can i multiply two signed numbers in FPGA.
> How the logic is really implemented..
> ie., if i multiply two signed numbers are they multiplying the
> positive number and the 2's complement (if the number is negative)
> directly ..?
> Or are they really changing the negative number to positive and do
> normal multiplication and appends the sign accordingly..?
> And is the positive number, and its 2's complement form same always...?

Multiplication, at it's heart, is nothing more than a sum of all of
the powers in any given number. The same holds for digital
multiplication. Lets first look at unsigned multiplication:

13 * 7 (1101 x 0111)

All that happens is you add up all of the individual powers of two
multiplication, which in binary is a simple bit shift to the left.

0 1 1 1 0 0 0   (8x = 2^3)  1
0 1 1 1 0 0   (4x = 2^2)  1
0 0 0 0 0   (2x = 2^1)  0
+       0 1 1 1   (1x = 2^0)  1
----------------
0 1 0 1 1 0 1 1  = 91

When multiplying two binary numbers, the number of bits required to
represent the result is always length(a) + length(b).
The rules above still carry through when using two's compliment. Lets
have a look at the same two binary numbers in twos compliment.

7 x -3 (0111 x 1101)
In twos compliment though, you have to remember to extend the sign bit
forward.

0 0 0 0 0 0 0 0    (8x) 0
1 1 1 1 0 1 0 0    (4x) 1
1 1 1 1 1 0 1 0    (2x) 1
+  1 1 1 1 1 1 0 1    (1x) 1
------------------
1  1 1 1 0 1 0 1 1   = -21.
|
|
-------- We only have an 8 bit result, so bits above bit 7 are
removed.

Fixed point multiplication works in exactly the same way, except that
an m.n x a.b number has a result of length (m + a).(n + b) (the total
number of bits is still the sum of the totals). This means some
additions require a bit shift to the right rather than left (ie. 2^-n)

FPGA's though, often have integrated multipliers and you dont have to
worry about resourcing a large number of adders. The easiest form of
multiplaction in VHDL is:

library ieee.
use ieee.numeric_std.all

.....
.....
.....

signal A, B : unsigned(7 downto 0); --or signed if you wish
signal R    : unsigned(15 downto 0); --or signed if you wish, if A
and B are signed
begin

process(clk)
begin
if rising_edge(clk) then
R  <= A * B;
end if;
end process;

....
....

Any good synthesiser should assign this to an onboard multiplier (if
it fits - its common for internal multipliers to be 9/18/36 bits or
less). Otherwise it should have knowledge of a multiplier it can build
out of logic.

Also remember though, that multiplying by 2^n is simply a bit shift,
so you dont need to use any logic for that. You simply append 0's or
remove bits.
```
 0

```>On Sep 8, 2:12 pm, Tricky <Trickyh...@gmail.com> wrote:

Hi
thanks for the insight
it was very useful
But i still have some doubts

> 7 x -3 (0111 x 1101)
> In twos compliment though, you have to remember to extend the sign bit
> forward.
>
>    0 0 0 0 0 0 0 0    (8x) 0
>    1 1 1 1 0 1 0 0    (4x) 1
>    1 1 1 1 1 0 1 0    (2x) 1
> +  1 1 1 1 1 1 0 1    (1x) 1
> ------------------
> 1  1 1 1 0 1 0 1 1   = -21.
> |
> |
> -------- We only have an 8 bit result, so bits above bit 7 are
> removed.

In this case why did you append 4 bits to the left..?
Why cant it be 1 or 2..?

Suppose i am  multiplying -3 and 3 (appending only 1 bit)
that means 00011 * 11101
So the result is 0001010111.
In this case how can we determine which all bits we need to skip..?
And i think if we change the number of bits appended, the result is
likely to be changed.. and the 2's complement doesn't yield the
expected result.
Does that mean there is no direct way to realize signed multiplication
in hardware..?,
rather we should changed signed to unsigned and multiply and put back
the sign for the result..?

> Any good synthesiser should assign this to an onboard multiplier (if
> it fits - its common for internal multipliers to be 9/18/36 bits or
> less). Otherwise it should have knowledge of a multiplier it can build
> out of logic.

For me only 16 bits are required for signed representation..
But why these multipliers start of multiples of 9..?

```
 0

```On Mon, 8 Sep 2008 04:10:55 -0700 (PDT), knight <krsheshu@gmail.com>
wrote:

>>On Sep 8, 2:12 pm, Tricky <Trickyh...@gmail.com> wrote:
>
>Hi
>thanks for the insight
>it was very useful
>But i still have some doubts
>
>
>
>> 7 x -3 (0111 x 1101)
>> In twos compliment though, you have to remember to extend the sign bit
>> forward.
>>
>>    0 0 0 0 0 0 0 0    (8x) 0
>>    1 1 1 1 0 1 0 0    (4x) 1
>>    1 1 1 1 1 0 1 0    (2x) 1
>> +  1 1 1 1 1 1 0 1    (1x) 1
>> ------------------
>> 1  1 1 1 0 1 0 1 1   = -21.
>> |
>> |
>> -------- We only have an 8 bit result, so bits above bit 7 are
>> removed.
>
>
>
>In this case why did you append 4 bits to the left..?
>Why cant it be 1 or 2..?
>
>Suppose i am  multiplying -3 and 3 (appending only 1 bit)
>that means 00011 * 11101
>So the result is 0001010111.
>In this case how can we determine which all bits we need to skip..?
>And i think if we change the number of bits appended, the result is
>likely to be changed.. and the 2's complement doesn't yield the
>expected result.
>Does that mean there is no direct way to realize signed multiplication
>in hardware..?,

You need to sign extend to the size of the result for two's complement
multiplication work as expected for signed numbers. After the
multiplication you need to use the lower 2N bits for the result. So
011x101 (3x-3) should be treated as 000011x111101 which gives the
result 110111 6 bit result which is the expected outcome ie -9 in 6
bits.
```
 0

```On Sep 8, 12:58=A0pm, Muzaffer Kal <k...@dspia.com> wrote:
> On Mon, 8 Sep 2008 04:10:55 -0700 (PDT), knight <krshe...@gmail.com>
> wrote:
>
>
>
> >>On Sep 8, 2:12 pm, Tricky <Trickyh...@gmail.com> wrote:
>
> >Hi
> >thanks for the insight
> >it was very useful
> >But i still have some doubts
>
> >> 7 x -3 (0111 x 1101)
> >> In twos compliment though, you have to remember to extend the sign bit
> >> forward.
>
> >> =A0 =A00 0 0 0 0 0 0 0 =A0 =A0(8x) 0
> >> =A0 =A01 1 1 1 0 1 0 0 =A0 =A0(4x) 1
> >> =A0 =A01 1 1 1 1 0 1 0 =A0 =A0(2x) 1
> >> + =A01 1 1 1 1 1 0 1 =A0 =A0(1x) 1
> >> ------------------
> >> 1 =A01 1 1 0 1 0 1 1 =A0 =3D -21.
> >> |
> >> |
> >> -------- We only have an 8 bit result, so bits above bit 7 are
> >> removed.
>
> >In this case why did you append 4 bits to the left..?
> >Why cant it be 1 or 2..?
>
> >Suppose i am =A0multiplying -3 and 3 (appending only 1 bit)
> >that means 00011 * 11101
> >So the result is 0001010111.
> >In this case how can we determine which all bits we need to skip..?
> >And i think if we change the number of bits appended, the result is
> >likely to be changed.. and the 2's complement doesn't yield the
> >expected result.
> >Does that mean there is no direct way to realize signed multiplication
> >in hardware..?,
>
> You need to sign extend to the size of the result for two's complement
> multiplication work as expected for signed numbers. After the
> multiplication you need to use the lower 2N bits for the result. So
> 011x101 (3x-3) should be treated as 000011x111101 which gives the
> result 110111 6 bit result which is the expected outcome ie -9 in 6
> bits.

If you are using signed numbers, you only need 2n-1 bits to hold the
result.

Rick
```
 0

```On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <gnuarm@gmail.com>
wrote:

>On Sep 8, 12:58�pm, Muzaffer Kal <k...@dspia.com> wrote:
>> On Mon, 8 Sep 2008 04:10:55 -0700 (PDT), knight <krshe...@gmail.com>
>> wrote:
>>
>>
>>
>> >>On Sep 8, 2:12 pm, Tricky <Trickyh...@gmail.com> wrote:
>>
>> >Hi
>> >thanks for the insight
>> >it was very useful
>> >But i still have some doubts
>>
>> >> 7 x -3 (0111 x 1101)
>> >> In twos compliment though, you have to remember to extend the sign bit
>> >> forward.
>>
>> >> � �0 0 0 0 0 0 0 0 � �(8x) 0
>> >> � �1 1 1 1 0 1 0 0 � �(4x) 1
>> >> � �1 1 1 1 1 0 1 0 � �(2x) 1
>> >> + �1 1 1 1 1 1 0 1 � �(1x) 1
>> >> ------------------
>> >> 1 �1 1 1 0 1 0 1 1 � = -21.
>> >> |
>> >> |
>> >> -------- We only have an 8 bit result, so bits above bit 7 are
>> >> removed.
>>
>> >In this case why did you append 4 bits to the left..?

>> You need to sign extend to the size of the result for two's complement
>> multiplication work as expected for signed numbers. After the
>> multiplication you need to use the lower 2N bits for the result. So
>> 011x101 (3x-3) should be treated as 000011x111101 which gives the
>> result 110111 6 bit result which is the expected outcome ie -9 in 6
>> bits.
>
>If you are using signed numbers, you only need 2n-1 bits to hold the
>result.

Except when both inputs are -2^(n-1).

In some applications you can guarantee this will never occur. In others
you _may_ need that extra bit, or an alternative overflow detection
scheme.

- Brian

```
 0

```On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <gnuarm@gmail.com>
wrote:

>On Sep 8, 12:58�pm, Muzaffer Kal <k...@dspia.com> wrote:
>> You need to sign extend to the size of the result for two's complement
>> multiplication work as expected for signed numbers. After the
>> multiplication you need to use the lower 2N bits for the result. So
>> 011x101 (3x-3) should be treated as 000011x111101 which gives the
>> result 110111 6 bit result which is the expected outcome ie -9 in 6
>> bits.
>
>If you are using signed numbers, you only need 2n-1 bits to hold the
>result.
>
>Rick

Have you considered the most negative number multiplied by itself?
Unless you saturate to most positive number that result doesn't fit to
2n-1 bits.
```
 0

```>
> For me only 16 bits are required for signed representation..
> But why these multipliers start of multiples of 9..?
>

Im not 100% sure exactly why they chose 9/18/36, but I think it has
something to do with the fact that many of them allow you to
accumulate before multiplying (8bits + 8bits = 9 bit result).

Dont worry about having exact multiples of 9. If you dont append 0s
(for unsigned multiplication) or the sign bit (for signed
multiplication) the synthesiser will.
```
 0

```On Sep 9, 3:33=A0am, Muzaffer Kal <k...@dspia.com> wrote:
> On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <gnu...@gmail.com>
> wrote:
>
> >On Sep 8, 12:58=A0pm, Muzaffer Kal <k...@dspia.com> wrote:
> >> You need to sign extend to the size of the result for two's complement
> >> multiplication work as expected for signed numbers. After the
> >> multiplication you need to use the lower 2N bits for the result. So
> >> 011x101 (3x-3) should be treated as 000011x111101 which gives the
> >> result 110111 6 bit result which is the expected outcome ie -9 in 6
> >> bits.
>
> >If you are using signed numbers, you only need 2n-1 bits to hold the
> >result.
>
> >Rick
>
> Have you considered the most negative number multiplied by itself?
> Unless you saturate to most positive number that result doesn't fit to
> 2n-1 bits.

I think you are confused.  Try the math.  It fits...

-8 x -8 =3D -64  =3D=3D=3D  1000 x 1000 =3D 1000000

or even simpler

-2 x -2 =3D -4 =3D=3D=3D 10 x 10 =3D 100

The reason this fits is because in an n bit signed number there are
n-1 significant bit plus a sign bit.  Multiplied, this gives 2(n-1)
significant bits plus a sign bit or 2n-1 rather than 2n bit to hold
the full word.

Rick
```
 0

```On Sep 9, 4:21=A0am, Tricky <Trickyh...@gmail.com> wrote:
> > For me only 16 bits are required for signed representation..
> > But why these multipliers start of multiples of 9..?
>
> > Thanks for the reply
>
> Im not 100% sure exactly why they chose 9/18/36, but I think it has
> something to do with the fact that many of them allow you to
> accumulate before multiplying (8bits + 8bits =3D 9 bit result).
>
> Dont worry about having exact multiples of 9. If you dont append 0s
> (for unsigned multiplication) or the sign bit (for signed
> multiplication) the synthesiser will.

The fact that Xilinx matches multipliers to block RAMs (which come in
multiples of 9 bits) would make you think it has more to do with some
chip level efficiency improvements.  It may just be that they are
sharing the I/O routing, or it may be that they are sharing some of
the logic.  Can you use both the block rams and the multipliers?
Maybe it just ends up being a packing convenience based on the
symmetry of the routing for both.

Rick
```
 0

```On Tue, 9 Sep 2008 07:47:08 -0700 (PDT), rickman wrote:

>I think you are confused.  Try the math.  It fits...
>
>-8 x -8 = -64  ===  1000 x 1000 = 1000000

Urrrrm, when I was at school -8 * -8 = +64
which definitely needs 8 bits to represent
in 2s complement without overflow.

>The reason this fits is because in an n bit signed number there are
>n-1 significant bit plus a sign bit.  Multiplied, this gives 2(n-1)
>significant bits plus a sign bit or 2n-1 rather than 2n bit to hold
>the full word.

--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
```
 0

```On Tue, 9 Sep 2008 07:47:08 -0700 (PDT), rickman <gnuarm@gmail.com>
wrote:

>On Sep 9, 3:33�am, Muzaffer Kal <k...@dspia.com> wrote:
>> On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <gnu...@gmail.com>
>> wrote:
>>
>> >On Sep 8, 12:58�pm, Muzaffer Kal <k...@dspia.com> wrote:
>> >> You need to sign extend to the size of the result for two's complement
>> >> multiplication work as expected for signed numbers. After the
>> >> multiplication you need to use the lower 2N bits for the result. So
>> >> 011x101 (3x-3) should be treated as 000011x111101 which gives the
>> >> result 110111 6 bit result which is the expected outcome ie -9 in 6
>> >> bits.
>>
>> >If you are using signed numbers, you only need 2n-1 bits to hold the
>> >result.
>>
>> >Rick
>>
>> Have you considered the most negative number multiplied by itself?
>> Unless you saturate to most positive number that result doesn't fit to
>> 2n-1 bits.
>
>I think you are confused.  Try the math.  It fits...
>
>-8 x -8 = -64  ===  1000 x 1000 = 1000000
>
>or even simpler
>
>-2 x -2 = -4 === 10 x 10 = 100

I know you're confused. When you square -8 you get +64 and when you
multiply -2 by itself you get +4. Continuing with the simpler case if
you have two bit two's complement numbers and you multiply the most
negative number (ie -2) by itself the result has to be a positive
number and one should be able to represent and interpret it thus. So
-2 x -2 == 10 x 10 = +4 == 0100. If you drop the leading zero and
claim that the result fits into 3 bits as opposed to 4 needed then you
should interpret it as a 3 bit two's complement number which makes 100
a negative number ie -4 which is the wrong result.

The confusing issue is that two's complement numbers don't have a
symmetrical distribution in the number line. The most negative two's
complement number of any size doesn't have an equivalent in the
positive domain so one can not describe it in the same size. And when
one squares the most negative number the result doesn't fit into 2n-1
but fits into 2n nicely.
```
 0

```On Sep 9, 10:47=A0am, rickman <gnu...@gmail.com> wrote:
>
> I think you are confused. =A0Try the math. =A0It fits...
>
> -8 x -8 =3D -64 =A0=3D=3D=3D =A01000 x 1000 =3D 1000000
>
> or even simpler
>
> -2 x -2 =3D -4 =3D=3D=3D 10 x 10 =3D 100
>

I guess I'll have to get a new calculator.  It tells me...
-8 x -8 =3D 64 (not -64)
-2 x -2 =3D 4 (not -4)

But if my calculator is correct, then the signed representations would
need 7 bits to represent +64 and 3 bits to represent +4 in a signed
notation.

KJ
```
 0

```On Sep 9, 11:09=A0am, KJ <kkjenni...@sbcglobal.net> wrote:

> then the signed representations would
> need 7 bits to represent +64 and 3 bits to represent +4 in a signed
> notation.
>

Make that 8 bits to represent +64 and 4 bits to represent +4 in signed
notation...sigh...

+64 =3D 01000000
+4 =3D 0100

KJ
```
 0