经过一番研究，我创建了一个小应用程序，可以根据一些输入计算 DFT（离散傅里叶变换）。它工作得很好，但速度很慢。
我读到 FFT（快速傅立叶变换）允许更快的计算，但它们有何不同？更重要的是，我将如何在 C++ 中实现它们？
问问题
422 次
5 回答
4
如果你不需要手动实现算法，你可以看看西方最快的傅里叶变换
即使认为它是用 C 开发的，它也可以在 C++ 中正式运行（来自常见问题解答）
问题 2.9。我可以从 C++ 调用 FFTW 吗？
明确地。FFTW 应该在任何 C++ 编译器下编译和/或链接。此外，C++ 模板类很可能与 FFTW 的复数格式位兼容（有关详细信息，请参阅 FFTW 手册）。
于 2010-04-03T22:31:51.423 回答
3
与具有 n^2 的 DFT 相比，FFT 具有 n*log(n) 的复杂性。
有很多关于这方面的文献，我强烈建议你先检查一下，因为如此广泛的话题在这里无法完整解释。 http://en.wikipedia.org/wiki/Fast_Fourier_transform（检查外部链接）
例如，如果您需要图书馆，我建议您使用现有的图书馆。 http://www.fftw.org/ 该库有效地实现了 FFT，也用于专有软件（例如 MATLAB）
于 2010-04-03T22:39:05.260 回答
1
Steven Smith 的书The Scientist and Engineer's Guide to Digital Signal Processing，特别是关于 DFT 的第 8 章和关于 FFT 的第12 章，在解释我曾经做过的两种变换方面做得更好。
顺便说一句，整本书都是免费的（上面的链接），它是对信号处理的一个很好的介绍。
关于 C++ 代码请求，我只使用了西方最快的傅立叶变换（superexsl 已经引用）或 TI 或 Analog Devices 等 DSP 库。
于 2010-04-04T02:39:43.263 回答
1
正确实现的 DFT 的结果与正确实现的 FFT 的结果基本相同（它们的区别仅在于舍入误差）。正如其他人在这里指出的那样，主要区别在于性能。DFT 有 O(n^2) 次运算，而 FFT 有 O(nlogn) 次运算。
我发现的最好的、最易读的出版物（我仍然参考的那个）是E Oran Brigham的《快速傅里叶变换及其应用》。前几章对傅里叶变换的连续和离散形式进行了非常全面的概述。然后，他使用它来开发基于Cooley-Tukey 算法的快速版本的 DFT，用于基数 2（n 是 2 的幂）和混合基数情况（尽管后者比前者更浅一些） .
radix-2 算法中对输入 X 执行线性时间运算并递归地将结果分成两半并对两半执行相似的线性时间运算的基本方法。混合基数的情况类似，尽管您每次都需要将 X 分成相等的部分，因此如果 n 没有任何大的素因数，它会有所帮助。
于 2010-04-04T03:58:01.850 回答
0
我发现了这个很好的解释，其中描述了一些算法。
关于实施，
- 首先，我会确保您的实现返回正确的结果（比较 matlab 或 octave 的输出 - 内置傅立叶变换）
- 必要时进行优化，使用分析器
- 不要使用不必要的 for 循环
于 2010-04-03T22:35:46.853 回答