Community
cancel
Showing results for
Did you mean:
Honored Contributor I
887 Views

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

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?

8 Replies
Honored Contributor I
39 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.

Honored Contributor I
39 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 :).
Honored Contributor I
39 Views

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

Honored Contributor I
39 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?

Honored Contributor I
39 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.
Honored Contributor I
39 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)?

Honored Contributor I
39 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.
Honored Contributor I
39 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