我在哪里可以找到一个很好的FFT示例实现/教程？

Question

我一直在寻找一个示例快速傅立叶变换实现/教程（最好是）C＃。

但是，我发现每个人都很难解释正在发生的事情和/或评论不好;或者他们假设你已经知道FFT算法，或者他们是关于如何使用FFT的教程。

任何人都知道一个很好的示例/教程？

Answer 1

谷歌变成了几个：

• Exocortex.DSP

• FFTW（C库DLL，可以是 called from C#)

的FFTW库被推荐为解决快速的FFT 。

Answer 2

这里是另外一个用C写的

http://www.archelon.com/fft.html

此外，您还可以让你的问题更具体。例如，你想比较DFT和FFT吗？你对FFT为何如此快速感兴趣吗？

如果我没记错的话，DFT就像N^2乘法，FFT大约是N log N次乘法，其中N是信号中采样的次数。

Answer 3

维基百科有一个伟大的FFT的写作：http://en.wikipedia.org/wiki/Fft。就实现而言，FFTW是我使用过的最快的，但代码非常难以理解，因为它是疯狂优化的。有大量的基本FFT实现的链接，包括C＃中的大量链接; Google是你的朋友在这里。

Answer 4

http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html （yeesh，我发现这非常有用，但字体和布局是可怕的，我希望这只是我的浏览器是奇怪的。）

Answer 5

旧标准书数字运算：数字食谱，可以有足够的解释。

Answer 6

如果你可以找到一份副本，Hal Chamberlin，1983（？）的微处理器音乐应用 可能有一段FFT - 唉我的副本现在正在工作，所以我不能检查专门为FFT智慧。但我确实学到了音频滤波，采样等许多基础知识，并且傅立叶变换及其使用方面有大量材料。

Answer 7

道歉缺乏超链接的，我没有权限，将它们添加 :(

你问这里两件事情

1）FFT的解释

非常简短：

如果你想获得信号的频域表示，你可以使用fourier变换，这是将信号从时域变换到频域的数学变换。当对数字信号进行操作时，我们有一组离散样本，所以我们必须使用离散傅里叶变换或DFT。然而，这是一个相当慢的操作，并且易于优化，所以我们改为使用快速傅里叶变换算法或快速傅里叶变换。

这是一个很大的信号处理主题，所以我建议你找一本信号处理书作为参考。我建议“数字信号处理：一种实用的方法”。当然，无处不在的维基百科文章也是如此。

2）FFT的实现

由于对FFT平台和语言往往有具体的实现，你应该检查头和文档的高度优化的性质（通常它会在“音频发现'部分）以防它包含在标准库中。

如果您想自己实现算法，我建议您找到数值处方的副本，其中包含关于FFT的完整章节以及关于“傅立叶和光谱应用”的章节。有很好的文档伪代码应该很容易转录成任何语言。

对于第三方解决方案，流行的选择是FFTW，一个C库。我谷歌搜索“FFT库”将为您提供一些替代品。

Answer 8

请参阅sourceforge上的kissfft。它缺乏FFTW的速度，但在小尺寸和可读性方面弥补了这一点。 sourceforge上还有一个关于派生的pdf - 如果你想要了解它，那么这是必需的。

Answer 9

问题在于将两个完全不同的东西解释为“好”。

一个快速现代优化的FFT，如FFTW，几乎无用于解释发生了什么。代码的很大一部分通常是性能优化，这些性能优化与编译器提示，流水线处理，并行处理，缓存阻塞等有关，而不是基本的FFT算法。

尽管FFT代码的一个很好的短（半页代码）递归示例可能看起来完全像FFT的教科书衍生之一的摘要，但与FFTW相比非常慢。