圖基fft演算法

『壹』 FFT演算法分幾種

FFT演算法分析FFT演算法的基本原理是把長序列的DFT逐次分解為較短序列的DFT。按照抽取方式的不同可分為DIT-FFT（按時間抽取）和DIF-FFT（按頻率抽取）演算法。按照蝶形運算的構成不同可分為基2、基4、基8以及任意因子（2n,n為大於1的整數），基2、基4演算法較為常用。 網上有幫助文檔: http://www.5doc.com/doc/123035(右上角有點擊下載)

『貳』 誰知道DFT和FFT的發展歷史啊

DFT/FFT的發展歷史
離散傅里葉變換（Discrete Fourier Transform，DFT）是數字信號處理最重要的基石之一，也是對信號進行分析和處理時最常用的工具之一。在200多年前法國數學家、物理學家傅里葉提出後來以他名字命名的傅里葉級數之後，用DFT這個工具來分析信號就已經為人們所知。歷史上最偉大的數學家之一。
歐拉是第一個使用「函數」一詞來描述包含各種參數的表達式的人，例如：y = f(x)。他是把微積分應用於物理學的先驅者之一。 給出了一個用實變數函數表示傅立葉級數系數的方程； 用三角級數來描述離散聲音在彈性媒介中傳播，發現某些函數可以通過餘弦函數之和來表達。 但在很長時間內，這種分析方法並沒有引起更多的重視，最主要的原因在於這種方法運算量比較大。直到1965年，Cooley和Tukey在《計算機科學 》發表著名的《機器計算傅立葉級數的一種演算法》論文，FFT才開始大規模應用。
那個年代，有個肯尼迪總統科學咨詢委員會。其中有項研究主題是，對蘇聯核測試進行檢測，Tukey就是其中一員。美國/蘇聯核測試提案的批准，主要取決於不實地訪問核測試設施而做出檢測的方法的發展。其中一個想法是，分析離海岸的地震計情況，這種計算需要快速演算法來計算DFT。其它應用是國家安全，如用聲學探測遠距離的核潛艇。所以在軍事上，迫切需要一種快速的傅立葉變換演算法，這也促進了FFT的正式提出。
FFT的這種方法充分利用了DFT運算中的對稱性和周期性，從而將DFT運算量從N2減少到N*log2N。當N比較小時，FFT優勢並不明顯。但當N大於32開始，點數越大，FFT對運算量的改善越明顯。比如當N為1024時，FFT的運算效率比DFT提高了100倍。在庫利和圖基提出的FFT演算法中，其基本原理是先將一個N點時域序列的DFT分解為N個1點序列的DFT，然後將這樣計算出來的N個1點序列DFT的結果進行組合，得到最初的N點時域序列的DFT值。實際上，這種基本的思想很早就由德國偉大的數學家高斯提出過，在某種情況下，天文學計算（也是現在FFT應用的領域之一）與等距觀察的有限集中的行星軌道的內插值有關。由於當時計算都是靠手工，所以產生一種快速演算法的迫切需要。 而且，更少的計算量同時也代表著錯誤的機會更少，正確性更高。高斯發現，一個富氏級數有寬度N=N1*N2，可以分成幾個部分。計算N2子樣本DFT的N1長度和N1子樣本DFT的N2長度。只是由於當時尚欠東風——計算機還沒發明。在20世紀60年代，伴隨著計算機的發展和成熟，庫利和圖基的成果掀起了數字信號處理的革命，因而FFT發明者的桂冠才落在他們頭上。
之後，桑德（G.Sand）-圖基等快速演算法相繼出現，幾經改進，很快形成了一套高效運算方法，這就是現在的快速傅立葉變換（FFT）。這種演算法使DFT的運算效率提高1到2個數量級，為數字信號處理技術應用於各種信號的實時處理創造了良好的條件，大大推進了數學信號處理技術。1984年，法國的杜哈梅（P.Dohamel）和霍爾曼（H.Hollamann）提出的分裂基塊快速演算法，使運算效率進一步提高。
庫利和圖基的FFT演算法的最基本運算為蝶形運算，每個蝶形運算包括兩個輸入點，因而也稱為基-2演算法。在這之後，又有一些新的演算法，進一步提高了FFT的運算效率，比如基-4演算法，分裂基演算法等。這些新演算法對FFT運算效率的提高一般在50%以內，遠遠不如FFT對DFT運算的提高幅度。從這個意義上說，FFT演算法是里程碑式的。可以說，正是計算機技術的發展和FFT的出現，才使得數字信號處理迎來了一個嶄新的時代。除了運算效率的大幅度提高外，FFT還大大降低了DFT運算帶來的累計量化誤差，這點常為人們所忽略。

