The DFT of the window w_2N[n] is equal to W_2N[k] := exp(-i pi
(k-1/2)(1-1/N)) sin(pi(k-1/2))/sin(pi(k-1/2)/N). So
DFT( x1[n] w_2N[n]) = X1[k] * W_2N[k],
the circular convolution of X1 with the transform of the window
(similarly for X2). Therefore
X(2k +1) = (X1[k] - X2[k]) * W_2N[k]
The kernel W_2N is not sparse, therefore windowing & FFT is (at least
asymptotically) more efficient than the circular convolution operation.
> Regards,
> Andor
Reply by Andor●January 12, 20062006-01-12
Friends,
assume x[n] is a comlex vector of length 2N, and I want to compute the
2N-point DFT X[k] of x[n]. Also, I am given X1[k] = DFT(x1[n]) with x1
= x(0:N-1) and X2[k] = DFT(x2[n]) with x2 = x(N:2N-1). I want to save
time computing X by using X1 and X2.
DIF gives me X(2 k) = X1(k) + X2(k), so the even indices of X are very
smple to compute. Unfortunately, X(2 k + 1) = DFT((x1[n] - x2[n])
w_2N[n]), where w_2N is a complex phasor with frequency 2 pi / (2N). So
we have
X(2k+1) = DFT( x1[n] w_2N[n]) - DFT( x2(n) w_2N[n]) (1).
The multiplication in n-domain fof x1 and x2 with w_2N corresponds to a
frequency shift of (2pi)/(2N), in other words, I need to interpolate
X1 and X2 in halfway in between the bins and compute
X(2k+1) = X1(k+1/2) - X2(k+1/2) (2)
If I remember correctly, I need to this with sinc-interpolation (with
circular sinc-functions?). Unless there is some simple but accurate
approximative interpolation, I would say that it is faster to actually
compute X(2k+1) with (1) (ie. using two N-point FFTs than via (2).
What do you think?
Regards,
Andor