fft js实现
FFT（快速傅里叶变换）的 JavaScript 实现
快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）的算法。以下是基于 Cooley-Tukey 算法的递归实现，适用于长度为 2 的幂次的输入。
递归实现
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).fill(0).map((_, k) => {
const angle = -2 * Math.PI * k / N;
const exp = { re: Math.cos(angle), im: Math.sin(angle) };
const term = {
re: exp.re * odd[k % (N/2)].re - exp.im * odd[k % (N/2)].im,
im: exp.re * odd[k % (N/2)].im + exp.im * odd[k % (N/2)].re
};
return {
re: even[k % (N/2)].re + term.re,
im: even[k % (N/2)].im + term.im
};
});
return result;
}非递归优化实现
递归实现虽然直观，但性能较差。以下是基于迭代的非递归实现：
function fftIterative(input) {
const N = input.length;
const log2N = Math.log2(N);
const output = input.map((val, i) => ({ re: val, im: 0 }));
for (let s = 1; s <= log2N; 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 * output[k + j + m/2].re - w.im * output[k + j + m/2].im,
im: w.re * output[k + j + m/2].im + w.im * output[k + j + m/2].re
};
const u = output[k + j];
output[k + j] = { re: u.re + t.re, im: u.im + t.im };
output[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 output;
}使用示例
const signal = [1, 1, 1, 1, 0, 0, 0, 0]; // 长度为 8 的示例信号（2^3）
const spectrum = fftIterative(signal);
console.log(spectrum.map(c => `${c.re.toFixed(2)} + ${c.im.toFixed(2)}i`));注意事项
- 输入信号长度必须是 2 的幂次（如 2, 4, 8, 16 等），否则需要补零。
- 输出结果为复数数组，包含实部（
re）和虚部（im）。 - 如需逆变换（IFFT），可将旋转因子的角度符号取反，并最终除以 N。
性能优化建议
- 预处理旋转因子（twiddle factors）以减少重复计算。
- 使用 TypedArray（如 Float32Array）替代普通数组提升性能。
- 对于大规模数据，考虑 WebAssembly 或 GPU 加速（如 WebGL）。