分給我吧 哈哈

『叄』 FFT的公式是什麼和演算法是怎樣實現

二維FFT相當於對行和列分別進行一維FFT運算。具體的實現辦法如下：
先對各行逐一進行一維FFT，然後再對變換後的新矩陣的各列逐一進行一維FFT。相應的偽代碼如下所示：
for (int i=0; i<M; i++)
FFT_1D(ROW[i]，N);
for (int j=0; j<N; j++)
FFT_1D(COL[j]，M);
其中，ROW[i]表示矩陣的第i行。注意這只是一個簡單的記法，並不能完全照抄。還需要通過一些語句來生成各行的數據。同理，COL[i]是對矩陣的第i列的一種簡單表示方法。
所以，關鍵是一維FFT演算法的實現。下面討論一維FFT的演算法原理。

【1D-FFT的演算法實現】
設序列h(n)長度為N，將其按下標的奇偶性分成兩組，即he和ho序列，它們的長度都是N/2。這樣，可以將h(n)的FFT計算公式改寫如下 ：

(A)
由於

所以，(A)式可以改寫成下面的形式：

按照FFT的定義，上面的式子實際上是：

其中，k的取值范圍是 0~N-1。
我們注意到He(k)和Ho(k)是N/2點的DFT，其周期是N/2。因此，H(k)DFT的前N/2點和後N/2點都可以用He(k)和Ho(k)來表示

『肆』 什麼是FFT

計算離散傅里葉變換的一種快速演算法,簡稱FFT(Fast Fourier Transform)。快速傅里葉變換是1965年由J.W.庫利和T.W.圖基提出的。採用這種演算法能使計算機計算離散傅里葉變換所需要的乘法次數大為減少,特別是被變換的抽樣點數N越多,FFT演算法計算量的節省就越顯著。
FFT 的出現，使信號分析從時域分析向頻域分析成為可能，極大地推動了信號分析在各領域的實際應用。
http://ke..com/view/1006229.htm

『伍』 fft可分解多少級

2的n-1次方級。
FFT演算法的實質是把一長序列的DFT計算分割為較短序列的DFT計算，對於基2演算法而言，是把序列每次一分為二，最後分割成兩點DFT，也可以採用別的分割法，每次一分為三，四，五等，就得到了基3，基4，基5等演算法，其中基4演算法由於具備某些優點，應用價值較大。
快速傅里葉變換計算離散傅里葉變換的一種快速演算法，簡稱FFT；快速傅里葉變換是1965年由J.W庫利和T.W.圖基提出的，採用這種演算法能使計算機計算離散傅里葉變換所需要的乘法次數大為減少，特別是被變換的抽樣點數N越多，FFT演算法計算量的節省就越顯著。

『陸』 FFT原理的FFT基本原理

FFT是一種DFT的高效演算法，稱為快速傅立葉變換（fast Fourier transform）。FFT演算法可分為按時間抽取演算法和按頻率抽取演算法，先簡要介紹FFT的基本原理。從DFT運算開始，說明FFT的基本原理。
DFT的運算為：

式中

由這種方法計算DFT對於X（K）的每個K值，需要進行4N次實數相乘和（4N-2）次相加，對於N個k值，共需N*N乘和N（4N-2）次實數相加。改進DFT演算法，減小它的運算量，利用DFT中

的周期性和對稱性，使整個DFT的計算變成一系列迭代運算，可大幅度提高運算過程和運算量，這就是FFT的基本思想。
FFT基本上可分為兩類，時間抽取法和頻率抽取法，而一般的時間抽取法和頻率抽取法只能處理長度N=2^M的情況，另外還有組合數基四FFT來處理一般長度的FFT 設N點序列x(n),,將x(n)按奇偶分組，公式如下圖

改寫為：

一個N點DFT分解為兩個 N/2點的DFT，繼續分解，迭代下去，其運算量約為

其演算法有如下規律
兩個4點組成的8點DFT

