logo标签列表

我该去哪里找到一个好的FFT样例实现/教程？

c#fftsample
6
我已经在各处寻找一个（最好是）C#的示例快速傅里叶变换实现/教程。
然而，我发现每个我找到的都很差，无法解释正在发生的事情，或者注释不当；或者它们假定你已经知道FFT算法，或者它们是关于如何使用FFT的教程。
有人知道一个好的示例/教程吗？
我猜FFT是快速傅里叶变换？可能需要澄清一下。 - cletus
我没有看到这个内容与编程有任何关系。它同样可以是关于编织的。 - Mitch Wheat
5
哦，所以我只需要编织一些可以计算FFT的东西吗？这与寻找好的地形高度图教程或快速排序教程一样重要，都是关于编程技巧的。 - TraumaPony
4
正如问题中已经提到的那样，我已经尝试过了，但没有任何效果。 - TraumaPony
2
@Mitch Wheat，为什么在C#中的快速傅里叶变换与编程无关？我不明白。 - mmcdole
FFT代码示例实际上与FFT教程是两回事，顺便说一句。也许你可以要求其中之一？ - Joe Soul-bringer
9个回答
6

抱歉没有超链接，我没有添加它们的权限 :(

您在这里要求两件事：

1）FFT的解释

简单地说：

如果您想获得信号的频域表示，则使用傅里叶变换，这是一种将信号从时间域转换为频率域的数学变换。当操作数字信号时，我们有一组离散样本，因此必须使用离散傅里叶变换或DFT。但是，这是一个相当慢的操作，并且很容易进行优化，因此我们使用快速傅里叶变换算法或FFT。

这是一个大的信号处理主题，因此建议您寻找用作参考的信号处理书籍。我建议使用“数字信号处理：实用方法”。当然还有无处不在的维基百科文章。

2）FFT的实现

由于FFT的高度优化性质，平台和语言通常具有特定的实现，您应该在头文件和文档中查找（通常会在“音频”部分中找到），以确定是否包含在标准库中。

如果要自己实现算法，我建议找到Numerical Recipes的副本，其中包含FFT的整个章节，以及“傅里叶和频谱应用”一章。有很好的文档化伪代码，应该很容易转录到任何语言中。

对于第三方解决方案，一个受欢迎的选择是FFTW，这是一个C库。搜索“FFT库”将为您提供一些替代方案。

3

请查看sourceforge上的kissfft。它的速度不如FFTW，但在体积小和易读性方面弥补了不足。在sourceforge上还有一份关于推导的pdf文件--如果你想要理解它，这是必需的。

1

谷歌搜索出了一些结果：

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

是的，但前者几乎没有注释，而后者则高度优化；不完全是一个介绍性的“这就是如何做”的东西。 - TraumaPony
也许你要求一个教程，唉！ - Mitch Wheat
1

这里有另一个用C语言编写的。

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

另外，请问您能否让问题更加具体一些。例如，您想要比较DFT和FFT吗？您对FFT为什么更快感兴趣吗？

如果我没记错的话，DFT需要约N^2次乘法运算，而FFT只需要约N log N次乘法运算，其中N是信号中样本数量。

@TraumaPony: 你打算保持一致的态度，也对这个答案进行否定吗？因为它不能满足你的要求吗？ - Mitch Wheat
它可能不能完全满足他们的需求，但它仍然相当清晰简单。 - TraumaPony
1

维基百科有一篇关于FFT的很好的介绍：http://en.wikipedia.org/wiki/Fft。

就实现而言，FFTW是我使用过的最快的，但代码非常难以理解，因为它被疯狂地优化了。有大量基本FFT实现的链接，包括许多C#实现；Google在这里是你的朋友。

1
1

旧的标准数值计算书籍：Numerical Recipes，可能有足够的解释。

1
显然，NR已经过时，并且其FFT建议可能存在缺陷。 - Mitch Wheat
我也听说过，但不太记得那个漏洞是什么了。大家要小心，因人而异，自己检查一下数学计算等等... - DarenW
1
如果你能找到一本《微处理器的音乐应用》（Hal Chamberlin，1983年？），它可能有一个FFT部分 - 不幸的是，我的副本现在在工作中，所以我无法具体查看FFT智慧。但我确实学到了许多音频滤波、采样等基础知识，并且有大量关于傅里叶变换及其用途的材料。
谢谢，我得看看买一个。 - TraumaPony
我喜欢这本书。刚刚被激发写了一个亚马逊评论。 - DarenW
1

问题在于解释您所说的“好”这个词对两件完全不同的事情。

像FFTW这样的快速现代优化FFT几乎无法用来解释正在发生的事情。代码的大部分通常是性能优化，与基本的FFT算法相比，更多地涉及编译器提示、流水线、并行性、缓存阻塞等方面。

而一个漂亮简短（半页或更少的代码）的递归FFT代码示例可能看起来恰好像是FFT的一个（干净优雅简短的）教科书推导的摘要，但与FFTW（或矢量化的pffft等）相比，它可能会变得相当慢，并且使用更多的内存。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接