js实现FFT
FFT算法基础
快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的高效算法，用于将时域信号转换为频域表示。Cooley-Tukey算法是最常见的递归分治实现，时间复杂度为O(n log n)。
JavaScript实现步骤
复数类定义 处理FFT需要复数运算，先定义基础复数操作：
class Complex {
constructor(re = 0, im = 0) {
this.re = re;
this.im = im;
}
add(other) {
return new Complex(this.re + other.re, this.im + other.im);
}
sub(other) {
return new Complex(this.re - other.re, this.im - other.im);
}
mul(other) {
return new Complex(
this.re * other.re - this.im * other.im,
this.re * other.im + this.im * other.re
);
}
}递归FFT实现
function fft(input) {
const N = input.length;
if (N <= 1) return input;
// 分奇偶项
const even = fft(input.filter((_, i) => i % 2 === 0));
const odd = fft(input.filter((_, i) => i % 2 === 1));
// 合并结果
const output = Array(N).fill(new Complex());
for (let k = 0; k < N / 2; k++) {
const t = odd[k].mul(
new Complex(
Math.cos(-2 * Math.PI * k / N),
Math.sin(-2 * Math.PI * k / N)
)
);
output[k] = even[k].add(t);
output[k + N/2] = even[k].sub(t);
}
return output;
}使用示例
// 输入信号（需转换为复数形式）
const signal = [1, 1, 1, 1, 0, 0, 0, 0].map(x => new Complex(x));
const spectrum = fft(signal);
// 输出频域幅度
const magnitudes = spectrum.map(c => Math.sqrt(c.re2 + c.im2));
console.log(magnitudes); // 输出各频率分量幅度性能优化建议
对于生产环境使用，建议：
- 使用迭代而非递归实现减少调用开销
- 预计算旋转因子（twiddle factors）
- 考虑WebAssembly版实现（如FFTW.js）
- 注意输入长度必须是2的幂次
现成库推荐
如需直接应用，推荐以下成熟库：
- math.js：包含完整的FFT实现
- dsp.js：专攻数字信号处理的库
- FFT.js：轻量级专用实现
以上实现展示了FFT的核心原理，实际应用中需根据具体场景调整窗函数、零填充等参数。
