any smart methods - FFT related

Hi,

I am trying to optimize a piece of code where am stopped at the
following point:

I have
Y(F) = FFT[ x(n) * w(n)]  where * is multiplication. 0<= n <=N

With Y(F) in hand (already computed) I would like to know if anyone
could think of a smart way of finding out Z(F) without much complexity
where,

Z(F) = FFT[ x(n) * w(N-n)]

On Wed, 20 May 2009 05:13:59 -0700, hurry wrote:

> Hi,
> 
> I am trying to optimize a piece of code where am stopped at the
> following point:
> 
> I have
> Y(F) = FFT[ x(n) * w(n)]  where * is multiplication. 0<= n <=N
> 
> With Y(F) in hand (already computed) I would like to know if anyone
> could think of a smart way of finding out Z(F) without much complexity
> where,
> 
> Z(F) = FFT[ x(n) * w(N-n)]

My knee-jerk reaction is "can't be done", unless w(n) and x(n) has some 
fairly regular properties.

Consider this counter-example:  If x(n) = d(n-10), where d is the 
Kronecker delta*, and if w(n) = d(n-5), then Y(F) = zero, but Z(F) may 
well not be.  I am sure that there are other, less contrived, counter-
examples.

* I.e. d(n) = 1 for n = 0, 0 otherwise, d(n-10) = 1 for n = 10, 0 
otherwise, etc.

-- 
http://www.wescottdesign.com

On May 20, 5:13 am, hurry <hurrynar...@gmail.com> wrote:
> Hi,
>
> I am trying to optimize a piece of code where am stopped at the
> following point:
>
> I have
> Y(F) = FFT[ x(n) * w(n)]  where * is multiplication. 0<= n <=N
>
> With Y(F) in hand (already computed) I would like to know if anyone
> could think of a smart way of finding out Z(F) without much complexity
> where,
>
> Z(F) = FFT[ x(n) * w(N-n)]

Use a window where w(n) == w(N-n).

Dale B. Dalrymple

On May 20, 8:13&#4294967295;am, hurry <hurrynar...@gmail.com> wrote:
>
> I am trying to optimize a piece of code where am stopped at the
> following point:
>
> I have
> Y(F) = FFT[ x(n) * w(n)] &#4294967295;where * is multiplication. 0 <= n < N

first of all, you have some notational problems.  like what is "F"?

i assume that N is the size of your FFT (note that i changed

   "0 <= n <= N"  to  "0 <= n < N" ).

the usual notation for the DFT (for which the FFT is a "fast" method
of computing it) has variable parameters n, k, and N.  so i'm gonna
assume your "F" is what the textbooks say is "k" and i'm correcting
all of your notation below.


  Y[k] = DFT{ x[n] * w[n] }

means

  y[n] = x[n] * w[n]

and

  Y[k] = DFT{ y[n] }

we know that

  Y[k] = DFT{ x[n] * w[n] }

       = X[k] (*) W[k]

where

  X[k] = DFT{ x[n] }

  W[k] = DFT{ w[n] }

and

  (*) means circular convolution.


> With Y[k] in hand (already computed) I would like to know if anyone
> could think of a smart way of finding out Z(F) without much complexity
> where,
>
> Z[k] = DFT{ x[n] * w[N-n] }

so what this means is

  Z[k] = DFT{ z[n] }

where

  z[n] = x[n] * w[N-n]

well, if there is any symmetry to w[n], then w[-n] should be the
same.  since the DFT periodically extends anything that goes into it, w
[N-n] is the same as w[-n].  so it all depends on if there is symmetry
in w[n].

is there any symmetry to x[n]?  (generally, i look at "w[n]" as a
window function where i might expect symmetry and "x[n]" as completely
arbitrary data.)  but if there is symmetry to *either* x[n] or w[n]
(it need not be both), you can get a simplified answer.

r b-j