fft js实现

FFT 的 JavaScript 实现

快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）的算法。以下是一个基于 Cooley-Tukey 算法的递归实现：

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

  // 分离偶数和奇数部分
  const even = [];
  const odd = [];
  for (let i = 0; i < N; i += 2) {
    even.push(signal[i]);
    odd.push(signal[i + 1]);
  }

  // 递归计算
  const evenTransformed = fft(even);
  const oddTransformed = fft(odd);

  // 合并结果
  const result = new Array(N);
  for (let k = 0; k < N / 2; k++) {
    const angle = -2 * Math.PI * k / N;
    const exp = {
      re: Math.cos(angle),
      im: Math.sin(angle)
    };

    // 复数乘法
    const oddTerm = {
      re: exp.re * oddTransformed[k].re - exp.im * oddTransformed[k].im,
      im: exp.re * oddTransformed[k].im + exp.im * oddTransformed[k].re
    };

    result[k] = {
      re: evenTransformed[k].re + oddTerm.re,
      im: evenTransformed[k].im + oddTerm.im
    };
    result[k + N/2] = {
      re: evenTransformed[k].re - oddTerm.re,
      im: evenTransformed[k].im - oddTerm.im
    };
  }
  return result;
}

使用示例

// 输入信号（复数形式）
const signal = [
  {re: 1, im: 0},
  {re: 1, im: 0},
  {re: 1, im: 0},
  {re: 1, im: 0},
  {re: 0, im: 0},
  {re: 0, im: 0},
  {re: 0, im: 0},
  {re: 0, im: 0}
];

// 计算FFT
const spectrum = fft(signal);
console.log(spectrum);

优化版本（迭代实现）

递归实现虽然直观，但效率较低。以下是更高效的迭代实现：

function fftIterative(signal) {
  const N = signal.length;
  let result = [...signal];

  // 位反转重排
  for (let i = 0, j = 0; i < N; i++) {
    if (i < j) {
      [result[i], result[j]] = [result[j], result[i]];
    }
    let m = N >> 1;
    while (m >= 1 && j >= m) {
      j -= m;
      m >>= 1;
    }
    j += m;
  }

  // 蝶形运算
  for (let s = 1; s <= Math.log2(N); s++) {
    const m = 1 << s;
    const wm = {
      re: Math.cos(-2 * Math.PI / m),
      im: Math.sin(-2 * Math.PI / m)
    };

    for (let k = 0; k < N; k += m) {
      let w = {re: 1, im: 0};
      for (let j = 0; j < m / 2; j++) {
        const t = {
          re: w.re * result[k + j + m/2].re - w.im * result[k + j + m/2].im,
          im: w.re * result[k + j + m/2].im + w.im * result[k + j + m/2].re
        };
        const u = result[k + j];
        result[k + j] = {
          re: u.re + t.re,
          im: u.im + t.im
        };
        result[k + j + m/2] = {
          re: u.re - t.re,
          im: u.im - t.im
        };
        w = {
          re: w.re * wm.re - w.im * wm.im,
          im: w.re * wm.im + w.im * wm.re
        };
      }
    }
  }
  return result;
}

性能注意事项

1. 输入信号长度应为 2 的幂次方，如果不是，需要补零
2. 对于大型信号，考虑使用 WebAssembly 或 GPU 加速
3. 实际应用中可能需要添加窗函数以减少频谱泄漏

逆 FFT 实现

逆 FFT 可以通过简单修改 FFT 实现得到：

function ifft(spectrum) {
  const N = spectrum.length;
  // 取共轭
  const conjugated = spectrum.map(bin => ({
    re: bin.re,
    im: -bin.im
  }));

  // 计算FFT
  const result = fft(conjugated);

  // 取共轭并缩放
  return result.map(bin => ({
    re: bin.re / N,
    im: -bin.im / N
  }));
}