地塹

[拼音]：kuaisu Fuliye bianhuan

[英文]：fast Fourier transformation

簡稱FFT，是指進行“有限離散傅立葉變換”(簡稱DFT)的快速演算法。一維DFT是把N元陣列

A

(0)，

A

(1)，…，

A

(N-1)按線性關係式

(1)

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

=1，其值為

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

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

演算法的基本思想

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

時的餘數，新的算式是

即先行計算兩個

元陣列Y(j1)和Z(j1)，然後再用2n個乘法和2n個加法算出2n元陣列x(j)。類似地，可把

元陣列的計算化為兩個

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

，

，由此可得

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

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

C

(0)，

C

(1)，…，

C

(N-1)。上述演算法的運算次數約為3Nlog2N，而傳統演算法則是N 2。除用於計算卷積外，FFT演算法還可用作計算兩個多項式的乘積等等。

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

演算法本身的發展近況

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