递归IFFT实现中的缩放错误：原因排查与修复方案

我用C++实现了一个递归FFT/IFFT，正向FFT运行正常，但逆IFFT的输出存在缩放错误——8点FFT的逆变换结果是原始数据的1/8，无法正确还原。

实现代码 #

FFT与IFFT实现 #

#include <complex>
#include <numbers>
#include <ranges>
#include <valarray>
#include <vector>

#include "assert.hpp"

template<typename T = float>
std::valarray<std::complex<T>> fft(std::valarray<std::complex<T>> const& data)
{
    const auto N = data.size();
    ASSERT(!(N & (N - 1)), "FFT length has to be power of two");

    if (N == 1)
        return data;

    auto even = fft(data[std::slice(0, N / 2, 2)]);
    auto odd = fft(data[std::slice(1, N / 2, 2)]);

    auto result = std::valarray<std::complex<T>>(N);
    for (size_t k = 0; k < N / 2; ++k)
    {
        auto t = std::exp(std::complex<T>(0, -2 * std::numbers::pi * T(k) / N));
        result[k] = even[k] + odd[k] * t;
        result[k + N / 2] = even[k] - odd[k] * t;
    }

    return result;
}

template<typename T = float>
std::valarray<std::complex<T>> ifft(std::valarray<std::complex<T>> const& data)
{
    const auto N = data.size();
    ASSERT(!(N & (N - 1)), "FFT length has to be power of two");

    if (N == 1)
        return data;

    auto even = ifft(data[std::slice(0, N / 2, 2)]);
    auto odd = ifft(data[std::slice(1, N / 2, 2)]);

    auto result = std::valarray<std::complex<T>>(N);
    for (size_t k = 0; k < N / 2; ++k)
    {
        auto t = std::exp(std::complex<T>(0, 2 * std::numbers::pi * T(k) / N));
        result[k] = (even[k] + odd[k] * t) / T(N);
        result[k + N / 2] = (even[k] - odd[k] * t) / T(N);
    }

    return result;
}

测试代码 #

std::valarray<std::complex<float>> data = { 3, 5, 8, 9, 1, 4, 7, 2 };

std::cout << "Data: ";
for (auto const& e : data)
    std::cout << e << " ";
std::cout << "\n";

auto spectrum = fft(data);

std::cout << "Forward FFT: ";
for (auto const& e : spectrum)
    std::cout << e << " ";
std::cout << "\n";

std::cout << "Inverse FFT: ";
auto inverse = ifft(spectrum);
for (auto const& e : inverse)
    std::cout << e << " ";
std::cout << "\n";

运行输出 #

Data: (3,0) (5,0) (8,0) (9,0) (1,0) (4,0) (7,0) (2,0) 
Forward FFT: (39,0) (-2.24264,-6.65685) (-11,2) (6.24264,-4.65685) (-1,0) (6.24264,4.65685) (-11,-2) (-2.24264,6.65685) 
Inverse FFT: (0.375,0) (0.625,6.58126e-09) (1,2.73196e-09) (1.125,-1.21692e-08) (0.125,0) (0.5,-1.20452e-08) (0.875,-2.73196e-09) (0.25,1.76331e-08)

问题原因 #

标准逆FFT的总缩放因子应为1/N（对应离散傅里叶逆变换的定义），但当前IFFT实现错误地在每一层递归的组合步骤都除以当前序列长度N，导致总缩放过度：

• 对于8点序列，递归分为3层（8→4→2），总缩放因子为1/(8*4*2)=1/64
• 正向FFT的结果X[k]经过逆变换后本应得到N*x[n]，当前代码额外多除以了8，最终结果变为x[n]/8

修复方案 #

方案一：仅在递归结束后整体缩放 #

将缩放操作移到递归的最后一步，只对最终结果整体除以总长度N：

template<typename T = float>
std::valarray<std::complex<T>> ifft(std::valarray<std::complex<T>> const& data)
{
    const auto N = data.size();
    ASSERT(!(N & (N - 1)), "FFT length has to be power of two");

    if (N == 1)
        return data;

    auto even = ifft(data[std::slice(0, N / 2, 2)]);
    auto odd = ifft(data[std::slice(1, N / 2, 2)]);

    auto result = std::valarray<std::complex<T>>(N);
    for (size_t k = 0; k < N / 2; ++k)
    {
        auto t = std::exp(std::complex<T>(0, 2 * std::numbers::pi * T(k) / N));
        result[k] = even[k] + odd[k] * t;
        result[k + N / 2] = even[k] - odd[k] * t;
    }

    // 仅在最后一步整体除以总长度N
    return result / T(N);
}

方案二：分层缩放（每一层除以2） #

将总缩放因子1/N分解到每一层递归中，每一层组合时除以2（因为每一层将N点序列拆分为两个N/2点序列，总层数为log2(N)，(1/2)^log2(N)=1/N）：

template<typename T = float>
std::valarray<std::complex<T>> ifft(std::valarray<std::complex<T>> const& data)
{
    const auto N = data.size();
    ASSERT(!(N & (N - 1)), "FFT length has to be power of two");

    if (N == 1)
        return data;

    auto even = ifft(data[std::slice(0, N / 2, 2)]);
    auto odd = ifft(data[std::slice(1, N / 2, 2)]);

    auto result = std::valarray<std::complex<T>>(N);
    const T scale = T(0.5); // 每一层缩放1/2
    for (size_t k = 0; k < N / 2; ++k)
    {
        auto t = std::exp(std::complex<T>(0, 2 * std::numbers::pi * T(k) / N));
        result[k] = (even[k] + odd[k] * t) * scale;
        result[k + N / 2] = (even[k] - odd[k] * t) * scale;
    }

    return result;
}

两种方案都能让逆FFT正确还原原始数据，修复缩放错误。

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