傅里叶变换：从时域到频域的优雅桥梁

一个改变世界的数学发现

傅里叶变换（Fourier Transform）是 19 世纪数学家傅里叶提出的核心思想：任何连续的周期信号都可以表示为正弦波的叠加。这个看似简单的结论，却构成了现代信号处理、图像压缩、音频分析的基石。

从欧拉公式出发

傅里叶变换的优雅源于欧拉公式：

e^(iωt) = cos(ωt) + i·sin(ωt)

这意味着复指数可以同时编码正弦和余弦分量。连续傅里叶变换定义为：

F(ω) = ∫ f(t) · e^(-iωt) dt

它将时域函数 f(t) 转换为频域函数 F(ω)，告诉你信号在每个频率处的振幅和相位。

离散傅里叶变换 (DFT)

在计算机中我们处理离散信号，DFT 公式为：

X[k] = Σ x[n] · e^(-i2πkn/N),  k = 0, 1, ..., N-1

直接计算 DFT 的时间复杂度是 O(N²)，对于 N=1024 的信号就需要百万次运算。

JavaScript 实现 DFT

function dft(signal) {
  const N = signal.length;
  const result = [];
  for (let k = 0; k < N; k++) {
    let re = 0, im = 0;
    for (let n = 0; n < N; n++) {
      const phi = -2 * Math.PI * k * n / N;
      re += signal[n] * Math.cos(phi);
      im += signal[n] * Math.sin(phi);
    }
    result.push({ re, im, mag: Math.sqrt(re*re + im*im) });
  }
  return result;
}

快速傅里叶变换 (FFT)

FFT 利用分治思想将复杂度降到 O(N log N)。核心观察：e^(-i2πkn/N) 具有周期性，可以分解为偶数项和奇数项：

X[k] = E[k] + W^k · O[k]
X[k + N/2] = E[k] - W^k · O[k]

其中 W = e^(-i2π/N) 是 N 次单位根，E[k] 是偶数项的 DFT，O[k] 是奇数项的 DFT。

递归 FFT 实现

function fft(signal) {
  const N = signal.length;
  if (N <= 1) return signal;

  const even = fft(signal.filter((_, i) => i % 2 === 0));
  const odd  = fft(signal.filter((_, i) => i % 2 === 1));

  const result = new Array(N);
  for (let k = 0; k < N / 2; k++) {
    const angle = -2 * Math.PI * k / N;
    const wr = Math.cos(angle);
    const wi = Math.sin(angle);

    const tr = wr * odd[k].re - wi * odd[k].im;
    const ti = wr * odd[k].im + wi * odd[k].re;
    result[k] = { re: even[k].re + tr, im: even[k].im + ti };
    result[k + N/2] = { re: even[k].re - tr, im: even[k].im - ti };
  }
  return result;
}

实际应用场景

• 音频频谱可视化：将音频信号做 FFT，绘制频率-振幅图
• JPEG 压缩：对图像块做 2D DCT（离散余弦变换），丢弃高频分量
• MP3 编码：利用人耳对频率的感知特性，压缩不敏感频段
• 雷达与通信：OFDM 正交频分复用依赖 FFT 实现

傅里叶变换告诉我们：看似复杂的信号，不过是简单正弦波的合唱。这正是数学抽象的力量。