8.8 Summary

8.8 Summary#

  • The Fourier transform is a mathematical tool with three properties that make it impractical to compute: it integrates over infinite time, it operates on continuous signals, and it is defined for every real frequency.

  • Issue 1 (finite time): multiplying by a rectangular window restricts the transform to a finite interval, \(\hat{X}(\omega) = \int_0^T x(t) e^{-j\omega t} dt\). This introduces spectral leakage, a smearing of the spectrum.

  • Issue 2 (discrete samples): a Riemann sum turns the integral into a finite sum over samples, \(\hat{X}(\omega) \propto \sum_{n=0}^{N-1} x[n] e^{-j\omega n \Delta t}\).

  • Issue 3 (finite frequencies): since a signal sampled at \(f_s\) only has content in a band of width \(f_s\), we test \(N\) evenly-spaced analysis frequencies (bins), spaced \(\Delta f = f_s / N = 1/T\) apart.

  • The discrete Fourier transform is \(\texttt{DFT}(x)[k] = \sum_{n=0}^{N-1} x[n]\, e^{-2\pi j k n / N}\), mapping \(N\) samples to \(N\) complex bins.

  • For real signals, even/odd symmetry makes the upper bins redundant, so the DFT has only \(N/2 + 1\) non-redundant bins spanning \([0, f_s/2]\). This is np.fft.rfft.

  • The naive DFT is \(O(N^2)\). The fast Fourier transform uses divide and conquer to compute it in \(O(N \log N)\).

  • The DFT is invertible, enabling a perfect round trip between the time and frequency domains, which we used to analyze and resynthesize a clarinet note.