快速傅立葉變換

快速傅立葉變換因子之積來快速計算此類變換。 因此，它能夠將計算DFT的複雜度從只用DFT定義計算需要的 formula_1，降低到 formula_2，其中 formula_3 為資料大小。快速傅立葉變換廣泛的應用於工程、科學和數學領域。這裡的基本思想在1965年才得到普及，但早在1805年就已推匯出來。 1994年美國數學家吉爾伯特·斯特朗把FFT描述為“我們一生中最重要的數值演算法”，它還被IEEE科學與工程計算期刊列入20世紀十大演算法。定義和速度.用FFT計算DFT會得到與直接用DFT定義計算相同的結果；最重要的區別是FFT更快。令 "x"0, ..., "x""N"-1 為複數。DFT由下式定義formula_4直接按這個定義求值需要 O("N"2) 次運算："X""k" 共有 "N" 個輸出，每個輸出需要 "N" 項求和。直接使用DFT運算需使用N個複數乘法(4N 個實數乘法)與N-1個複數加法(2N-2個實數加法)，因此，計算使用DFT所有N點的值需要"N"2複數乘法與"N"2-N 個複數加法。FFT則是能夠在 O("N" log "N") 次操作計算出相同結果的任何方法。更準確的說，所有已知的FFT演算法都需要 O("N" log "N") 次運算，雖然還沒有已知的證據證明更低的複雜度是不可能的。要說明FFT節省時間的方式，就得考慮複數相乘和相加的次數。直接計算DFT的值涉及到 "N"2 次複數相乘和 "N"("N"−1) 次複數相加和 "N"log2("N") 次加法就可以得到相同結果。在實際中，現代計算機通常的實際效能通常不受算術運算的速度和對複雜主體的分析主導，但是從 O("N"2) 到 O("N" log "N") 的總體改進仍然能夠體現出來。一般的簡化理論.假設一個M*N型矩陣S可分解成列向量以及行向量相乘：formula_5若formula_6有formula_7個相異的非平凡值formula_10有formula_11個相異的非平凡值則S共需要formula_12個乘法。formula_13Step 1：formula_14Step 2：formula_15簡化理論的變型：formula_16formula_17也是一個M*N的矩陣。若formula_17有formula_19個值不等於0，則formula_20的乘法量上限為formula_21。快速傅立葉變換乘法量的計算.假設formula_22，其中formula_23彼此互質formula_24點DFT的乘法量為formula_25，則formula_26點DFT的乘法量為：formula_27假設formula_28，P是一個質數。若formula_29點的DFT需要的乘法量為formula_30且formula_31當中有formula_33個值不為formula_34及formula_35的倍數，有formula_36個值為formula_34及formula_35的倍數，但不為formula_39的倍數，則N點DFT的乘法量為：formula_40庫利-圖基演算法.庫利-圖基演算法是最常見的FFT演算法。這一方法以分治法為策略遞迴地將長度為formula_41的離散傅立葉變換分解為長度為formula_42的formula_43個較短序列的離散傅立葉變換，以及與formula_44個旋轉因子的複數乘法。這種方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作發表"An algorithm for the machine calculation of complex Fourier series"之後開始為人所知。但後來發現，實際上這兩位作者只是重新發明了高斯在1805年就已經提出的演算法。庫利-圖基演算法最有名的應用，是將序列長為"N "的DFT分割為兩個長為"N/2 "的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和Cooley與Tukey都指出的那樣，Cooley-Tukey演算法也可以用於序列長度"N "為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。儘管Cooley-Tukey演算法的基本思路是採用遞迴的方法進行計算，大多數傳統的演算法實現都將顯式的遞迴演算法改寫為非遞迴的形式。另外，因為Cooley-Tukey演算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT演算法聯合使用。設計思想.下面，我們用N次單位根formula_45來表示formula_46。formula_45的性質：為了簡單起見，我們下面設待變換序列長度formula_55。根據上面單位根的對稱性，求級數formula_56時，可以將求和區間分為兩部分：formula_57formula_58和formula_59是兩個分別關於序列formula_60奇數號和偶數號序列N/2點變換。由此式只能計算出formula_61的前N/2個點，對於後N/2個點，注意formula_58和formula_59都是週期為N/2的函式，由單位根的對稱性，於是有以下變換公式：這樣，一個N點變換就分解成了兩個N/2點變換。照這樣可繼續分解下去。這就是庫利-圖基快速傅立葉變換演算法的基本原理。根據主定理不難分析出此時演算法的時間複雜度為formula_66首先將formula_67個輸入點列按二進位制進行編號，然後對各個編號按位倒置並按此重新排序。例如，對於一個8點變換，001倒置以後變成 100000 → 000001 → 100010 → 010011 → 110100 → 001101 → 101110 → 011111 → 111倒置後的編號為{0,4,2,6,1,5,3,7}。然後將這n個點列作為輸入傳送到蝶形結網路中，注意將因子formula_68逐層加入到蝶形網路中。演算法複雜度.由於按蝶形結網路計算n點變換要進行log "n"層計算，每層計算n個點的變換，故演算法的時間複雜度為formula_69。其他演算法.在Cooley-Tukey演算法之外還有其他DFT的快速演演算法。對於長度formula_70且formula_42與formula_43互質的序列，可以採用基於中國剩餘定理的互質因子演算法將N長序列的DFT分解為兩個子序列的DFT。與Cooley-Tukey演算法不同的是，互質因子演算法不需要旋轉因子。Rader-Brenner演算法是類似於Cooley-Tukey演算法，但是採用的旋轉因子都是純虛數，以增加加法運算和降低了數值穩定性為代價減少了乘法運算。這方法之後被split-radix variant of Cooley-Tukey所取代，與Rader-Brenner演演算法相比，有一樣多的乘法量，卻有較少的加法量，且不犧牲數值的準確性。Bruun以及QFT演演算法是不斷的把DFT分成許多較小的DFT運算。。尤其是Bruun演演算法，把FFT看成是formula_73，並把它分解成formula_74與formula_75的形式。另一個從多項式觀點的快速傅立葉變換法是Winograd演算法。此演演算法把formula_73分解成cyclotomic多項式，而這些多項式的係數通常為1，0，-1。這樣只需要很少的乘法量，所以winograd是可以得到最少乘法量的快速傅立葉演演算法，對於較小的數字，可以找出有效率的算方式。更精確地說，winograd演演算法讓DFT可以用formula_77點的DFT來簡化，但減少乘法量的同時，也增加了非常多的加法量。Winograd也可以利用剩餘值定理來簡化DFT。Rader演演算法提出了利用點數為N。實數或對稱資料專用的演演算法.在許多的運用當中，要進行DFT的資料是純實數，如此一來經過DFT的結果會滿足對稱性：formula_78=formula_79而有一些演演算法是專門為這種情形設計的。在Matlab上用一次N點FFT計算兩個N點實數訊號x,y的FFT:function [X,Y] = Real2FFT( x,y )% N-point FFT is used for 2 real signals both with length NN = length(x);z = x+y*i ;Z = fft(z);X = 0.5*(Z+conj(Z(1+mod(0:-1:1-N,N))));Y = 0.5*(Z-conj(Z(1+mod(0:-1:1-N,N))))/i;end一度人們認為，用離散哈特利轉換來處理純實數的DFT會更有效率，但接著人們發現，對於同樣點數的純實數DFT，經過設計的FFT，可以比DHT省下更多的運算。Bruun演演算法是第一個試著從減少實數輸入的DFT運算量的演演算法，但此法並沒有成為人們普遍使用的方法。對於實數輸入，且輸入為偶對稱或奇對稱的情形，可以更進一步的省下時間以及記憶體，此時DFT可以用離散餘弦轉換或離散正弦轉換來代替。由於DCT/DST也可以設計出FFT的演演算法，故在此種情形下，此方法取代了對DFT設計的FFT演演算法。DFT可以應用在頻譜分析以及做摺積的運算，而在此處，不同應用可以用不同的演演算法來取代，列表如下：用來做頻譜分析的情況下，DFT可用下列的演演算法代替：用來做摺積的情況下，DFT可用下列的演演算法代替：複雜度以及運算量的極限.長久以來，人們對於求出快速傅立葉變換的複雜度下限以及需要多少的運算量感到很有興趣，而實際上也還有許多問題需要解決。即使是用較簡單的情形，即formula_77點的DFT，也還沒能夠嚴謹的證明出FFT至少需要formula_81的運算量，目前也沒有發現複雜度更低的演演算法。通常數學運算量的多寡會是運算效率好壞最主要的因素，但在現實中，有許多因素也會有很大的影響，如快取記憶體以及CPU均有很大的影響。在1978年，Winograd率先匯出一個較嚴謹的FFT所需乘法量的下限：formula_83。當formula_84時，DFT只需要formula_85次無理實數的乘法即可以計算出來。更詳盡，且也能趨近此下限的演演算法也一一被提出。很可惜的是，這些演演算法，都需要很大量的加法計算，目前的硬體無法克服這個問題。對於所需加法量的數目，雖然我們可以在某些受限制的假設下，推得其下限，但目前並沒有一個精確的下限被推匯出來。1973年，Morgenstern在乘法常數趨近巨大的情形下提出使用Cooley-Tukey演演算法所需的複數加法量formula_89是最少的。到目前為止，在長度為formula_84情況，還沒有任何FFT的演演算法可以讓複數的加法量比formula_89還少。還有一個問題是如何把乘法量與加法量的總和最小化，有時候稱作"演算複雜度"大多數嘗試要降低或者證明FFT複雜度下限的人都把焦點放在複數資料輸入的情況，因其為最簡單的情形。但是，複數資料輸入的FFT演演算法，與實數資料輸入的FFT演演算法，離散餘弦轉換。快速演演算法查表.當輸入訊號長度為N時:N = 1~60N  1000