Python实现FFT算法输出与NumPy参考值不符的排查求助
FFT实现问题定位与调试指引
核心问题排查
- 旋转因子符号与通用FFT约定不匹配
NumPy及标准Cooley-Tukey FFT定义的旋转因子为 $W_n^k = e^{-j\frac{2\pi k}{n}}$,你当前代码中w_n = np.exp(complex(0,2*np.pi/n))使用了正指数形式,等价于计算逆FFT的旋转因子,直接导致所有输出的虚部符号完全颠倒。对应你给出的测试现象:输入[1,2,3,4]时自实现结果的-2-2j对应NumPy的-2+2j,输入[1,4,4,0]时自实现的-3+4j对应NumPy的-3-4j,和虚部符号反转的特征完全吻合。 - 顶层长度计算逻辑错误,导致非2幂序列计算截断
你在FFT函数入口直接取原始输入长度作为计算用的n值,但实际序列补零操作是在decomp函数内部完成的:比如输入长度为3的序列,decomp会自动把序列补到4个元素再做奇偶拆分,但FFT函数顶层的n值仍然是3,后续循环只执行range(int(n/2))也就是1次迭代,最终拼接出的结果长度仅为2,直接丢失两个频点的计算结果,出现输入[1,2,3]仅输出[6,2]的异常。 - 递归层冗余补零引发的长度不匹配
每次调用decomp时都重新计算当前序列长度的最近2的幂并补零,但递归FFT的正常流程是:仅在函数最入口一次性把原始输入补到全局长度为N(满足2^m ≥ 输入长度)的2的幂长度,后续每一层递归的子序列长度自然是N/2、N/4……,不需要每层重复做补零计算,否则会进一步加剧长度不匹配的问题。 - 强制取整逻辑覆盖复数结果
代码最后直接用np.around(A_star)转成整数列表,会把小幅值的虚部直接抹除,进一步放大结果偏差。
修正后的参考实现
import numpy as np def cpo2(x, y): # 保持原有功能:返回max(x,y)向上取整的最近2的幂 m = max(x, y) n = 1 while n < m: n *= 2 return n def fill(A, n): # 保持原有功能:在列表末尾补零到指定长度 return A + [0j] * (n - len(A)) def recursive_fft(A): n = len(A) if n == 1: return A # 修正旋转因子为负指数,匹配NumPy FFT约定 w_n = np.exp(complex(0, -2 * np.pi / n)) w = 1 # 直接在传入的等长子序列上做奇偶拆分,不再重复补零 A0 = A[0::2] A1 = A[1::2] A0_star = recursive_fft(A0) A1_star = recursive_fft(A1) A_star0 = [] A_star1 = [] for k in range(n // 2): A_star0.append(A0_star[k] + w * A1_star[k]) A_star1.append(A0_star[k] - w * A1_star[k]) w = w * w_n return A_star0 + A_star1 def FFT(A): # 函数入口统一完成补零操作 target_len = cpo2(len(A), len(A)) A_padded = fill([complex(x) for x in A], target_len) return np.array(recursive_fft(A_padded))
修正后验证效果
- 输入
[1,2]时输出[3+0j, -1+0j],与NumPy结果一致 - 输入
[1,2,3,4]时输出[10+0j, -2+2j, -2+0j, -2-2j],与NumPy参考值完全匹配 - 输入
[1,2,3]时自动补零到4点计算,输出长度为4的正确FFT结果,与NumPy对短序列自动补零的计算逻辑一致 - 输入
[1,4,4,0]时输出[9+0j, -3-4j, 1+0j, -3+4j],与NumPy参考值完全匹配
内容的提问来源于stack exchange,提问作者Othmane lakhdar
相关产品推荐
相关产品推荐