四個2點組成的8點DFT
按時間抽取的8點DFT
原位計算
當數據輸入到存儲器中以後，每一級運算的結果仍然儲存在同一組存儲器中，直到最後輸出，中間無需其它存儲器
序數重排
對按時間抽取FFT的原位運算結構，當運算完畢時，這種結構存儲單元A(1)、A(2)，…，A(8)中正好順序存放著X(0)，X(1)，X(2)，…，X(7)，因此可直接按順序輸出，但這種原位運算的輸入x(n)卻不能按這種自然順序存入存儲單元中，而是按X(0)，X(4)，X(2)，X(6)，…，X(7)的順序存入存儲單元，這種順序看起來相當雜亂，然而它也是有規律的。當用二進製表示這個順序時，它正好是「碼位倒置」的順序。
蝶形類型隨迭代次數成倍增加
每次迭代的蝶形類型比上一次蝶代增加一倍，數據點間隔也增大一倍 頻率抽取2FFT演算法是按頻率進行抽取的演算法。
設N=2^M，將x(n)按前後兩部分進行分解，
按K的奇偶分為兩組，即
得到兩個N/2 點的DFT運算。如此分解，並迭代，總的計算量和時間抽取（DIT）基2FFT演算法相同。
演算法規律如下：
蝶形結構和時間抽取不一樣但是蝶形個數一樣，同樣具有原位計算規律，其迭代次數成倍減小 時，可採取補零使其成為
，或者先分解為兩個p,q的序列，其中p*q=N，然後進行計算。 前面介紹，採用FFT演算法可以很快算出全部N點DFT值，即z變換X（z）在z平面單位圓上的全部等間隔取樣值。實際中也許①不需要計算整個單位圓上z變換的取樣，如對於窄帶信號，只需要對信號所在的一段頻帶進行分析，這時希望頻譜的采樣集中在這一頻帶內，以獲得較高的解析度，而頻帶以外的部分可不考慮，②或者對其它圍線上的z變換取樣感興趣，例如語音信號處理中，需要知道z變換的極點所在頻率，如極點位置離單位圓較遠，則其單位圓上的頻譜就很平滑，這時很難從中識別出極點所在的頻率，如果采樣不是沿單位圓而是沿一條接近這些極點的弧線進行，則在極點所在頻率上的頻譜將出現明顯的尖峰，由此可較准確地測定極點頻率。③或者要求能有效地計算當N是素數時序列的DFT，因此提高DFT計算的靈活性非常有意義。
螺旋線采樣是一種適合於這種需要的變換，且可以採用FFT來快速計算，這種變換也稱作Chirp-z變換。

『柒』 FFT的最優演算法是什麼以及其代碼（C語言），謝謝！

應該是庫利-圖基演算法和桑德-圖基演算法吧。這兩種演算法的時間復雜度是一樣的，需要（N/2)log2N次的復數乘法和Nlog2N的復數加法。
當然你要是用基-4的FFT會更快，需要3/8Nlog2N次的復數乘法和Nlog2N次的加法。但這樣做的一個很麻煩的事是在做快速傅立葉變換時需要將原數據補足到2或4的整數次方。因此如果數據量合適的話基-4要快，如果數據不合適還是用基-2好。至於C語言代碼暫時沒有。還有為什麼要編C啊？用Matlab不是更好嗎？連循環都不用寫，甚至還有已經寫好的函數fft（），直接看這個函數演算法就好了

『捌』 試畫出信號按時間抽取的基-2FFT演算法信號流圖，並寫出對應過程奇偶分流的公式。

基2演算法，序列的長度是為2的冪，序列的DFT為。序列可以由奇序列和偶序列組成，DFT分別為和。 從最後一級往前分解對應的蝶形結構，這些蝶形結構最左邊的輸入都是序列的DFT值，而分解直到最左邊的蝶形結構是兩點序列的DFT，此時最左邊的值是序列x[k]。

f1=50; %10Hz

f2=100; %100Hz

%抽樣頻率

Fs=1000; %100Hz

%抽樣點數N

L=10;

N=2^L;

%抽樣脈沖序列

n = 0:N-1;

t = n./Fs;

% f2 一個周期的采樣數

M = floor(Fs/f2);

%被采樣信號

x = cos(2*pi*f1.*t)+sin(2*pi*f2.*t);

%采樣序列

subplot(311);

stem(t(1:2*M),x(1:2*M));

hold off;

%傅里葉變換

%根據有限長序列的離散傅里葉變換公式計算DFT

n = 0:N-1;

k = 0:N-1;

