6
$\begingroup$

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

|improve this question
$\endgroup$
  • 1
    $\begingroup$ I'll defer to someone with more knowledge, but one thing worth noting is that the discrete cosine transform enforces even symmetry. The "fast" DCT algorithms employ FFT structures that are optimized for these input constraints. I would start your search there. Other than that, I know you can pack a length N sequency 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. $\endgroup$ – Bryan Aug 22 '13 at 17:57
  • $\begingroup$ @Bryan: Wikipedia says "DCTs are equivalent to DFTs of roughly twice the length, operating on real data with even symmetry (since the Fourier transform of a real and even function is real and even)" $\endgroup$ – endolith Aug 23 '13 at 16:07
  • $\begingroup$ As I said, I'll defer to someone with more knowledge :) However, to your point, the DCT in general assumes the input is a length N sequence with no symmetry constraints, so it implicity enforces even-symmetry by "mirroring" the sequence about the origin. The method of mirroring is what distinguishes the DCT variants. If your length 'N' sequence is already even-symmetric, you could equivalently perform the DCT of half the sequence. $\endgroup$ – Bryan Aug 23 '13 at 16:42
  • 1
    $\begingroup$ Done. I'm not resistent to posting answers, but rather formally answering in domains I'm not comfortable in. Despite reading papers on DCTs, I've never implemented one myself. I've actually implemented the complex packing scheme in hardware before, but that didn't seem like it would exploit all of your input constraints at first glance. Glad I could help. $\endgroup$ – Bryan Aug 23 '13 at 19:08
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Seems the Type I DCT is exactly what I was looking for. I've tried to learn about the DCT in the past but could never get it. Today I finally do. :) SciPy's dct(a[:N/2+1], 1) produces the same output as rfft(a), but ~3 times as fast, or ~5 times as fast as fft(a). I made an example here $\endgroup$ – endolith Aug 23 '13 at 21:26
1
$\begingroup$

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.

|improve this answer
$\endgroup$

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.