Can you quarter the processing time for real, symmetric FFTs?

Question

The DFT of a real signal is Hermite-symmetric, so you can roughly halve the computation time/memory by not bothering to calculate half the values of the spectrum (and complex conjugating the existing values and copying them to the second half if needed). So the rfft operation takes N samples and outputs N/2 spectrum bins in half the time, for instance.

Signals which are even-symmetrical and real have even-symmetrical and real spectra (and real spectra take half the memory to store as complex spectra), so for symmetrical input, can the calculation be halved again by only using the first half of the signal (N/2) to generate the first half of the spectrum (N/2)? How?

Is there a way to take the regular FFT of the N/2 half-signal and manipulate the output to produce the N/2 half-spectrum?

(real/odd ⇔ imaginary/odd would work, too, but real/even ⇔ real/even case is simpler to follow.)

Answer 1

There are many possible reductions in the number of computations for the DFT for constrained inputs. Looking closer at what well known DFT libraries do (FFTW for example) should be a good resource for how one can exploit these constraints. For your case, I would look at the discrete cosine transform (DCT). The discrete cosine transform enforces even symmetry. The "fast" DCT algorithms employ FFT structures that are optimized for these input constraints. The types of implicit even-symmetry mirroring that the DCT perform are what differentiate the various DCT types (Type I, Type II, ...). If your sequence is truly even-symmetric, then you could use a fast DCT algorithm (one based on FFT structures) with half of your data knowing the algorithm is assuming the other half is equivalent (albeit time-reversed). This should result in a reduction in the number of overall operations, as it would require a DFT of twice this length if you went the normal route.

You can also pack a length N sequence into N/2 complex samples and for not much added complexity you can recover a length N FFT. So you can sort of attack it from the other angle of doing a half-length complex FFT. While this seems less efficient, for a typical FFT structure you are complex after the first stage anyways, and so for large DFT sizes this becomes very efficient.

Answer 2

I'm not sure about quartering the process time but this is what I can think of for now. N point DFT of x.

$X_k = \sum_{n=0}^{N-1}x_nW_N^{kn}$

By the even symmetry assumption

$X_k = \sum_{n=0}^{N/2-1}x_n(W_N^{kn}+W_N^{k(N-1-n)})$

Then we simplify

$X_k = W_N^{k(N-1)/2}\sum_{n=0}^{N/2-1}x_n(W_N^{kn}W_N^{-k(N-1)/2}+W_N^{-kn}W_N^{k(N-1)/2})$

$X_k = 2W_N^{k(N-1)/2}\sum_{n=0}^{N/2-1}x_n\cos(2\pi k\frac{n-(N-1)/2}{N})$

There are probably some errors but if simplifications are valid the 'FFT' size is reduced by a factor of 2 and the twiddle factors are real (this maybe corresponds to your quartering). As in normal FFT the symmetry and periodicity can be exploited to decompose the 'symmetric FFT' into radix-2 steps for instnace.