N不是2的幂次时用Numpy（Python）进行FFT

Question

我的问题是在Numpy的FFT函数中使用的算法。在

Numpy的文档说它使用Cooley-Tukey算法。然而，正如您所知，此算法仅在点数N是2的幂次方时有效。在

numpy是否填充了我的输入向量x[n]以计算其FFT x[k]？（我不这么认为，因为我在输出中的点数也是N）。我怎么能真正“看到”numpy用于其FFT函数的代码呢？在

干杯！在

Answer 1

根据我的经验，这些算法不会自动填充，或者至少有些算法没有希比。信号。希尔伯特方法对长度不等于2的幂的信号使用了大约45秒。当我自己用0填充信号到这样的长度时，花了100毫秒

但这是一个反复检查的东西，基本上任何时候你运行一个信号处理算法。在

Answer 2

文档说numpy的FFT基于FFTPACK。在

在FFTPACK文档中，我发现了以下内容：

---

subroutine rffti(n,wsave)

---

subroutine rffti initializes the array wsave which is used in both rfftf and rfftb. the prime factorization of n together with a tabulation of the trigonometric functions are computed and stored in wsave.

标准的Cooley-Tukey算法是“具有时间抽取的基数-2”，它递归地将大小为2*n的FFT的计算减少为2个大小为n的FFT，加上大小为2的FFT。同一算法有一个通用的因式分解版本，它将一个大小为m*n的FFT转换成n个大小为m的FFT加上m个大小为n的FFT。FFTPACK中的准备例程计算输入大小的素数因式分解这一事实似乎表明了他们正在做的事情。所以除非你用质数的元素，或者你的元素数有一个非常大的质数因子，你仍然可以得到一个很好的加速。在

几年前，我写了一篇关于cooleytukey算法的radix-2和general factorization版本的博客。阅读这些可能有助于理解纽比内部发生了什么。下面的图片是从那里拍摄的，描述了CT FFT：