The Azimuth Project
Fast Fourier transform



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.



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.



Two free online books:


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:

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