js实现FFT
JavaScript 实现 FFT（快速傅里叶变换）
快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）的算法。以下是一个基于 Cooley-Tukey 算法的 JavaScript 实现，适用于长度为 2 的幂的输入序列。
复数类辅助实现
FFT 涉及复数运算，需先定义复数类及基本运算方法：
class Complex {
constructor(real, imag = 0) {
this.re = real;
this.im = imag;
}
add(other) {
return new Complex(this.re + other.re, this.im + other.im);
}
subtract(other) {
return new Complex(this.re - other.re, this.im - other.im);
}
multiply(other) {
return new Complex(
this.re * other.re - this.im * other.im,
this.re * other.im + this.im * other.re
);
}
magnitude() {
return Math.sqrt(this.re 2 + this.im 2);
}
}FFT 核心算法
递归实现 Cooley-Tukey 算法：
function fft(input) {
const N = input.length;
if (N === 1) return input;
// 确保输入长度为 2 的幂
if (Math.log2(N) % 1 !== 0) {
throw new Error("Input length must be a power of 2.");
}
// 分离偶数和奇数索引
const even = [];
const odd = [];
for (let i = 0; i < N; i += 2) {
even.push(input[i]);
odd.push(input[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 exp = new Complex(Math.cos(angle), Math.sin(angle));
const term = oddTransformed[k].multiply(exp);
output[k] = evenTransformed[k].add(term);
output[k + N / 2] = evenTransformed[k].subtract(term);
}
return output;
}使用示例
计算实数信号的频谱：
// 输入信号（示例：8 个采样点）
const signal = [1, 1, 1, 1, 0, 0, 0, 0].map(x => new Complex(x));
// 执行 FFT
const spectrum = fft(signal);
// 计算幅度谱
const magnitudes = spectrum.map(c => c.magnitude());
console.log(magnitudes); // 输出频域幅度注意事项
- 输入长度：必须为 2 的幂（如 256、512），否则需补零。
- 性能优化：递归实现适合教学，实际应用建议用迭代版（如位反转置换）。
- 逆变换：实现 IFFT 只需调整角度符号并除以 N：
function ifft(input) {
const N = input.length;
const conjugated = input.map(c => new Complex(c.re, -c.im));
const transformed = fft(conjugated);
return transformed.map(c => new Complex(c.re / N, -c.im / N));
}现成库推荐
生产环境建议使用成熟库：
