Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > VHDL > Signed multiplication

Reply
Thread Tools

Signed multiplication

 
 
knight
Guest
Posts: n/a
 
      09-08-2008
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...?
 
Reply With Quote
 
 
 
 
Tricky
Guest
Posts: n/a
 
      09-08-2008
On 8 Sep, 07:11, knight <(E-Mail Removed)> 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.
 
Reply With Quote
 
 
 
 
Tricky
Guest
Posts: n/a
 
      09-08-2008
On 8 Sep, 07:11, knight <(E-Mail Removed)> 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.
 
Reply With Quote
 
knight
Guest
Posts: n/a
 
      09-08-2008
>On Sep 8, 2:12 pm, Tricky <(E-Mail Removed)> 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..?


Thanks for the reply


 
Reply With Quote
 
knight
Guest
Posts: n/a
 
      09-08-2008
>On Sep 8, 2:12 pm, Tricky <(E-Mail Removed)> 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..?


Thanks for the reply


 
Reply With Quote
 
Muzaffer Kal
Guest
Posts: n/a
 
      09-08-2008
On Mon, 8 Sep 2008 04:10:55 -0700 (PDT), knight <(E-Mail Removed)>
wrote:

>>On Sep 8, 2:12 pm, Tricky <(E-Mail Removed)> 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.
 
Reply With Quote
 
rickman
Guest
Posts: n/a
 
      09-08-2008
On Sep 8, 12:58*pm, Muzaffer Kal <(E-Mail Removed)> wrote:
> On Mon, 8 Sep 2008 04:10:55 -0700 (PDT), knight <(E-Mail Removed)>
> wrote:
>
>
>
> >>On Sep 8, 2:12 pm, Tricky <(E-Mail Removed)> 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.


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

Rick
 
Reply With Quote
 
jeppe jeppe is offline
Senior Member
Join Date: Mar 2008
Location: Denmark
Posts: 348
 
      09-08-2008
A short comment - try a visit to this site:
http://tima-cmp.imag.fr/~guyot/Cours...ish/Multip.htm
very informative with interactive appletts

Jeppe
 
Reply With Quote
 
Muzaffer Kal
Guest
Posts: n/a
 
      09-09-2008
On Mon, 8 Sep 2008 10:33:14 -0700 (PDT), rickman <(E-Mail Removed)>
wrote:

>On Sep 8, 12:58*pm, Muzaffer Kal <(E-Mail Removed)> 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.
 
Reply With Quote
 
Tricky
Guest
Posts: n/a
 
      09-09-2008

>
> 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 = 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Source of term "multiplication" in matrix multiplication William Hughes C Programming 13 03-15-2010 02:04 PM
signed multiplication priya VHDL 2 11-17-2006 08:04 AM
Help to get a copy of A. D. Booth, "A signed binary multiplication technique," Weng Tianxiang VHDL 4 04-07-2005 04:10 PM
32x32 and 64x64 signed integer multiplication Christopher Dyken C Programming 18 02-24-2004 09:05 AM



Advertisments