在哪里可以找到好的 FFT 示例实现/教程？
我一直在到处寻找（最好是）C# 中的示例快速傅里叶变换实现/教程。
然而，我发现的每个人都不太善于解释正在发生的事情，和/或评论很差； 或者他们假设您已经了解 FFT 算法，或者他们是有关如何使用 FFT 的教程。
有人知道好的示例/教程吗？
I've been looking everywhere for a sample Fast Fourier Transform implementation/tutorial in (preferably) C#.
However, every one I've found has been poor at explaining what's going on, and/or poorly commented; or they assume that you already know the FFT algorithm, or they're tutorials about how to USE FFTs.
Anyone know of a good sample/tutorial?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
抱歉缺少超链接，我没有添加它们的权限：（
您在这里要求两件事
1）FFT的解释
非常简单：
如果您想要要获得信号的频域表示，您可以使用傅立叶变换，这是一种将信号从时域变换到频域的数学变换。 当对数字信号进行操作时，我们有一组离散样本，因此我们必须使用离散傅里叶变换或DFT。 然而，这是一个相当慢的操作并且很容易优化，因此我们改用快速傅立叶变换算法或FFT。
这是一个很大的信号处理主题，因此我建议您寻找一本信号处理书籍作为参考。 我建议“数字信号处理：一种实用方法”。 当然还有无处不在的维基百科文章。
2) FFT 的实现
由于 FFT 平台和语言的高度优化特性通常具有特定的实现，因此您应该检查标头和文档（通常可以在“音频”部分中找到）如果它包含在标准库中。
如果您想自己实现该算法，我建议您找到一份 Numerical Recipes 的副本，其中包含有关 FFT 的整个章节，以及有关“傅里叶和频谱应用”的章节。 有详细记录的伪代码，应该很容易转录成任何语言。
对于第三方解决方案，流行的选择是 FFTW，一个 C 库。 我在谷歌上搜索“FFT Library”将为您提供一些替代方案。
Apologies for lack of hyperlinks, I do not have permissions to add them :(
You are asking for two things here
1) An explanation of the FFT
Very briefly:
If you want to obtain the frequency domain representation of a signal you use the fourier transform, this is a mathematical transform which transforms a signal from the time domain to the frequency domain. When operating on digital signals we have a set of discrete samples so we must use the Discrete Fourier Transform or DFT. However this is a rather slow operation and is easily optimised, so we instead use a Fast Fourier Transform algorithm or FFT.
This is a large signal processing topic so I suggest you look for a signal processing book to use as a reference. I suggest "Digital Signal Processing: A Practical Approach". There is of course the ubiquitous wikipedia article as well.
2) An implementation of the FFT
Because of the highly optimised nature of the FFT platforms and languages often have specific implementations, you should check headers and documentation (typically it will be found in an 'audio' section) in case it is included in a standard library.
If you want to implement the algorithm yourself I recommend finding a copy of Numerical Recipes, this contains an entire chapter on the FFT, as well as a chapter on "Fourier and Spectral Applications". There is well documented pseudocode which should be easy to transcribe into any language.
For a third party solution a popular choice is FFTW, a C library. I google search for "FFT Library" will provide you with some alternatives.
请参阅 Sourceforge 上的 Kissfft。 它缺乏 FFTW 的速度，但以小尺寸和可读性弥补了这一点。 sourceforge 上也有一个关于推导的 pdf 文件——如果您想尝试理解它，则需要它。
See kissfft on sourceforge. It lacks a bit of the speed of FFTW, but makes up for it in small size and readability. There is a pdf also on sourceforge about the derivation -- required if you are going to try to understand it.
Google 发现了一些：
Exocortex.DSP
FFTW（C 库 DLL，可以
从 C# 调用
建议使用 FFTW 库作为快速解决方案FFT。
Google turns up a few:
Exocortex.DSP
FFTW (C library DLL that can be
called from C#)
The FFTW library is recommended as a solution fast FFTs.
这是用 C 语言编写的另一篇文章。
http://www.archelon.com/fft.html
另外，你能把你的问题说得更具体一些吗？ 例如，您想将 DFT 与 FFT 进行比较吗？ 您是否对为什么 FFT 速度如此之快感兴趣？
如果我没记错的话，DFT 类似于 N^2 乘法，而 FFT 大约是 N log N 乘法，其中 N 是信号中的样本数。
Here is another one written in C.
http://www.archelon.com/fft.html
Also, can you make your question more specific. For example, do you want to compare the DFT to the FFT? Are you interested in why the FFT is so much faster?
If I remember correctly DFT is something like N^2 multiplications and the FFT is about N log N multiplications, where N is number of samples in the signal.
维基百科有一篇关于 FFT 的精彩文章：http://en.wikipedia.org/wiki/Fft。
就实现而言，FFTW 是我用过的最快的，但代码非常难以理解，因为它经过了疯狂的优化。 有大量指向基本 FFT 实现的链接，其中包括大量 C# 语言； Google 是您的朋友。
Wikipedia has a great writeup of the FFT: http://en.wikipedia.org/wiki/Fft.
As far as implementations go, FFTW is the fastest I've ever used, but the code is extremely difficult to understand as it is crazy optimized. There are tons of links to basic FFT implementations, including plenty in C#; Google is your friend here.
http://www.cmlab. csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html
（是的，我发现这很有用，但字体和布局很糟糕。我希望这只是我的浏览器很奇怪）
http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html
(yeesh, i found this useful but the font and layout are horrible. i hope it's just my browser being weird)
数字运算的旧标准书：Numerical Recipes，可能有足够的解释。
The old standard book for number crunching: Numerical Recipes, may have an sufficient explanation.
如果你能找到一份《微处理器的音乐应用》
作者：Hal Chamberlin，1983（？）可能有 FFT 的一部分 - 唉，我的副本现在正在工作，所以我无法专门查看这本书以了解 FFT 知识。 但我确实学习了音频过滤、采样等的许多基础知识，并且有大量关于傅里叶变换及其用途的材料。
If you can find a copy, Musical Applications of Microprocessors
by Hal Chamberlin, 1983 (?) may have a section of FFT - alas my copy is at work right now so i can't check the book specifically for FFT wisdom. But i did learn many basics of audio filtering, sampling etc. and there is plenty of material on Fourier transforms and their uses.
问题在于如何将“好”这个词解释为两个完全不同的事物。
快速现代优化的 FFT（例如 FFTW）对于解释正在发生的事情几乎毫无用处。 代码的很大一部分通常是性能优化，与基本 FFT 算法相比，它们更多地与编译器提示、流水线、并行性、缓存阻塞等相关。
然而，FFT 代码的一个简短的（半页代码或更少）递归示例可能看起来与 FFT 的教科书推导之一（干净优雅的简短）的摘要完全相同，但与 FFTW 相比，速度相当慢并且使用更多内存（或矢量化 pffft 等）。
The problem is with interpreting your word "good" for two completely different things.
A fast modern optimized FFT, such as FFTW, is nearly useless for explaining what's going on. A huge portion of the code is usually performance optimizations that have more to do with compiler hints, pipelining, parallelism, cache blocking, and such, than the basic FFT algorithm.
Whereas a nice short (half page of code or less) recursive example of FFT code may look exactly like a summary of one of the (clean elegant short) textbook derivations of the FFT, but be quite slow and use more memory in comparison to FFTW (or vectorized pffft, et.al.).