43.1 FFT Fundamentals

The Discrete Fourier Transform (DFT) converts time‑domain samples to frequency bins. FFT algorithms reduce O(N²) complexity to O(N log N).

43.1.1 DFT Definition

For N samples x[n], the DFT is:

X[k] = Σ(n=0 to N-1) x[n] · exp(-2πi·kn/N)

k = frequency bin, n = time index.

43.1.2 Complex Number Representation

Store complex as interleaved floats: [re0, im0, re1, im1, ...]

class Complex {
  static void mul(float[] a, int ia, float[] b, int ib, float[] c, int ic) {
    float are = a[ia], aim = a[ia+1];
    float bre = b[ib], bim = b[ib+1];
    c[ic]   = are*bre - aim*bim;
    c[ic+1] = are*bim + aim*bre;
  }
  static void add(float[] a, int ia, float[] b, int ib, float[] c, int ic) {
    c[ic]   = a[ia]   + b[ib];
    c[ic+1] = a[ia+1] + b[ib+1];
  }
  static void sub(float[] a, int ia, float[] b, int ib, float[] c, int ic) {
    c[ic]   = a[ia]   - b[ib];
    c[ic+1] = a[ia+1] - b[ib+1];
  }
}

43.1.3 Naive DFT (O(N²))

void dftNaive(float[] x, float[] X, int N) {
  for (int k = 0; k < N; k++) {
    float re = 0f, im = 0f;
    for (int n = 0; n < N; n++) {
      float angle = -2f * (float)Math.PI * k * n / N;
      float cos = (float)Math.cos(angle);
      float sin = (float)Math.sin(angle);
      re += x[2*n]   * cos - x[2*n+1] * sin;
      im += x[2*n]   * sin + x[2*n+1] * cos;
    }
    X[2*k] = re; X[2*k+1] = im;
  }
}

43.1.4 FFT Complexity Insight

Cooley–Tukey recursively splits DFT into even/odd halves, yielding O(N log N) via divide‑and‑conquer.