Reply by robert bristow-johnson●June 25, 20152015-06-25
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."
>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.
Reply by Waldek Hebisch●June 24, 20152015-06-24
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
Reply by robert bristow-johnson●June 23, 20152015-06-23
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."
Reply by sachinwannabe●June 23, 20152015-06-23
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