The Azimuth Project
Fast Fourier transform

Contents

Idea

The Fast Fourier transform (FFT) denotes a family of algorithms that can be used to calculate the Fourier transform of a time series. The discrete Fourier transform of a finite time series, written as a vector of real numbers xx, is naiveley a matrix multiplication M*xM*x. In principle, the complexity of such an operation would be O(n 2)O(n^2), where nn is the number of elements of the time series. FFT algorithms use the very special structure of the Fourier matrix MM to achieve a much lower computational cost, namely a complexity of O(nlogn)O(n log n).

An FFT algorithm was known to Gauss, but was rediscovered in the mid 20th century and became relevant when computers allowed the calculation of the FFT for large datasets.

Details

Definition

Let (x) l=0,...,N1(x)_{l=0, ..., N-1} be a given finite time series of real numbers.

The FFT is about the calculation of

X r:= l=0 N1x lω rl X_r := \sum_{l = 0}^{N -1} x_l \; \omega^{r l}

for r=0,...,N1r = 0,..., N-1 and ω:=exp(2iπN)\omega := \exp{(\frac{2 i \pi}{N} )} being the NNth root of unity.

For convenience, we note that ω N N2=1\omega_N^{\frac{N}{2}} = -1 and ω N2=ω N 2\omega_{\frac{N}{2}} = \omega_N^2.

Divide and Conquer

The FFT algorithms are examples of divide and conquer algorithms.

Decimation in Time, Radix 2

We assume that the length NN of the given time series is a power of 2.

Note that we can rewrite the defining equation of the discrete Fourier transform in the following way:

X r= l=0 N21x 2lω 2rl+ω N r l=0 N21x 2l+1ω 2rl X_r = \sum_{l = 0}^{\frac{N}{2} -1} x_{2l} \; \omega^{2 r l} + \omega_N^r \sum_{l = 0}^{\frac{N}{2} -1} x_{2l+1} \; \omega^{2 r l}

Using ω N2=ω N 2\omega_{\frac{N}{2}} = \omega_N^2 we can rewrite this sum as:

X r= l=0 N21x 2lω N2 rl+ω N r l=0 N21x 2l+1ω N2 rl X_r = \sum_{l = 0}^{\frac{N}{2} -1} x_{2l} \; \omega_{\frac{N}{2}}^{r l} + \omega_N^r \sum_{l = 0}^{\frac{N}{2} -1} x_{2l+1} \; \omega_\frac{N}{2}^{r l}

This equation represents the FFT as the sum of two FFT of the length N2\frac{N}{2}, the first one involving all the even indexed elements of the time series x 0,x 2,...x_0, x_2, ... and the other one all elements with an odd index, x 1,x 3x_1, x_3 etc.

References

General

Two free online books:

  • C. Sidney Burrus: Fast Fourier Transforms (online version)

  • Douglas L. Jones: The DFT, FFT, and Practical Spectral Analysis (online version)

Implementations

Fastest Fourier Transform of the West

One of the most well known implementations is the FFTW (fastest Fourier Transform in the West):

The authors explain that an important part of performance optimizing is the use of the multi level caching architecture of modern CPUs, via a combination of automated self-testing (empirically determining which code performs best on the current machine, including implicitly cache effects) and cache-oblivious algorithms. A free online explanation of this concept can be found here:

  • Steven G. Johnson, Matteo Frigo: Implementing FFTs in Practice (online)

For an installation on Windows and linking to it from a Visual C++ 2010 Express Installation (VC) as of January 2012, note the following:

  • download the precompiled DLL from here

  • open a cmd shell, run vcvars32.bat from the VC\bin folder to set up the necessary environment variables,

  • execute “lib /def:libfftw3-3.def” using the lib.exe from the VC\bin folder to generate “libfftw3-3.lib”,

  • in VC, add “libfftw3-3.lib” in VC to your project via project -> properties -> linker -> input -> additional dependencies.