C++
C#
VB
JScript
All

# FFT

Copyright (C) 2005 IENT-RWTH Aachen

Fast Fourier Transform

Include

    signal/fft.h

Mixed radix algorithms

The implementation of the FFT uses the so-called mixed-radix algorithm. The theory is explained in the review article Self-sorting Mixed-radix FFTs by Clive Temperton. The same method is used in C by the GNU Scientific Library (GSL), and FFTW.

The mixed-radix FFT is based on optimized modules for small length FFTs. The implemented modules' lengths are 2,3,4,5,8,16,32 and 64. The mixed-radix FFT works for any length that can be decomposed in a product of modules' factors. No alternative is programmed yet, in case the length is not a multiple of these factors.

Precompiled FFT

Because of its long compilation time, some usual FFT functions are declared in the fft.cpp source file in order to precompile them. Any FFT calculation on dense arrays with float or double real types is considered as usual. Any other calls of FFT functions would need some longer compilation time, and you should consider precompiling them in object files of your project. You can avoid the precompilation by commenting the FFT_PRECOMPILE macro in genial_config.h

Complexity Level

You can choose the maximum size used by a FFT module. Possible values are 2,3,4,5,8,16,32 or 64, default value is 8. Just change the FFT_LEVEL macro in genial_config.h. The bigger it is, the quicker the calculation of the FFT is likely to be (depending on the length of your signal), but on the other side the bigger the requirements will be for your compiler.

SIMD optimizations

If your system supports SSE processor instructions (Pentium III and above), you would probably want to increase the speed of float based FFTs. SSE instructions can simultaneously handle 4 floats.

SSE2 instructions (Pentium IV) deal with 2 doubles at once. But consider to use single precision artihmetic instead of a double precision if execution time is important, and if precision is sufficient.

SSE3 instructions (on some Pentium IV) allow quicker complex arithmetic.

Include the corresponding header file ( sse.h, sse2.h or sse3.h ) before any other include statement in your project or uncomment the corresponding statement in genial_config.h.

Inlined functions

The FFT implementation makes an intensive use of inlined functions It is essential for an optimal execution speed, that the compiler really inline them. But the inline keyword is almost considered by the compiler as clue given by the programmer. The Visual and Intel Compilers can force inlining: Uncomment the corrsponding declaration in genial_config.h to assure maximal execution speed.

Twiddle tables

The FFT calculation needs tables named twiddles. The twiddle tables depend on the length N of the signal. Because of memory considerations, only twiddles of a given signal length are calculated at once. But because of speed consideration, they are stored in static variables, invisible for the user, in the hope that the next FFT calculation will use a signal of the same length. So if you need to compute several FFT, try to group the signals according to their length.

abs_fft | FFT magnitude of a signal, magnitude spectrum
fft | FFT of a signal
fft_in_place | FFT in place of a signal
half_real_fft | FFT of a real signal
half_real_row_fft | FFT of every row of a real signal
ifft | IFFT of a signal
norm_fft | FFT squared magnitude of a signal, energy spectrum
real_ifft | IFFT of a complex-symmetric signal
row_fft | FFT of every row of a signal
row_ifft | IFFT of every row of a signal

See Also

Signal Processing