js实现FFT
FFT 算法实现
快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）的算法。以下是使用 JavaScript 实现 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 = 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)).multiply(odd[k]);
output[k] = even[k].add(exp);
output[k + N / 2] = even[k].subtract(exp);
}
return output;
}
class Complex {
constructor(real, imaginary) {
this.real = real;
this.imaginary = imaginary;
}
add(other) {
return new Complex(this.real + other.real, this.imaginary + other.imaginary);
}
subtract(other) {
return new Complex(this.real - other.real, this.imaginary - other.imaginary);
}
multiply(other) {
return new Complex(
this.real * other.real - this.imaginary * other.imaginary,
this.real * other.imaginary + this.imaginary * other.real
);
}
}使用说明
输入数据应为复数数组，实部和虚部都需要提供。如果输入是实数信号，可以将虚部设为0：
const realSignal = [1, 2, 3, 4];
const complexInput = realSignal.map(x => new Complex(x, 0));
const spectrum = fft(complexInput);性能优化
对于实际应用，可以考虑以下优化措施：
- 预计算旋转因子（twiddle factors）
- 使用迭代而非递归实现
- 采用位反转排列优化内存访问模式
- 考虑使用WebAssembly或GPU加速计算密集型部分
应用示例
计算信号的幅度谱：
function magnitudeSpectrum(fftOutput) {
return fftOutput.map(c => Math.sqrt(c.real * c.real + c.imaginary * c.imaginary));
}注意事项
- 输入长度应为2的幂次方，否则需要补零
- 浮点数精度可能导致计算误差
- 对于实时应用，需要考虑算法延迟和计算效率
