Efficient computation of inverse FFT of real sequence using half sized FFT or inverse FFT

Question

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?

Answer 1

As far as I understood your problem right, then the following code (modified from your code) provides an efficient computation of the $N$ point inverse-DFT of a real valued and even symmetric frequency sequence $X[k]$ in terms of an $M = N/2$ point inverse-DFT of an associated frequency sequence $Z[k]$, as the following MATLAB code shows:

It exploits the duality of operations between time to frequency and frequency to time mapping of DFT.

N = 10;                  % length N of frequency sequence X[k]
M = N/2;                 % M = N/2 , half-size
X = [4 3 2 1 0 -1 0 1 2 3];  % some real-valued even sequence X[k]
x = ifft(X,N)            % N-point I-DFT x[n] of N-point sequence X[k]

Z = X(1:2:N)+1j*X(2:2:N);% Half-Length complex frequency sequence Z[k]

z = ifft(Z,M);             % M-point DFT Z[k] 

% Construct first M+1 points of real-even x[n] from Z[k]
ze = +0.25*( z + conj( [z(1) , z(M:-1:2)] ) );       % even part
zo = -0.25*1j*( z - conj([z(1),z(M:-1:2)]) );        % odd part
xz = [ze,ze(1)] + exp(1j*2*pi*(0:M)/N).*[zo,zo(1)]; % COMBINE

Is this really an efficient way? Eventhough it exploits the symmetry and avoids computing the half of the sequence, it makes quite large number of pre-processing and post-processing which should be taken into account...