n 点的 FFT（非 2 的幂）

Question

我需要知道一种方法，使 FFT (DFT) 仅适用于 n 个点，其中 n 不是 2 的幂。

我想分析修改后的声谱，特别是 Wave 文件，它们共有 44100 个采样点。但我的 FFT 不起作用，它只适用于形状如 2^n 的点。

那我能做什么呢？除了用零填充向量的 2 的下一个幂？！有什么办法可以修改FFT算法吗？

谢谢！

Answer 1

除了按照您的建议填充数组或使用其他一些库函数之外，您还可以在频域中构造具有任意长度和间距的傅立叶变换（也适用于非整数样本间距）。

这是众所周知的结果，基于 Chirp-z 变换（或 Bluestein 的 FFT）。Rabiner 提供了另一个很好的参考资料，可以在上面的链接中找到。

总之，通过这种方法，您不必自己编写 FFT，您可以简单地使用现有的高性能 FFT，然后将卷积定理应用于适当缩放和调节的信号版本。

性能仍然是 O(n*log n) 乘以一些与实现相关的缩放因子。