微型致冷器
[拼音]：kuaisu Fuliye bianhuan
[英文]：fast Fourier transform
計算離散傅立葉變換的一種快速演算法，簡稱FFT。快速傅立葉變換是1965年由J.W.庫利和T.W.圖基提出的。採用這種演算法能使計算機計算離散傅立葉變換所需要的乘法次數大為減少，特別是被變換的抽樣點數N越多，FFT演算法計算量的節省就越顯著。
當用數字計算機計算訊號序列x(n)的離散傅立葉變換時，它的正變換
(1)
反變換(IDFT)是
(2)
式中
、x(n)和X(k)可以是實數或複數。由上式可見，要計算一個抽樣序列就需要做N次複數乘法運算及N-1次複數加法運算。
計算離散傅立葉變換的快速方法，有按時間抽取的FFT演算法和按頻率抽取的FFT演算法。前者是將時域訊號序列按偶奇分排，後者是將頻域訊號序列按偶奇分排。它們都藉助於
的兩個特點:一是
的週期性；另一是
的對稱性，這裡符號*代表其共軛。這樣，便可以把離散傅立葉變換的計算分成若干步進行，計算效率大為提高。
時間抽取演算法
令訊號序列的長度為N＝2M，其中M是正整數，可以將時域訊號序列x(n)分解成兩部分，一是偶數部分x（2n），另一是奇數部分x（2n+1），其中
。於是訊號序列x(n)的離散傅立葉變換可以用兩個 N/2抽樣點的離散傅立葉變換來表示和計算。考慮到
和離散傅立葉變換的週期性，式(1)可以寫成
(3)
其中
(4a)
(4b)
由此可見，式(4)是兩個只含有N/2個點的離散傅立葉變換，G(k)僅包括原訊號序列中的偶數點序列，H(k)則僅包括它的奇數點序列。雖然k=0，1，2，…，N-1，但是G(k)和H(k)的週期都是N/2，它們的數值以N/2週期重複。
因為
於是由式(3)和式(4)得到
(5a)
(5b)
因此，一個抽樣點數為N 的訊號序列 x(n)的離散傅立葉變換，可以由兩個 N/2抽樣點序列的離散傅立葉變換求出。依此類推，這種按時間抽取演算法是將輸入訊號序列分成越來越小的子序列進行離散傅立葉變換計算，最後合成為N點的離散傅立葉變換。
通常用圖1中蝶形演算法的訊號流圖來表示式(5)的離散傅立葉變換運算。例如，N＝8＝23的抽樣點的訊號序列x(n)的離散傅立葉變換，可用如圖2所示的FET演算法的訊號流圖來計算。由圖可知
（1）N=2M點的離散傅立葉變換的計算全由蝶形運算組成，需要M級運算，每級包括N/2個蝶形運算，總共有
個蝶形運算。所以，總的計算量為
次複數乘法運算和N log2N次複數加法運算。
（2）FFT演算法按級迭代進行，計算公式可以寫成
(6)
N抽樣點的輸入訊號具有N個原始資料x0(n)，經第一級運算後，得出新的N個數據x1(n)，再經過第二級迭代運算，又得到另外N個數據x2(n)，依此類推，直至最後的結果x
(k)＝xM(k)＝X(k)在逐級迭代計算中，每個蝶形運算的輸出資料存放在原來存貯輸入資料的單元中，實行所謂“即位計算”，這樣可以節省大量存放中間資料的暫存器。
（3）蝶形運算中加權係數
隨迭代級數成倍增加。由圖2可以看出係數
的變化規律。對於N=8，M=3情況，需進行三級迭代運算。在第一級迭代中，只用到一種加權係數
;蝶形運算的跨度間隔等於1。在第二級迭代中，用到兩種加權係數即
、
；蝶形運算的跨度間隔等於2。在第三級迭代中，用到4種不同的加權係數即
、
、
、
；蝶形運算的跨度間隔等於4。可見，每級迭代的不同加權係數的數目比前一級迭代增加一倍；跨度間隔也增大一倍。
（4）輸入資料序列x(n)需重新排列為x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)，這是按照二進位制數的碼位倒置所得到的反序數，例如N=8中數“1”的二進位制數為“001”，將其碼位倒轉變為“100”，即為十進位制數“4”。
頻率抽取演算法
按頻率抽取的 FFT演算法是將頻域訊號序列X(k)分解為奇偶兩部分，但演算法仍是由時域訊號序列開始逐級運算，同樣是把 N點分成N/2點計算FFT，可以把直接計算離散傅立葉變換所需的N2次乘法縮減到
次。
在N＝2
的情況下，把N點輸入序列x(n)分成前後兩半
(7)
時間序列x1(n)±x2(n)的長度為N/2， 於是N點的離散傅立葉變換可以寫成
(8a)
(8b)
頻率訊號序列X(2l)是時間訊號序列x1(n)+x2(n)的N/2點離散傅立葉變換，頻率訊號序列X(2l+1)是時間訊號序列[x1(n)-x2(n)]
的N/2點離散傅立葉變換，因此，N點離散傅立葉變換的計算，通過兩次加（減）法和一次乘法，從原來序列獲得兩個子序列，所以，頻率抽取演算法也具有蝶形運算形式。以2為基數的FFT基本蝶形運算公式為
(9)
其計算量完全和時間抽取演算法一樣，即只需
次乘法運算和Nlog2N次加(減)法運算。圖3 表示N=8=23點的離散傅立葉變換的訊號流圖。由圖可見，它以三級迭代進行即位計算，輸入資料是按自然次序存放，使用的係數也是按自然次序，而最後結果則以二進位制反序存放。
實際上，頻率抽取演算法與時間抽取演算法的訊號流圖之間存在著轉置關係，如將流圖適當變形，可以得出多種幾何形狀。
除了基2的FFT演算法之外，還有基4、基8等高基數的FFT演算法以及任意數為基數的FFT演算法。
參考書目
何振亞著：《數字訊號處理的理論與應用》下冊，人民郵電出版社，北京，1983。
E.O.布里漢著，柳群譯：《快速傅立葉變換》，上海科學技術出版社，1979。（E. O. Brigham， TheFast Fourier Transform，Prentice Hall，Englewood Cliffs，New Jersey，1974.）