当前位置：首页 > JavaScript

js实现FFT

2026-04-06 19:57:21JavaScript

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));
}