1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ x = [1, 2, 3, 4, 3, 2]; % some folded real-valued signal is not just some real sequence, it's real and even so that its inverse-DFT will be real and even... So will you consider just any real sequence or a symmetric real sequence ? $\endgroup$ – Fat32 Oct 25 '17 at 13:56
  • $\begingroup$ @Fat32 in my mind folded means symmetric in the FFT sense that the later half of the values are the flipped version of the former half (minus the first value). The length of the sequence would be even. So it has got to be symmetric (minus the first value) otherwise the inverse FFT won't be real and there's no point to the question. $\endgroup$ – keith Oct 25 '17 at 14:01
  • $\begingroup$ so what you ask is a fast way of computing the inverse DFT of a real valued and even frequency sequence $X[k]$ , which will be an even and real sequence $x[n]$ in time and only half of which is necessarily to be computed. $\endgroup$ – Fat32 Oct 25 '17 at 14:06
  • $\begingroup$ @Fat32, yes as fast as possible, no wasted operations (which implies an output which yields only the first half of the $x[n]$ given input of the first half of the $X[k]$ using your notation). $\endgroup$ – keith Oct 25 '17 at 14:10
1
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ Thanks, I've upvoted you and accepted your answer as you put me on the right track by emphasising the correct terminology I need to search on, namely: real symmetric FFT algorithms. The first two pages of the paper On the Use of Symmetry in FFT Computation, LAWRENCE R. RABINER, IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-27, NO. 3, JUNE 1979 provides an $N / 4$ approach which is what I was after. $\endgroup$ – keith Oct 26 '17 at 8:28
  • $\begingroup$ thanks yes: for $N$-point real and even sequences both domains will be real and even therefore instead of $N$-point complex DFT, it would actually need half the samples (due to the evennes) and half the arithmetic (due to realness) hence a total $N/4$ point computations... $\endgroup$ – Fat32 Oct 26 '17 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.