快速傅裏葉變換-百科詞條

　　簡稱FFT，是指進行“有限離散傅裏葉變換”(簡稱DFT)的快速演算法。一維DFT是把N元陣列A(0)，A(1)，…，A(N-1)按線性關係式

　　(1)

變為 N元數組 x(0)， x(1)，…， x( N-1)的一種線性變換，其中記號 W是一個復常數，滿足

=1，其值為

傳統算法是直接計算(1)，大約需要 N ²次運算(這裡所說的運算每一次包含一個復數乘法和一個復數加法)。1965年，美國人庫利和圖基提出的FFT算法把運算次數縮減為 N log ₂ N。因此，FFT算法比傳統算法提高工效約為 N/ log ₂ N倍。當 N很大時，這是巨量的提高。例如，在圖像處理問題中，一個圖像分為10000×10000個點，因而對所進行的DFT來說，應有 N=10 ⁸，於是用FFT算法提高工效約為10 ¹⁶/(10 ⁸log ₂1 0 ⁸)

3750000倍。如用每秒能作一千萬次運算的電子計算機進行計算，按FFT算法，幾百秒即可完成，若按傳統算法要幾十年才能算完。

　　算法的基本思想　總的來說是利用復常數W的性質把關系式(1)的各項重新組合為新的算式，並使用遞推的步驟，以縮減運算次數。以N=2ⁿ為例，設j₁是j除以

時的餘數，新的算式是

　即先行計算兩個

元數組 Y( j ₁)和 Z( j ₁)，然後再用 2 ⁿ個乘法和2 ⁿ個加法算出2 ⁿ元數組 x( j)。類似地，可把

元數組的計算化為兩個

元數組的計算，等等，如此遞推，最後把計算 M元數組的運算次數記為 T( M)，按上述計算步驟有關系式：

，

，由此可得

。如果 N不是2 ⁿ的形式，而是有分解式

，則可建立運算次數不超過

的FFT算法。

　　在數值計算和實際問題中的應用　上述算法同樣可應用於逆DFT，即從N元數組x(0)，x(1)，…，x(N-1)按線性關系式

變換為數組 A(0)， A(1)，…， A( N-1)。FFT算法在數值計算中的一個重要應用是計算卷積，即從 N元數組 A(0)， A(1)，…， A( N-1)及具有周期 N的數組 B(0)， B(1)，…， B( N-1)( B(-1)= B( N-1)， B(-2)= B( N-2)，…)按關系式

計算 N元數組 C(0)， C(1)，…， C( N-1)。采用如下步驟：首先把兩個數組 A( k)和 B( k)用FFT算法分別得數組 X( j)和 Y( j)，其次作數組（隻需 N個乘法）

Z(j)=X(j)·Y(j)(j=0，1，…，N-1)，

最後用FFT算法把數組 Z( j)作逆DFT，得卷積 C(0)， C(1)，…， C( N-1)。上述算法的運算次數約為3 Nlog ₂ N，而傳統算法則是 N ²。除用於計算卷積外，FFT算法還可用作計算兩個多項式的乘積等等。

　　FFT算法在實際問題中已廣泛應用，在光譜、聲譜、地震譜分析、晶體結構分析、濾波、數字信號處理、圖像信息處理、物探、天線、雷達、衛星攝影分析、全息圖，以及醫療衛生上的心電圖、腦電圖、X光相片強化等等方面，已大量應用，很有發展前途。

　　算法本身的發展近況　近年來，FFT算法本身不斷增添新的內容。在一維DFT的算法方面有：“素因子”法、不要調換排列順序法、修剪法、N為素數的算法、餘弦變換算法、一維DFT的二維處理方法、基底3-FFT的新算法、維諾格拉特算法(這是DFT算法的一個重要進展)以及雷德-佈萊納算法等；二維DFT的算法除以一維FFT為基礎的算法外，也建立瞭若幹直接對二維數組進行運算（分解和變換）的算法。

　　快速數論變換　如上所述，計算卷積要做三次 FFT，這在N很大時的計算量仍然很大。此外，還存在由於舍入誤差而不能得到高精度的卷積以及要貯存三角函數以保證有關