然而,我发现每个我找到的都很差,无法解释正在发生的事情,或者注释不当;或者它们假定你已经知道FFT算法,或者它们是关于如何使用FFT的教程。
有人知道一个好的示例/教程吗?
抱歉没有超链接,我没有添加它们的权限 :(
您在这里要求两件事:
1)FFT的解释
简单地说:
如果您想获得信号的频域表示,则使用傅里叶变换,这是一种将信号从时间域转换为频率域的数学变换。当操作数字信号时,我们有一组离散样本,因此必须使用离散傅里叶变换或DFT。但是,这是一个相当慢的操作,并且很容易进行优化,因此我们使用快速傅里叶变换算法或FFT。
这是一个大的信号处理主题,因此建议您寻找用作参考的信号处理书籍。我建议使用“数字信号处理:实用方法”。当然还有无处不在的维基百科文章。
2)FFT的实现
由于FFT的高度优化性质,平台和语言通常具有特定的实现,您应该在头文件和文档中查找(通常会在“音频”部分中找到),以确定是否包含在标准库中。
如果要自己实现算法,我建议找到Numerical Recipes的副本,其中包含FFT的整个章节,以及“傅里叶和频谱应用”一章。有很好的文档化伪代码,应该很容易转录到任何语言中。
对于第三方解决方案,一个受欢迎的选择是FFTW,这是一个C库。搜索“FFT库”将为您提供一些替代方案。
请查看sourceforge上的kissfft。它的速度不如FFTW,但在体积小和易读性方面弥补了不足。在sourceforge上还有一份关于推导的pdf文件--如果你想要理解它,这是必需的。
这里有另一个用C语言编写的。
http://www.archelon.com/fft.html
另外,请问您能否让问题更加具体一些。例如,您想要比较DFT和FFT吗?您对FFT为什么更快感兴趣吗?
如果我没记错的话,DFT需要约N^2次乘法运算,而FFT只需要约N log N次乘法运算,其中N是信号中样本数量。
维基百科有一篇关于FFT的很好的介绍:http://en.wikipedia.org/wiki/Fft。
就实现而言,FFTW是我使用过的最快的,但代码非常难以理解,因为它被疯狂地优化了。有大量基本FFT实现的链接,包括许多C#实现;Google在这里是你的朋友。
http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html (唉,我发现这个很有用,但字体和布局太糟糕了。希望只是我的浏览器出了点问题)
旧的标准数值计算书籍:Numerical Recipes,可能有足够的解释。
问题在于解释您所说的“好”这个词对两件完全不同的事情。
像FFTW这样的快速现代优化FFT几乎无法用来解释正在发生的事情。代码的大部分通常是性能优化,与基本的FFT算法相比,更多地涉及编译器提示、流水线、并行性、缓存阻塞等方面。
而一个漂亮简短(半页或更少的代码)的递归FFT代码示例可能看起来恰好像是FFT的一个(干净优雅简短的)教科书推导的摘要,但与FFTW(或矢量化的pffft等)相比,它可能会变得相当慢,并且使用更多的内存。