Recycling FFTs

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

> 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