非2的幂长度输入的FFT零填充问题：为何与Numpy结果不符？

我正在用Python实现快速傅里叶变换（FFT），处理长度非2的幂的输入数据时遇到问题。我尝试用零填充将输入补至最近的2的幂长度，但结果和Numpy的标准实现差异很大。

我的FFT实现代码 #

import numpy as np

def myfft(x):
    N = len(x)
    if N <= 1:
        return x
    evens = myfft(x[0::2])
    odds = myfft(x[1::2])
    t = np.exp(-2j * np.pi * np.arange(N) / N)
    f = np.concatenate([evens + t[:N//2] * odds,
                        evens + t[N//2:] * odds])
    return f

测试结果对比 #

当输入长度为2的幂时，我的实现和numpy.fft.fft()结果一致，但零填充后的输入结果差异明显：

output1 = np.fft.fft([1,2,3,4,5,6,7])
output2 = myfft([1,2,3,4,5,6,7,0])

# output1:
[28  -3.5+7.3j -3.5+2.8j -3.5+0.8j -3.5-0.8j -3.5-2.8j -3.5-7.3j]
# output2:
[28  -9.7+4j   -4-4j      1.7-4j    4         1.7+4j   -4+4j     -9.7-4j]

问题 #

请问零填充是否是处理非2的幂长度输入FFT的可行方法？若是，正确的实现方式是什么？

零填充的可行性 #

零填充是处理非2的幂输入的可行方法，但它本质上是对原始信号做频谱插值，而非直接计算原始长度N的FFT。你得到的差异核心原因是：

• np.fft.fft([1,2,3,4,5,6,7])计算的是7点FFT，对应7个原始频率点；
• 你的myfft计算的是8点FFT，对应8个经过插值的频率点，两者的采样频率点完全不同，结果自然无法直接对应。

正确的处理方式 #

如果想用零填充配合基2FFT实现和Numpy逻辑一致的结果，需要注意两点：

1. 明确零填充的作用：原始N点信号x的M点零填充FFT（M>N），等价于对原始N点FFT的频谱做插值。你可以通过对Numpy的7点FFT结果做插值，得到和8点零填充FFT对应的结果，反之亦然。
2. 若要计算原始长度的FFT：基2FFT只支持长度为2的幂的输入，若要直接计算非2的幂长度的FFT，需要实现混合基FFT（比如Cooley-Tukey算法的通用版本），或者先零填充到2的幂后，再通过插值映射回原始长度的频率点。

验证你的实现正确性 #

如果你想验证零填充后的FFT是否正确，应该对比相同长度的结果：

# 用Numpy做零填充后的8点FFT
output_numpy_padded = np.fft.fft([1,2,3,4,5,6,7,0])
# 你的myfft的8点结果
output_my_padded = myfft([1,2,3,4,5,6,7,0])

这两个结果应该完全一致，说明你的基2FFT实现本身是正确的，之前的差异只是因为你错误对比了不同长度的FFT输出。

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