taking cubic/square product of a two's complement system

Hi,

this is not strictly related to digital signal processing but rather to dealing with a multiplication of two's complements.
Basically, I try to implement a square/cubic product of a signal. I have got a 16-bit signed integer, so I can represent a value within the range of +-2^15 (equals+-32768). Squaring value already apparently results mostly in an overflow, not even thinking of a further multiplication (the cubic product).

I am really wondering how I could map a squared product onto this relatively small range. A multiplication of two 16-bit (actually 15-bit magnitude) values results in an 32-bit result. Unfortunately, it's not as easy as just truncating the lower 8 LSBs.

Anybody has got an idea how to deal with this?

Thanks and BRs, Flo

On Wednesday, December 19, 2012 9:56:41 AM UTC-5, Florian Schlembach wrote:
> Hi,
> 
> 
> 
> this is not strictly related to digital signal processing but rather to dealing with a multiplication of two's complements.
> 
> Basically, I try to implement a square/cubic product of a signal. I have got a 16-bit signed integer, so I can represent a value within the range of +-2^15 (equals+-32768). Squaring value already apparently results mostly in an overflow, not even thinking of a further multiplication (the cubic product).
> 
> 
> 
> I am really wondering how I could map a squared product onto this relatively small range. A multiplication of two 16-bit (actually 15-bit magnitude) values results in an 32-bit result. Unfortunately, it's not as easy as just truncating the lower 8 LSBs.
> 
> 
> 
> Anybody has got an idea how to deal with this?
> 
> 
> 
> Thanks and BRs, Flo

You can compand (compress-expand) the numbers (your values will no longer be exact but rather approximate). How precise does your result need to be in terms of relative error? Are you trying to save storage?

Clay

> You can compand (compress-expand) the numbers (your values will no longer be exact but rather approximate). How precise does your result need to be in terms of relative error? Are you trying to save storage?

haven't thought about relative error yet. The idea is, to put in a sinosoidal signal, square it and cubic it in order to produce additional frequency components. 
How do I have to scale the compand in order to keep the relative error small?

Are you aware that discarding LSBs always rounds down? 
What you probably intended is to round to the nearest integer, but that's
not the same (add 1/2 LSB of the rounded precision, THEN  discard the lower
bits).

On Wednesday, December 19, 2012 10:55:15 AM UTC-5, Florian Schlembach wrote:
> > You can compand (compress-expand) the numbers (your values will no longer be exact but rather approximate). How precise does your result need to be in terms of relative error? Are you trying to save storage?
> 
> 
> 
> haven't thought about relative error yet. The idea is, to put in a sinosoidal signal, square it and cubic it in order to produce additional frequency components. 
> 
> How do I have to scale the compand in order to keep the relative error small?

You can do a nearly constant relative error companding such as mu-law where you adjust the compression to balance relative error and the number of bits.

Florian Schlembach <florian.schlembach@gmail.com> wrote:
 
> this is not strictly related to digital signal processing but 
> rather to dealing with a multiplication of two's complements.
> Basically, I try to implement a square/cubic product of a signal. 
> I have got a 16-bit signed integer, so I can represent a value 
> within the range of +-2^15 (equals+-32768). 

Well, first you get -32768 to +32767. Usually that isn't so much
of a problem, but you should know about it.

Often in DSP work, one uses scaled fixed point, moving the binary
point left 15 bits. That allows values from about -1.0000 to 0.9999,
not again that the negative range is slightly larger.

Now, when you multiply scaled binary values, just like multiplying
scaled decimal values (with the decimal point not to the right
of the last digit), you have to position the binary point of
the product. 

If you multiply two values with 15 bits after the binary point,
the product has 30 bits after the binary point. To get back to
the original representation of 16 bits with 15 after the binary
point, you have to get rid of 15 bits from the right. 

If you want values from -32768 to +32767, you still want to get
rid of 15 bits after the multiply. 

You need to decide if you want to round or truncate, too.

> Squaring value already apparently results mostly in an overflow, 
> not even thinking of a further multiplication (the cubic product).
 
> I am really wondering how I could map a squared product onto 
> this relatively small range. A multiplication of two 16-bit 
> (actually 15-bit magnitude) values results in an 32-bit result. 
> Unfortunately, it's not as easy as just truncating the 
> lower 8 LSBs.

Yes, you have to truncate (remove) at least 15 bits to get back
in range.

Many high-level languages don't have an operation to return the high
half of a product. Sometimes, you can get the full (double length)
product and shift right.

-- glen

Florian Schlembach <florian.schlembach@gmail.com> writes:

