Lecture
Echoes of Fourier
- Sound is modeled as a function of time, discretized into samples where 44,100 samples represent one second.
- Complex numbers are utilized to represent signals, visualized via a real and imaginary axis with polar forms defined by radius and angle.
- Complex multiplication corresponds geometrically to multiplying radii and adding angles.
- Euler's formula ($e^{i\theta} = \cos \theta + i \sin \theta$) establishes that complex exponentials represent circular motion on the unit circle, which is a more fundamental form of periodicity than sine or cosine alone.
- Positive frequencies correspond to counter-clockwise circular motion, while negative frequencies correspond to clockwise motion.
- In a finite discrete context, time is treated as wrapping around; the set of complex vectors $\mathbb{C}^n$ represents signals of length $n$.
- Any vector in $\mathbb{C}^n$ can be decomposed into a sum of complex sinusoids, which form an orthogonal basis for the space.
- The coefficients of this decomposition represent the magnitude (loudness) and phase (temporal alignment) of specific frequency components.
- The mapping from the time domain to these frequency coefficients is defined as the Discrete Fourier Transform (DFT).
- The Fast Fourier Transform (FFT), originally discovered by Gauss in 1805 and republished by Cooley and Tukey in 1965, computes the DFT in $O(n \log n)$ time, a significant improvement over the $O(n^2)$ complexity of direct calculation.
- The FFT utilizes a divide-and-conquer strategy, splitting signals into even and odd indexed components to recursively reduce computational load.
- High-frequency components in real-valued signals appear as symmetrical "mirror images" of low-frequency components due to the aliasing of frequencies (e.g., frequency $k$ is indistinguishable from negative frequency $-k$).
- Filtering involves removing specific frequency bins and applying the inverse Fourier transform, introducing negligible numerical error ($\approx 10^{-14}$ to $10^{-16}$) and resulting in a nearly perfect real-valued signal after extraction.
- Echoes are mathematically modeled as the convolution of an original signal ($A$) with an impulse response ($B$) that encodes the timing and amplitude of reflections.
- The impulse response represents the acoustic signature of a space, capturing all direct and secondary reflections resulting from a single sharp transient (impulse).
- Convolution in the time domain is equivalent to pointwise multiplication in the frequency domain, known as the Convolution Theorem.
- Applying the Convolution Theorem allows for efficient calculation of convolutions (e.g., audio reverb) in $O(n \log n)$ time using the FFT.
- Practical implementation requires padding signals with zeros to a power of 2 that exceeds the sum of the input lengths to prevent circular wrapping artifacts.
- Synthetic impulse responses can be generated by simulating acoustic reflections in a rectangular volume using an infinite lattice of mirrored sources, accounting for distance attenuation and wall absorption coefficients.
- In a simulated 30-meter hallway with 99.9% reflection, a resonant peak appears at roughly 10.9 Hz, corresponding to the physical wavelength of the room dimensions ($v/f \approx 30$ meters).
- Deconvolution (reversing the convolution to isolate the original signal or remove reverb) is theoretically possible but often numerically unstable if the frequency spectrum contains values near zero, leading to massive amplification of noise.
- Digital room correction systems attempt to approximate the inverse of a room's impulse response to flatten the frequency response of a recording space.
- Recording impulse responses often requires "smearing" the input pulse (using a chirp signal) to prevent microphone saturation and non-linear distortion, followed by deconvolution to extract the clean response.
- These concepts extend to two dimensions for image processing, where 2D convolutions can model blurring and deconvolution can theoretically reverse out-of-focus effects, though this remains computationally challenging.