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 output = new Array(N);
  for (let k = 0; k < N / 2; k++) {
    const angle = -2 * Math.PI * k / N;
    const twiddle = {
      re: Math.cos(angle),
      im: Math.sin(angle)
    };

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

    // 复数加法
    output[k] = {
      re: evenTransformed[k].re + oddTerm.re,
      im: evenTransformed[k].im + oddTerm.im
    };

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

  return output;
}

使用示例

// 输入信号（复数形式）
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);

优化建议

对于生产环境使用，建议考虑以下优化措施：

• 使用迭代实现代替递归以减少调用开销
• 预计算旋转因子（twiddle factors）
• 使用TypedArray提高数值计算性能
• 实现逆FFT（IFFT）功能

现有库推荐

如果需要更成熟的解决方案，可以考虑以下JavaScript库：

1. math.js：提供全面的数学计算功能，包括FFT
2. dsp.js：专注于数字信号处理的库
3. fft-js：轻量级的FFT实现

这些库通常经过优化，支持更大的输入尺寸和更高效的计算。