> Hi,
>
> this is not strictly related to digital signal processing but rather to dealing with a multiplication of two's complements.
> Basically, I try to implement a square/cubic product of a signal. I
> have got a 16-bit signed integer, so I can represent a value within
> the range of +-2^15 (equals+-32768). Squaring value already apparently
> results mostly in an overflow, not even thinking of a further
> multiplication (the cubic product).
>
> I am really wondering how I could map a squared product onto this
> relatively small range. A multiplication of two 16-bit (actually
> 15-bit magnitude) values results in an 32-bit result. Unfortunately,
> it's not as easy as just truncating the lower 8 LSBs.

First of all, get your details right. Squaring a signed two's complement
16-bit number requires 31 bits if you want to include -32768 * -32768.
If you can omit that case you can use 30 bits.

So if you want to keep the result in a 16 bit (unsigned) value and avoid
overflows, you need to round at either the 15th or 14th binary digit
(respectively) and shift right 15 or 14 bits, and consider the result
scaled U(31,-15) or U(30,-14), respectively (see note).

The problem with this is that you completely lose low-level information.
For example, (-128)^2 will become 0. SC'est la vie - you can't have
something for nothing.

--Randy

Note: You may want to refer to my paper on fixed-point arithmetic
to understand my notation:

  http://www.digitalsignallabs.com/fp.pdf
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

On 12/19/12 10:40 AM, clay@claysturner.com wrote:
> On Wednesday, December 19, 2012 9:56:41 AM UTC-5, Florian Schlembach wrote:

>>
>> this is not strictly related to digital signal processing but rather to dealing with a multiplication of two's complements.

this is definitely in the topic domain of digital signal processing.  we 
sometimes called it "effect of finite word size" or "quantization 
effects" and it touches many practical and theoretical aspects of DSP.

>>
>> Basically, I try to implement a square/cubic product of a signal. I have got a 16-bit signed integer, so I can represent a value within the range of +-2^15 (equals+-32768). Squaring value already apparently results mostly in an overflow, not even thinking of a further multiplication (the cubic product).
>>
>>
>>
>> I am really wondering how I could map a squared product onto this relatively small range. A multiplication of two 16-bit (actually 15-bit magnitude) values results in an 32-bit result. Unfortunately, it's not as easy as just truncating the lower 8 LSBs.

>
> You can compand (compress-expand) the numbers (your values will no longer be exact but rather approximate). How precise does your result need to be in terms of relative error? Are you trying to save storage?
>

Clay, you brought up this companding twice.  i guess i don't get it. 
you can't square the compressed values and use that as a valid 
representation of the squared value or even of the compressed version of 
the properly squared value.

with companding, you have to nearly always expand the compressed value 
back into linear, do the math in the linear domain and deal with all of 
the finite word width issues you would have to deal with without 
companding, and then, with your result compress again.

a decent bipolar log (like mu-law or A-law, i think the smoothest would 
be an arcsinh-law) will allow you to represent values equally 
accurately, no matter what the scale is.  but the math nearly always has 
to be done in the linear domain, no?


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Wednesday, December 19, 2012 3:10:33 PM UTC-5, robert bristow-johnson wrote:
> On 12/19/12 10:40 AM, clay wrote:
> 
> > On Wednesday, December 19, 2012 9:56:41 AM UTC-5, Florian Schlembach wrote:
> 


> 
> Clay, you brought up this companding twice.  i guess i don't get it. 
> 
> you can't square the compressed values and use that as a valid 
> 
> representation of the squared value or even of the compressed version of 
> 
> the properly squared value.
> 
> 
> 
> with companding, you have to nearly always expand the compressed value 
> 
> back into linear, do the math in the linear domain and deal with all of 
> 
> the finite word width issues you would have to deal with without 
> 
> companding, and then, with your result compress again.
> 
> 
> 
> a decent bipolar log (like mu-law or A-law, i think the smoothest would 
> 
> be an arcsinh-law) will allow you to represent values equally 
> 
> accurately, no matter what the scale is.  but the math nearly always has 
> 
> to be done in the linear domain, no?
> 
> 

If the companding is logarithmic or closely approximates it, then double the number to square it!

Clay

On Wed, 19 Dec 2012 07:55:15 -0800, Florian Schlembach wrote:

>> You can compand (compress-expand) the numbers (your values will no
>> longer be exact but rather approximate). How precise does your result
>> need to be in terms of relative error? Are you trying to save storage?
> 
> haven't thought about relative error yet. The idea is, to put in a
> sinosoidal signal, square it and cubic it in order to produce additional
> frequency components. How do I have to scale the compand in order to
> keep the relative error small?

The DSP-ish way to do this is to use fixed-point fractional numbers, 
where a 16-bit signed number ranges from -1 to almost 1.  Then your 
squares and cubes fit nicely into the range.

Unfortunately, while it's easy to implement this stuff in assembly, it 
can be tedious to do so in C.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com