Fourier transform

In short: The Fourier transform decomposes a signal into the oscillations of different frequencies it is made of.

In more detail: Instead of “how loud is it at each moment?” it answers “how strongly is each frequency present?”. Computers use the discrete variant (DFT), which the FFT algorithm computes in O(n log n) instead of O(n²).

In Depth

• Idea: Any signal can be written as a sum of sine and cosine waves.
• Result: A spectrum of amplitude (strength) and phase (shift) per frequency.
• Sampling theorem: To capture a frequency f you must sample at at least 2·f (Nyquist). Otherwise aliasing errors appear.
• Use: Equalisers and spectrum displays in audio programs, compression (MP3 and JPEG use related transforms), noise filters, fast multiplication of large numbers, radio and Wi-Fi (OFDM).
• Limit: The spectrum does not say when a frequency occurred. The short-time Fourier transform (spectrogram) covers that.

See also: Big-O notation