我在哪裏可以找到一個很好的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相比非常慢。