FFT与DFT有什么不同，以及如何在C++中实现它们？

经过一番研究，我创建了一个小应用程序，可以根据某些输入计算DFT（离散傅立叶变换）。它运行得很好，但速度很慢。FFT与DFT有什么不同，以及如何在C++中实现它们？

我读到FFT（快速傅立叶变换）允许更快的计算，但它们有什么不同？更重要的是，我将如何着手在C++中实现它们？

来源

2010-04-03 Nathan Osman

FFT仅仅是一个参考算法，快速计算的DFT的方式;也就是说，FFT算法的结果应该与通过定义计算DFT的结果相同（或非常接近）。 – 2010-04-03 22:31:38

FFT只能在长度为2的样本上计算，DFT没有此限制。我没有看到任何人的答案，但这是你需要知道的事情，我不认为这是一个单独的答案。 – 2010-04-05 03:28:13

如果您不需要手动实现算法，你可以看看在Fastest Fourier Transform in the West

甚至认为在C发达，它正式工作在C++（从FAQ）

问题2.9。我可以从 C++调用FFTW吗？

绝对是。 FFTW应该在任何C++编译器下编译和/或链接。此外，C++ 模板类可能与FFTW的复数格式（请参阅FFTW 手册以获得更多详细信息）位兼容。

来源

2010-04-03 22:31:51 XSL

嗯......你提到的图书馆需要非商业用途的费用。 – 2010-04-03 22:45:42

对不起，不知道这是出于商业目的。在这种情况下，你可以尝试http://kissfft.sourceforge.net/。这使用BSD许可证 – XSL 2010-04-03 23:16:40

我发现这个很好的解释与一些算法描述。

FastFourierTransform

关于实施，

首先我会确保您的实现返回正确的结果（比较从MATLAB或倍频输出 - 这已经建立了傅立叶transformates）
优化时必要时使用分析器
不要使用不必要的循环

来源

2010-04-03 22:35:46 bua

与具有n^2的DFT相比，FFT具有n * log（n）强度。

有很多关于这方面的文献，我强烈建议您先检查一下，因为这样的广泛的主题不能在这里完整地解释。 http://en.wikipedia.org/wiki/Fast_Fourier_transform（检查外部链接）

如果您需要库，我建议您使用现有的库，例如。 http://www.fftw.org/ 这图书馆有效地执行FFT，并且也用在propariaretery软件（MATLAB例如）

来源

2010-04-03 22:39:05

史蒂芬·史密斯的书The Scientist and Engineer's Guide to Digital Signal Processing，特别是Chapter 8 on the DFT和Chapter 12 on the FFT，做了解释两个变换的一个更好的工作，我都做不到。

顺便说一句，整本书是免费的（上面的链接），这是一个非常好的信号处理介绍。

关于C++代码请求，我只使用西方最快的傅立叶变换（已经被superexsl引用）或DSP库（例如来自TI或ADI公司的DSP库）。

来源

2010-04-04 02:39:43 Dan

一个正确实现DFT的结果的正确实现FFT的结果（它们仅通过舍入错误不同）基本上相同。正如其他人在这里指出的，主要区别在于绩效。 DFT具有O（n^2）操作，而FFT具有O（nlogn）操作。

最好的，最可读的出版，我曾经发现（一个我仍然引用）是The Fast Fourier Transform and its Applications用E奥兰布里格姆。前几章提供了傅立叶变换的连续和离散形式的非常全面的概述。然后，他使用它来开发基于Cooley-Tukey Algorithm的基数为2的快速版本的DFT（n是2的幂）和混合基数的情况（虽然后者比前者更浅一些）。

在基数为2的算法的基本方法对输入X执行线性时间操作，并递归地划分结果一半，并在两个半部分执行类似的线性时间的操作。混合基数情况是相似的，但是每次需要将X分成相等的部分，所以如果n没有任何大的素因子，它会有所帮助。

来源

2010-04-04 03:58:01 andand

FFT与DFT有什么不同，以及如何在C++中实现它们？

回答

相关问题