Waves & Fourier Analysis — Superposition, DFT, FFT Butterfly & Nyquist Theorem

1. Simple Harmonic Motion & Superposition

A mass on a spring satisfies Newton's second law with a restoring force F = −kx. The solution is a sinusoid: x(t) = A cos(ωt + φ) where ω = √(k/m). When two or more waves pass through the same medium simultaneously, their displacements add: constructive interference amplifies, destructive interference cancels.

2. The Discrete Fourier Transform

Given N samples x[n] of a signal, the DFT computes the spectrum X[k] — the amplitude and phase of each frequency component. Formally:

Direct computation of all N output values costs O(N²) multiply-add operations — too slow for large N. The Fast Fourier Transform exploits the twiddle-factor symmetry to reduce this to O(N log N).

3. FFT Butterfly — O(N log N) via Divide & Conquer

The Cooley-Tukey radix-2 FFT splits an N-point DFT into two (N/2)-point DFTs — one over the even indices, one over the odd:

// Iterative Cooley-Tukey FFT (in-place, N must be power of 2)
function fft(re, im) {          // re[], im[] are real and imaginary parts
  const N = re.length;
  // Bit-reversal permutation
  for (let i = 1, j = 0; i < N; i++) {
    let bit = N >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) { [re[i], re[j]] = [re[j], re[i]]; [im[i], im[j]] = [im[j], im[i]]; }
  }
  // Butterfly passes
  for (let len = 2; len <= N; len <<= 1) {
    const ang = -2 * Math.PI / len;
    const wRe = Math.cos(ang), wIm = Math.sin(ang);
    for (let i = 0; i < N; i += len) {
      let uRe = 1, uIm = 0;
      for (let j = 0; j < len / 2; j++) {
        const tRe = uRe * re[i+j+len/2] - uIm * im[i+j+len/2];
        const tIm = uRe * im[i+j+len/2] + uIm * re[i+j+len/2];
        re[i+j+len/2] = re[i+j] - tRe;  im[i+j+len/2] = im[i+j] - tIm;
        re[i+j] += tRe;                   im[i+j] += tIm;
        [uRe, uIm] = [uRe*wRe - uIm*wIm, uRe*wIm + uIm*wRe];
      }
    }
  }
}

4. Nyquist-Shannon Sampling Theorem

A bandlimited signal with maximum frequency f_max can be perfectly reconstructed from equally-spaced samples if and only if the sample rate f_s satisfies:

5. Standing Waves & Resonance

When a travelling wave reflects from a fixed boundary, the incident and reflected waves superpose to form a standing wave — nodes where displacement is always zero, antinodes where it is maximum. For a string of length L fixed at both ends, the allowed resonant frequencies are: f_n = n · v / (2L), where n = 1, 2, 3, … and v is the wave speed. This harmonic series is the physical basis of all string instruments.

Algorithms at a Glance