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...?
Signed multiplication
Started by ●September 8, 2008
Reply by ●September 8, 20082008-09-08
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 . . 00010 2 00001 1 00000 0 11111 -1 11110 -2 11101 -3 11100 -4 11011 -5 11010 -6 11001 -7 11000 -8
Reply by ●September 8, 20082008-09-08
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
Reply by ●September 8, 20082008-09-08
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.
Reply by ●September 8, 20082008-09-08
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's_complement#Multiplication
Reply by ●September 8, 20082008-09-08
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's_complement#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
Reply by ●September 8, 20082008-09-08
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
Reply by ●September 8, 20082008-09-08
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
Reply by ●September 8, 20082008-09-08
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
Reply by ●September 8, 20082008-09-08
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
