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
Recycling FFTs
Started by ●January 12, 2006
Reply by ●January 12, 20062006-01-12
> X(2k+1) = DFT( x1[n] w_2N[n]) - DFT( x2(n) w_2N[n]) (1).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