Fast Fourier transform

The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform and its inverse. It is of extreme importance in digital signal processing and related fields. This article describes the algorithm; see discrete Fourier transform for applications.

Let x₀, ...., x_n-1 be complex numbers. We will assume for simplicity that n is a power of two; since the number of sample points n can usually be chosen freely by the application, this is no important restriction. Evaluating the formulas

              n-1         
   fj  =  1/n  ∑  xk e-2πijk/n     j = 0,...,n-1
              k=0

directly would take O(n²) arithmetical operations (see Big O). The basic idea of the Fast Fourier Transform is to reduce this runtime to O(n log n) by using a recursive approach: first compute the Fourier transforms of the even indexed numbers x₀, x₂,....,x_n-2, and of the odd indexed numbers x₁, x₃,....,x_n-1, and then combine those two results to produce the Fourier transform of the whole sequence.

We write n' = n/2 and denote the discrete Fourier transform of the even indexed numbers x'₀ = x₀, x'₁ = x₂,....,x'_n'-1 = x_n-2 by f'₀,...,f'_n'-1, and the transform of the odd indexed numbers x''₀ = x₁,x''₁ = x₃,...,x''_n'-1 = x_n-1 by f''₀, ..., f''_n'-1. Then it follows:

              n/2-1                      n/2-1
     fj = 1/n   ∑   x2k e-2πij(2k)/n  +  1/n  ∑   x2k+1 e-2πij(2k+1)/n 
               k=0                        k=0

               n'-1                             n'-1
        = 1/n   ∑   x'k e-2πijk/n'  +  1/n e-2πij/n  ∑   xk e-2πijk/n'

               k=0                              k=0

            / 1/2 f'j  +  1/2 e-2πij/n f''j     if j<n'
        =  { 
             1/2 f'j-n'  +  1/2 e-2πij/n f''j-n'    if j≥n'

This trick was already known to Gauss, who used it in orbital computations in astronomy. It became popular in 1965 after Cooley-Tukey published a paper describing how to arrange the numbers occurring in the algorithm conveniently in an array.

References:

• Cooley, J. W. and Tukey, O. W. An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Comput. 19, 297-301, 1965.
• Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/. A free (GPL) C library for computing discrete Fourier transforms in one or more dimensions using the Fast Fourier Transform.