The discrete Fourier transform ​

A sequence of complex numbers has the discrete Fourier transform (DFT)

measures how strongly the sequence correlates with the complex exponential of frequency cycles per record. The inverse maps back:

Both sums are matrix-vector products with the   matrix  . The matrix costs multiplications, which is the naive algorithm. The point of the FFT is that factors into sparse pieces, so the product costs .

Conventions ​

FFTL uses the two signs and the two normalisations that are common in signal processing:

functionsignnormalisation
fft (forward)none
bfft (backward)none
ifft per transformed dimension

With these,  , and   . FFTW.jl uses the same names and the same scalings. The dct of FFTL is the orthonormal one, the convention that keeps the energy unchanged.

Why a Fourier transform at all ​

For a signal sampled at rate with samples, bin is the frequency . A tone that is not exactly on a bin spreads over several bins. This is the leakage that windows trade off against resolution; the spectrum tutorial uses a record that contains whole cycles, so none occurs.

The bins above are the negative frequencies. For real input  , so the spectrum of a real signal carries only half its information, and rfft returns that half.

Multiplying spectra is convolution in time: the cyclic convolution of two sequences is the inverse transform of the product of their transforms. A linear convolution is the cyclic one of zero-padded inputs. This turns filtering of long signals into work; the convolution tutorial shows it.

The algorithm as divide and conquer ​

The idea that makes the FFT fast is the one behind merge sort. Split the sum by the parity of the index,   and   :

Each sum is a DFT of length , and the two are combined with multiplications by the twiddle factors . Recursing on the halves gives   , so  . The same identity works for any factor   , not only 2. Radix splits into a stage of -point transforms. The algorithms explanation describes how FFTL turns this recursion into a sequence of loops over memory without recursion.