FFT與DFT有什麼不同，以及如何在C++中實現它們？

經過一番研究，我創建了一個小應用程序，可以根據某些輸入計算DFT（離散傅立葉變換）。它運行得很好，但速度很慢。FFT與DFT有什麼不同，以及如何在C++中實現它們？

我讀到FFT（快速傅立葉變換）允許更快的計算，但它們有什麼不同？更重要的是，我將如何着手在C++中實現它們？

來源

2010-04-03 Nathan Osman

FFT僅僅是一個參考算法，快速計算的DFT的方式;也就是說，FFT算法的結果應該與通過定義計算DFT的結果相同（或非常接近）。 – 2010-04-03 22:31:38

FFT只能在長度爲2的樣本上計算，DFT沒有此限制。我沒有看到任何人的答案，但這是你需要知道的事情，我不認爲這是一個單獨的答案。 – 2010-04-05 03:28:13

如果您不需要手動實現算法，你可以看看在Fastest Fourier Transform in the West

甚至認爲在C發達，它正式工作在C++（從FAQ）

問題2.9。我可以從 C++調用FFTW嗎？

絕對是。 FFTW應該在任何C++編譯器下編譯和/或鏈接。此外，C++ 模板類可能與FFTW的複數格式（請參閱FFTW 手冊以獲得更多詳細信息）位兼容。

來源

2010-04-03 22:31:51 XSL

嗯......你提到的圖書館需要非商業用途的費用。 – 2010-04-03 22:45:42

對不起，不知道這是出於商業目的。在這種情況下，你可以嘗試http://kissfft.sourceforge.net/。這使用BSD許可證 – XSL 2010-04-03 23:16:40

我發現這個很好的解釋與一些算法描述。

FastFourierTransform

關於實施，

首先我會確保您的實現返回正確的結果（比較從MATLAB或倍頻輸出 - 這已經建立了傅立葉transformates）
優化時必要時使用分析器
不要使用不必要的循環

來源

2010-04-03 22:35:46 bua

與具有n^2的DFT相比，FFT具有n * log（n）強度。

有很多關於這方面的文獻，我強烈建議您先檢查一下，因爲這樣的廣泛的主題不能在這裏完整地解釋。 http://en.wikipedia.org/wiki/Fast_Fourier_transform（檢查外部鏈接）

如果您需要庫，我建議您使用現有的庫，例如。 http://www.fftw.org/ 這圖書館有效地執行FFT，並且也用在propariaretery軟件（MATLAB例如）

來源

2010-04-03 22:39:05

史蒂芬·史密斯的書The Scientist and Engineer's Guide to Digital Signal Processing，特別是Chapter 8 on the DFT和Chapter 12 on the FFT，做了解釋兩個變換的一個更好的工作，我都做不到。

順便說一句，整本書是免費的（上面的鏈接），這是一個非常好的信號處理介紹。

關於C++代碼請求，我只使用西方最快的傅立葉變換（已經被superexsl引用）或DSP庫（例如來自TI或ADI公司的DSP庫）。

來源

2010-04-04 02:39:43 Dan

一個正確實現DFT的結果的正確實現FFT的結果（它們僅通過舍入錯誤不同）基本上相同。正如其他人在這裏指出的，主要區別在於績效。 DFT具有O（n^2）操作，而FFT具有O（nlogn）操作。

最好的，最可讀的出版，我曾經發現（一個我仍然引用）是The Fast Fourier Transform and its Applications用E奧蘭布里格姆。前幾章提供了傅立葉變換的連續和離散形式的非常全面的概述。然後，他使用它來開發基於Cooley-Tukey Algorithm的基數爲2的快速版本的DFT（n是2的冪）和混合基數的情況（雖然後者比前者更淺一些）。

在基數爲2的算法的基本方法對輸入X執行線性時間操作，並遞歸地劃分結果一半，並在兩個半部分執行類似的線性時間的操作。混合基數情況是相似的，但是每次需要將X分成相等的部分，所以如果n沒有任何大的素因子，它會有所幫助。

來源

2010-04-04 03:58:01 andand

FFT與DFT有什麼不同，以及如何在C++中實現它們？

回答

相關問題