Signed multiplication

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...?

On Sep 8, 2:14*am, 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...?


Here's some numbers. If the leftmost bit is a 1, then the number is a
negative number in 2's complement form, and to convert it to positive,
you'd complement and add 1. As for the logic to to do the
calculation, there are many ways. Peatman's book is a good start.
There are a lot of others.

integer value
code

knight schrieb:
> hi
>
> Can anyone tell me how can i multiply two signed numbers in FPGA.
> How the logic is really implemented..

If the number of bits in the factors is identical to the number of bits
in the product, you do not need to care whether the numbers are signed
in two's complement representation or unsigned, you only need to
interpret the result accordingly, though it might be hard to detect
overflows. (That is the "unsigned" multiplication algorithm also works
"magically" as signed multiplication with two's complement input, as
does addition and subtraction.)

If more bits are available in the product (which is usually a good idea)
or you need to detect overflows, you have to multiply the numbers and
their signs separately. That said, if A and B are the inputs:

sign <- false
if a < 0:
a <- (-a)
sign <- not(sign)
if b < 0:
b <- (-b)
sign <- not(sign)
product <- a * b #unsigned multiplication
if sign:
product <- (-product)

So long,
Thomas

On Sep 8, 2:14*pm, 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...?

* uns uns uns unsigned multiply; length of result = length of
1st par + length of 2nd par - 1
* sgn sgn sgn signed multiply (two's-complement); length of
result = length of 1st par + length of 2nd par - 1
* uns nat uns multiply a non-negative int with an uns; nat is
converted to uns (length = length of 1st par) before multiplication;
length of result = 2 * (length of 1st par) - 1
* nat uns uns multiply an uns with a non-negative int; nat is
converted to uns (length = length of 2nd par) before multiplication;
length of result = 2 * (length of 2nd par) - 1
* sgn int sgn multiply an int with a sgn (two's-complement); int
is converted to sgn (length = length of 1st par) before
multiplication; length of result = 2 * (length of 1st par) - 1
* int sgn sgn multiply a sgn with an int (two's-complement); int
is converted to sgn (length = length of 2nd par) before
multiplication; length of result = 2 * (length of 2nd par) - 1

-----------------
looks like a mess -_-!
check it from :
http://www.vhdl.org/comp.lang.vhdl/FAQ1.html#4.8.1

Cause I am using Xilinx device and the usual way is using MUL core.
The implemention of muls in FPGA varies, Mark Zwoski's book on VHDL
provide a one which the computation cycles is only depend on the word-
length of the operand.

On Sep 8, 6:14 pm, move <liubeny...@gmail.com> wrote:

> length of result = 2 * (length of 1st par) - 1
> * nat uns uns multiply an uns with a non-negative int; nat is
> converted to uns (length = length of 2nd par) before multiplication;
> length of result = 2 * (length of 2nd par) - 1
> * sgn int sgn multiply an int with a sgn (two's-complement); int
> is converted to sgn (length = length of 1st par) before
> multiplication; length of result = 2 * (length of 1st par) - 1
> * int sgn sgn multiply a sgn with an int (two's-complement); int
> is converted to sgn (length = length of 2nd par) before
> multiplication; length of result = 2 * (length of 2nd par) - 1
>
> -----------------
> looks like a mess -_-!
> check it from :http://www.vhdl.org/comp.lang.vhdl/FAQ1.html#4.8.1
>
> Cause I am using Xilinx device and the usual way is using MUL core.
> The implemention of muls in FPGA varies, Mark Zwoski's book on VHDL
> provide a one which the computation cycles is only depend on the word-
> length of the operand.


hi
thank you.
But how can you implement a signed multiplication by 2's complement
method..?
Don't you need to change the number to unsigned and then multiply..?
If you directly multiply the signed number and its 2's complement,
won't the result change..?

As here..

Suppose i am multiplying -3 and 3 (appending only 1 bit)
that means 00011 * 11101
So the result is 0001010111.
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
But some times the result is correct as in here
http://en.wikipedia.org/wiki/Two&#39...Multiplication

knight wrote:
> On Sep 8, 6:14 pm, move <liubeny...@gmail.com> wrote:
>
>> length of result = 2 * (length of 1st par) - 1
>> * nat uns uns multiply an uns with a non-negative int; nat is
>> converted to uns (length = length of 2nd par) before multiplication;
>> length of result = 2 * (length of 2nd par) - 1
>> * sgn int sgn multiply an int with a sgn (two's-complement); int
>> is converted to sgn (length = length of 1st par) before
>> multiplication; length of result = 2 * (length of 1st par) - 1
>> * int sgn sgn multiply a sgn with an int (two's-complement); int
>> is converted to sgn (length = length of 2nd par) before
>> multiplication; length of result = 2 * (length of 2nd par) - 1
>>
>> -----------------
>> looks like a mess -_-!
>> check it from :http://www.vhdl.org/comp.lang.vhdl/FAQ1.html#4.8.1
>>
>> Cause I am using Xilinx device and the usual way is using MUL core.
>> The implemention of muls in FPGA varies, Mark Zwoski's book on VHDL
>> provide a one which the computation cycles is only depend on the word-
>> length of the operand.
>
>
> hi
> thank you.
> But how can you implement a signed multiplication by 2's complement
> method..?
> Don't you need to change the number to unsigned and then multiply..?
> If you directly multiply the signed number and its 2's complement,
> won't the result change..?
>
> As here..
>
> Suppose i am multiplying -3 and 3 (appending only 1 bit)
> that means 00011 * 11101
> So the result is 0001010111.
> 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
> But some times the result is correct as in here
> http://en.wikipedia.org/wiki/Two&#39...Multiplication
>

If you read the Wikipedia explanation carefully you will see that you
need to double the precisiion of the input data first. To represent both
3 and -3 you need at least a 3 bit two's complement representation,
which you then need to double in precision to 6 bits. You then do a
6-bit x 6-bit 2's complement multiply and discard the 6 MS bits.

3 = 011 -> 000011
-3 = 101 -> 111101

000011 x 111101 = (000010)110111 -> 110111 = -9.

Paul

On Sep 8, 6:59*am, Thomas Richter <t...@math.tu-berlin.de> wrote:
> knight schrieb:
>
> > hi
>
> > Can anyone tell me how can i multiply two signed numbers in FPGA.
> > How the logic is really implemented..
>
> If the number of bits in the factors is identical to the number of bits
> in the product, you do not need to care whether the numbers are signed
> in two's complement representation or unsigned, you only need to
> interpret the result accordingly, though it might be hard to detect
> overflows. (That is the "unsigned" multiplication algorithm also works
> "magically" as signed multiplication with two's complement input, as
> does addition and subtraction.)

that's not true at all, except for the trivial case where both signed
numbers going in happen to be non-negative.

:-\ ???

let's say you're multiplying two 8-bit numbers -60 by +50 (answer
should be -3000).

if you leave the 2's complement bits of -60 untouched, it's the same
as 196. the 16-bit unsigned product has a bit pattern that looks like
9800, which is not the same as 65536-3000 = 62536. it's not just how
we interpret the bits, the bits are different.

to the OP: one way to do it without "if" statements is to convert the
2's comp numbers to "constant offset" numbers (by adding the magnitude
of the most negative possible number, which is the same as just
flipping the sign bit). then these intermediate values are always non-
negative, then multiply them with a regular unsigned multiplier, then
fix the result of the multiplication by subtracting scaled values of
your two input numbers.

like this:

let N be the word width of the two inputs, X and Y, and 2N is the
width of the product, XY.

let

A = X + 2^(N-1)

B = Y + 2^(N-1)


A*B = (X + 2^(N-1))*(Y + 2^(N-1))
X*Y + (X+Y)*2^(N-1) + 2^(2N-2)

XY = (X + 2^(N-1))*(Y + 2^(N-1)) - (X+Y)*2^(N-1) - 2^(2N-2)

the multiplication right of the equal sign is completely unsigned. it
*is* true that signed 2's complement adders and subtracters are no
different from unsigned binary adders and subtracters. you subtract
copies of X and Y shifted left by N-1 bits and you subtract (with
borrowing) 2^(2N-2) which is one bit right of the MSB.

r b-j

testing... 1, 2, 3...

Google just dropped a completed post of mine (after first telling me
that it was posted and even showing it on the list).

.... bastards.

r b-j

On Sep 8, 2:14*am, 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...?

let's try posting this again.

one way to do it without "if" statements is to convert the
2's comp numbers to "constant offset" numbers (by adding the magnitude
of the most negative possible number, which is the same as just
flipping the sign bit). then these intermediate values are always
non-
negative, then multiply them with a regular unsigned multiplier, then
fix the result of the multiplication by subtracting scaled values of
your two input numbers.

like this:

let N be the word width of the two inputs, X and Y, and 2N is the
width of the product, XY.

we know that

-2^(N-1) <= X < +2^(N-1)
-2^(N-1) <= Y < +2^(N-1)


let

A = X + 2^(N-1)
B = Y + 2^(N-1)

then we know that

0 <= A < +2^N
0 <= B < +2^N

so they're unsigned numbers.

A*B = (X + 2^(N-1))*(Y + 2^(N-1))
= X*Y + (X+Y)*2^(N-1) + 2^(2N-2)

XY = (X + 2^(N-1))*(Y + 2^(N-1)) - (X+Y)*2^(N-1) - 2^(2N-2)

the multiplication right of the equal sign is completely unsigned. it
*is* true that signed 2's complement adders and subtracters are no
different from unsigned binary adders and subtracters (although it
is not true of multipliers as Thomas R. suggested). you subtract
copies of X and Y shifted left by N-1 bits and you subtract (with
borrowing) 2^(2N-2) which is one bit right of the MSB.

r b-j

On Mon, 8 Sep 2008 09:39:18 -0700 (PDT), robert bristow-johnson
<rbj@audioimagination.com> wrote:

>
>testing... 1, 2, 3...
>
>Google just dropped a completed post of mine (after first telling me
>that it was posted and even showing it on the list).
>
>... bastards.

I see your earlier post with the same time as this. I recall that
Google has a delay in either making a new post visible, or in actually
posting it. It's been a few years since I've used groups.google.com to
post, but that delay before seeing my just=posted posts, wherever it
is or was, was always frustrating.

>
>r b-j