Programmable Devices
CPLDs, FPGAs, SoC FPGAs, Configuration, and Transceivers
20640 Discussions

Output of "x^2 + y^2" from 2's complement to binary (with sign)

Altera_Forum
Honored Contributor II
1,249 Views

Hi, 

 

I am using a altmult_add megafunction to generate output of x^2 + y^2 for inputs x and y, where both x and y are 2's complements. 

 

I understand that the output would always be a positive result. However, since the inputs are 2's complements, shouldn't the output be a 2's complement as well? 

 

So I need to convert the output from 2's complement to signed binary; what is a good of way of implementing this? 

 

Appreciate your guidance and help.
0 Kudos
8 Replies
Altera_Forum
Honored Contributor II
401 Views

You dont need to convert anything. Its already unsigned. For this, you just drop the MSB from the number if you are sure the output is ALWAYS positive (and therefore unsigned). It will always be a '0' anyway.

0 Kudos
Altera_Forum
Honored Contributor II
401 Views

I kind of knew that since it's a positive result, it would no longer be a two's complement, and your answer re-affirms this.  

 

Thank you :).
0 Kudos
Altera_Forum
Honored Contributor II
401 Views

It is still twos compliment. positive 2s complement numbers are the same as unsigned numbers with an extra 0 as the MSB.

0 Kudos
Altera_Forum
Honored Contributor II
401 Views

So you are saying that if x and y are 8-bits each, x^2 would be 16-bits and y^2 would also be 16-bits, and their sum would be 32-bits; so bit 31 would be the extra zero representing the sign?

0 Kudos
Altera_Forum
Honored Contributor II
401 Views

x/y = 8 bits signed 

x^2/y^2 = 16 bits signed  

 

if we add these two numbers we get a 17 bit result. bit 17 is always zero because the number is always positive, so it can be dropped to give a 16 bit Unsigned number. If you need to add it to any -ve numbers you have to add the sign bit back on again (a '0') so it might be worth keeping it after all.
0 Kudos
Altera_Forum
Honored Contributor II
401 Views

So, if x^2 and y^2 = 16-bits 

 

Is it always the case that x^2 + y^2 = 33-bits? 

And that bit 33 is THE sign bit (zero in this case)? 

 

Sorry to be picky about this; I have been trying to understand this since last week.
0 Kudos
Altera_Forum
Honored Contributor II
401 Views

No, that is not the case. 

 

when adding two N bit wide numbers the largest possible result is N+1 bit wide. 

 

let's assume both x² and y² are the largest possible 16 bit numbers (when using signed arithmetics): 

 

0x7FFF and 0x7FFF 

or binary: 0111.1111.1111.1111 

 

Adding those two numbers is equivalent to multiplying one of the numbers with 2. 

 

Multiplikation with 2 again is equivalent to shifting the number to the left by one, so we end up with: 

0.1111.1111.1111.1110 

 

which equals 0x0000FFFE 

 

When using unsigned arithmetics from now on we will not need the zeros at the beginning: so we end up with unsigned 0xFFFE.
0 Kudos
Altera_Forum
Honored Contributor II
401 Views

Hi guys, 

 

There's actually a couple of possible answers to this problem. 

 

If x and y are both 8-bit signed integers, then the range for x and y is -128 (1000_0000b) to 127 (0111_1111b), so the largest possible value of x^2 or y^2 is 128^2 = 16384 (4000h = 0100_0000_0000_0000b) which requires 16-bits to represent. If you then add x^2 and y^2, you need an extra bit to represent the sum, so 17-bits is required. 

 

If however, you limit the input range to symmetric signed integers, i.e., inputs are limited -127 to 127 (by converting any -128 codes into -127), then the largest possible value for x^2 or y^2 is 127^2 = 16129 (3F01h = 0011_1111_0000_0001h), which is still a 16-bit number, but the MSB (the second binary digit, since the first is the sign) is not set. This means that you can perform the accumulate x^2 + y^2 and not require 17-bits for the sum. 

 

Another reason for using symmetric integers is that you often want to flip the sign on data, and flipping the sign on -128 gives 128, which requires 1-bit more to represent, i.e., 9-bits. 

 

These types of DSP tricks are discussed here: 

 

http://www.ovro.caltech.edu/~dwh/correlator/pdf/esc-320paper_hawkins.pdf (http://www.ovro.caltech.edu/%7edwh/correlator/pdf/esc-320paper_hawkins.pdf

 

Cheers, 

Dave
0 Kudos
Reply