Discrete and Fast Fourier Transform

Discrete Fourier Transform (DFT)

The DFT converts $N$ equally spaced samples $x_n$ of a signal in the time domain into $N$ complex frequency components $X_k$:

$$X_k=\sum_{n=0}^{N-1}x_n\,e^{-i2\pi kn/N},\quad k=0,\dots,N-1$$

and the inverse is

$$x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_k\,e^{i2\pi kn/N}$$

$|X_k|$ gives the amplitude and $\arg X_k$ the phase of the component at frequency $f_k=k/(N\Delta t)$. Direct evaluation needs $N^2$ complex multiplications.

Fast Fourier Transform (FFT)

The FFT (Cooley and Tukey, 1965) is an efficient algorithm for computing the DFT. For $N=2^m$ it repeatedly splits the sum into even- and odd-numbered samples:

$$X_k=E_k+W_N^{k}\,O_k,\qquad X_{k+N/2}=E_k-W_N^{k}\,O_k,\qquad W_N=e^{-i2\pi/N}$$

This "butterfly" operation reduces the work to $\tfrac{N}{2}\log_2N$ multiplications, so $N=1024$ needs about 5,000 operations instead of about $10^6$.

Uses in civil engineering: frequency content of earthquake records, vibration of bridges and buildings, spectral analysis of waves, and signal filtering.