F = x * exp(-j*2*pi/N).^(n'*k);

subplot(312);

plot(n,abs(F));

subplot(313);

plot(k,angle(F));

(8)圖基fft演算法擴展閱讀：

庫利－圖基快速傅里葉變換演算法是將序列長為N的DFT分區為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和庫利與圖基都指出的那樣，庫利－圖基演算法也可以用於序列長度N為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。

盡管庫利－圖基演算法的基本思路是採用遞歸的方法進行計算，大多數傳統的演算法實現都將顯示的遞歸演算法改寫為非遞歸的形式。另外，因為庫利－圖基演算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT演算法聯合使用。

『玖』 FFT的演算法

FFT是一種DFT的高效演算法，稱為快速傅立葉變換（fast Fourier transform），它根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的演算法進行改進獲得的。FFT演算法可分為按時間抽取演算法和按頻率抽取演算法，先簡要介紹FFT的基本原理。從DFT運算開始，說明FFT的基本原理。
DFT的運算為：

式中
由這種方法計算DFT對於 的每個K值，需要進行4N次實數相乘和（4N-2）次相加，對於N個k值，共需4N*4N次實數相乘和（4N-2)(4N-2）次實數相加。改進DFT演算法，減小它的運算量，利用DFT中 的周期性和對稱性，使整個DFT的計算變成一系列迭代運算，可大幅度提高運算過程和運算量，這就是FFT的基本思想。
FFT對傅氏變換的理論並沒有新的發現，但是對於在計算機系統或者說數字系統中應用離散傅立葉變換，可以說是進了一大步。
設x(n)為N項的復數序列，由DFT變換，任一X（m）的計算都需要N次復數乘法和N-1次復數加法，而一次復數乘法等於四次實數乘法和兩次實數加法，一次復數加法等於兩次實數加法，即使把一次復數乘法和一次復數加法定義成一次「運算」（四次實數乘法和四次實數加法），那麼求出N項復數序列的X（m）,即N點DFT變換大約就需要N^2次運算。當N=1024點甚至更多的時候，需要N2=1048576次運算，在FFT中，利用WN的周期性和對稱性，把一個N項序列（設N=2k,k為正整數），分為兩個N/2項的子序列，每個N/2點DFT變換需要（N/2）2次運算，再用N次運算把兩個N/2點的DFT變換組合成一個N點的DFT變換。這樣變換以後，總的運算次數就變成N+2*（N/2)^2=N+（N^2）/2。繼續上面的例子，N=1024時，總的運算次數就變成了525312次，節省了大約50%的運算量。而如果我們將這種「一分為二」的思想不斷進行下去，直到分成兩兩一組的DFT運算單元，那麼N點的DFT變換就只需要Nlog2N次的運算，N在1024點時，運算量僅有10240次，是先前的直接演算法的1%，點數越多，運算量的節約就越大，這就是FFT的優越性。

『拾』 「DFT、IDFT、FFT、IFFT」各是什麼

DFT，即可測試性設計（Design for Testability, DFT）是一種集成電路設計技術，它將一些特殊結構在設計階段植入電路，以便設計完成後進行測試。電路測試有時並不容易，這是因為電路的許多內部節點信號在外部難以控制和觀測。通過添加可測試性設計結構，例如掃描鏈等，內部信號可以暴露給電路外部。總之，在設計階段添加這些結構雖然增加了電路的復雜程度，看似增加了成本，但是往往能夠在測試階段節約更多的時間和金錢。

IDFT就是Inverse Discrete Fourier Transform 離散傅里葉逆變換。FFT就是Fast Fourier Transform 快速傅里葉變換。

兩者的應用都是將時域中難以處理的信號轉換成易於處理的頻域信號，分析完成後進行傅里葉反變換即得到原始的時域信號。
兩者的異同是：我們知道在數學上用級數來無限逼進某個函數，以便簡化計算過程而又不致使誤差過大，這樣工程上才能應用，否則一些數學模型是無法實現快速求解的。

IDFT：對於有限長的序列我們可以使用離散傅立葉變換，IDFT是對序列傅立葉變換的等距采樣。

FFT：並不是與IDFT不相同的另一種變換（即原理是一樣的），而是為了減少IDFT運算次數的一種快速演算法。它是對IDFT變換式進行一次次的分解，使其成為若干小點數IDFT的組合，從而減小運算量。常用的FFT是以2為基數，它的運算效率高，程序比較簡單，使用也十分地方便。

IFFT——Inverse Fast Fourier Transform 快速傅里葉逆變換。

快速傅里葉變換 (fast Fourier transform), 即利用計算機計算離散傅里葉變換（DFT)的高效、快速計算方法的統稱，簡稱FFT。快速傅里葉變換是1965年由J.W.庫利和T.W.圖基提出的。採用這種演算法能使計算機計算離散傅里葉變換所需要的乘法次數大為減少，特別是被變換的抽樣點數N越多，FFT演算法計算量的節省就越顯著。