如何通过N/2点复-复FFT实现N点实-复FFT

我知道可以通过N/2点复-复FFT实现N点实-复FFT，但找不到具体实现示例。以下是我的尝试代码，但运行结果不正确：

function realFFT(real) {
    const n = real.length;
    const halfN = n / 2;

    const complexReal = new Array(halfN);
    const complexImag = new Array(halfN);

    for (let i = 0; i < halfN; i++) {
        complexReal[i] = real[2 * i];
        complexImag[i] = real[2 * i + 1]
    }

    complexFFT(complexReal, complexImag);

    const resultReal = new Array(n);
    const resultImag = new Array(n);

    for (let i = 0; i < halfN; i++) {
        const angle = -2 * Math.PI * i / n;
        const cosAngle = Math.cos(angle);
        const sinAngle = Math.sin(angle);

        resultReal[i] = complexReal[i];
        resultImag[i] = complexImag[i];
        resultReal[n - i - 1] = complexReal[i] * cosAngle + complexImag[i] * sinAngle;
        resultImag[n - i - 1] = -complexReal[i] * sinAngle + complexImag[i] * cosAngle;
    }

    return [resultReal, resultImag];
}

错误分析 #

你的代码核心问题在于利用复FFT结果推导实FFT时的公式错误，没有正确应用实序列FFT的共轭对称性和旋转因子。实序列的FFT满足X[N-k] = conjugate(X[k])，需要基于这个特性结合N/2点复FFT的结果来推导完整的N点FFT。

修正后的实现 #

function realFFT(real) {
    const n = real.length;
    const halfN = n / 2;

    // 构造N/2点复序列：实部为原序列的偶索引元素，虚部为奇索引元素
    const yReal = new Array(halfN);
    const yImag = new Array(halfN);
    for (let i = 0; i < halfN; i++) {
        yReal[i] = real[2 * i];
        yImag[i] = real[2 * i + 1];
    }

    // 执行N/2点复FFT（确保complexFFT是正确的基2正向FFT实现）
    complexFFT(yReal, yImag);

    const xReal = new Array(n);
    const xImag = new Array(n);

    // 遍历计算前半部分FFT结果，利用共轭对称性得到后半部分
    for (let k = 0; k < halfN; k++) {
        // 旋转因子 W_N^k = cos(2πk/N) - j*sin(2πk/N)
        const angle = 2 * Math.PI * k / n;
        const cosW = Math.cos(angle);
        const sinW = Math.sin(angle);

        // 计算Y[(halfN - k) mod halfN]的共轭
        const m = (halfN - k) % halfN;
        const conjYReal = yReal[m];
        const conjYImag = -yImag[m];

        // 计算W_N^k * conj(Y[m])
        const tempReal = cosW * conjYReal - sinW * conjYImag;
        const tempImag = cosW * conjYImag + sinW * conjYReal;

        // 得到X[k] = Y[k] + W_N^k * conj(Y[m])
        xReal[k] = yReal[k] + tempReal;
        xImag[k] = yImag[k] + tempImag;

        // 利用共轭对称性填充X[n - k]
        xReal[n - k] = xReal[k];
        xImag[n - k] = -xImag[k];
    }

    // 处理k=halfN的特殊情况：X[halfN]是实数，虚部为0
    xReal[halfN] = yReal[0] - yImag[0];
    xImag[halfN] = 0;

    return [xReal, xImag];
}

关键说明 #

• 确保complexFFT是正向基2复FFT实现，如果你的complexFFT是逆FFT，需要调整旋转因子的符号（将angle = 2 * Math.PI * k / n改为angle = -2 * Math.PI * k / n）。
• 这个实现仅适用于N为2的幂的情况（基2FFT的要求）。
• 共轭对称性的应用是核心：实序列的FFT结果关于N/2点共轭对称，因此只需计算前半部分，后半部分通过共轭直接得到。

内容的提问来源于stack exchange，提问作者Chris_F