The inverse FFT of a folded real sequence yields a real symmetric sequence. Are there any ways to exploit this symmetry to perform a smaller complex FFT or complex inverse FFT?
Background: it's possible to do this for a forward FFT of a real sequence (see: Real valued FFT in Matlab):
x = [1, 2, 3, 4, 5, 6, 7, 8]; % some real-valued signal
n = length(x); % must be even!
n2 = n/2; % assume n is even
z = x(1:2:n)+j*x(2:2:n); % complex signal of length n/2
Z = fft(z);
Ze = .5*( Z + conj([Z(1),Z(n2:-1:2)]) ); % even part
Zo = -.5*j*( Z - conj([Z(1),Z(n2:-1:2)]) ); % odd part
X = [Ze,Ze(1)] + exp(-j*2*pi/n*(0:n2)).*[Zo,Zo(1)]; % combine
X2 = fft(x);
Then X
and X2
yield the same values. With X
we have avoided the calculation of the symmetric values as we can recover those easily.
For the ifft:
x = [1, 2, 3, 4, 3, 2]; % some folded/symmetric real-valued signal (of even length)
ifft(x)
This yields a real symmetric sequence.
Would it be possible to take [1, 2, 3, 4]
and pack this into a complex FFT or inverse FFT to yield the same result?