Bit Growth in a complex multiplier

What is the bit growth of a complex multiplier?

(a + bj)* (c +jd) = (ac - bd) + j(ad + bc).

So conventional bit growth suggests if a, b, c, d = 1.9 representation
(-512 to 511), the real and conventional components should have 9*2 + 1 =
1.19 representation. But really the magnitude only grows A.B (using
Euluer), where A= mag(a + jb) and B = mag(c + jd). So do I really only
need 18 bits and not 19?


---------------------------------------
Posted through http://www.DSPRelated.com

On 6/23/15 10:50 AM, sachinwannabe wrote:
> What is the bit growth of a complex multiplier?
>
> (a + bj)* (c +jd) = (ac - bd) + j(ad + bc).
>
> So conventional bit growth suggests if a, b, c, d = 1.9 representation
> (-512 to 511), the real and conventional components should have 9*2 + 1 =
> 1.19 representation. But really the magnitude only grows A.B (using
> Euluer), where A= mag(a + jb) and B = mag(c + jd). So do I really only
> need 18 bits and not 19?
>

sach, the thing to look at is just the real values in the product, like 
a*c, b*d, a*d, and b*c.

there is bit growth in *both* the left and right directions.

and remember that where the binary point lies in fixed-point arithmetic 
is a concept that exists in your mind, not the computer who thinks it's 
multiplying and adding integers.

yes, when you multiply two 10-bit signed numbers together, you get a 
19-bit signed number (unless you round).  where the binary point goes in 
the product is up to how you interpret the binary point of the 
multiplicand and multiplier going in.

and when you add two 19-bit signed numbers, you get a 20-bit signed 
number (unless you clip) and the position of the binary point (from the 
right) is unchanged.

so i would say that if a, b, c, d are Q1.9 fractional values, that the 
real and imaginary parts of the result are Q2.18 fractional values until 
you start rounding and/or clipping.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

robert bristow-johnson <rbj@audioimagination.com> wrote:
> On 6/23/15 10:50 AM, sachinwannabe wrote:
> > What is the bit growth of a complex multiplier?
> >
> > (a + bj)* (c +jd) = (ac - bd) + j(ad + bc).
> >
> > So conventional bit growth suggests if a, b, c, d = 1.9 representation
> > (-512 to 511), the real and conventional components should have 9*2 + 1 =
> > 1.19 representation. But really the magnitude only grows A.B (using
> > Euluer), where A= mag(a + jb) and B = mag(c + jd). So do I really only
> > need 18 bits and not 19?
> >

I can not see the original post so I replay to this one.

Both calculations give the same result.  In a, b, c, d are integers
between -2^n and 2*n - 1, then maximal magintude is

sqrt((-2^n)^2 + (-2^n)^2) = sqrt(2)2^n

which corresponds to a = -2^n and b = -2^n.  The magnitude
of the product is sqrt(2)2^n*sqrt(2)2^n = 2^(2n+1), so
coordinates of the product are bounded by 2^(2n+1).  Indeed

(-2^n - j2^n)^2 = (1 + j)^22^(2n) = 2j2^(2n) = j2^(2n+1)

so indeed such value of coordinate is possible.  The same
result follows from estimation of the product.

BTW: Either you limit input coordinates to -(2^n - 1)..(2^n-1)
or you need extra bit to represent positve product of numbers
with negative coordinates of maximal possible magnitude.

-- 
                              Waldek Hebisch
hebisch@antispam.uni.wroc.pl 

Waldek Hebisch  <hebisch@antispam.uni.wroc.pl> wrote:

>BTW: Either you limit input coordinates to -(2^n - 1)..(2^n-1)
>or you need extra bit to represent positve product of numbers
>with negative coordinates of maximal possible magnitude.

For the sake of completeness, a third approach is to perform the full
signed multiply, and then for the single case of the most positive
result, saturate it to the next most positive value.  This results in 
the (often) desired N+M-1 bit result for an N by M bit signed multiply.


S.

On 6/25/15 12:46 AM, Steve Pope wrote:
> Waldek Hebisch<hebisch@antispam.uni.wroc.pl>  wrote:
>
>> BTW: Either you limit input coordinates to -(2^n - 1)..(2^n-1)
>> or you need extra bit to represent positve product of numbers
>> with negative coordinates of maximal possible magnitude.
>
> For the sake of completeness, a third approach is to perform the full
> signed multiply, and then for the single case of the most positive
> result, saturate it to the next most positive value.  This results in
> the (often) desired N+M-1 bit result for an N by M bit signed multiply.
>

well, we're increasing (unnecessarily) the number of symbols.

returning to the OP's notation, since the addition of the cross-products 
is anticipated, multiply the two Q1.9 pairs of numbers first into two 
Q2.18 numbers (no loss of information, even in the case of -1 x -1), 
then add.  still a remote potential of overflow here if all four values 
of a, b, c, d are equal to -1, that can be tested for and saturated if 
necessary.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."