快速傅裡葉變換:數字信号處理-中文百科頻道

計算方法

計算離散傅裡葉變換的快速方法，有按時間抽取的FFT算法和按頻率抽取的FFT算法。前者是将時域信号序列按偶奇分排，後者是将頻域信号序列按偶奇分排。它們都借助于的兩個特點：一是周期性；二是對稱性，這裡符号*代表其共轭。這樣，便可以把離散傅裡葉變換的計算分成若幹步進行，計算效率大為提高。

時間抽取算法

令信号序列的長度為N=2,其中M是正整數，可以将時域信号序列x(n)分解成兩部分，一是偶數部分x（2n），另一是奇數部分x（2n+1），于是信号序列x(n）的離散傅裡葉變換可以用兩個N/2抽樣點的離散傅裡葉變換來表示和計算。考慮到和離散傅裡葉變換的周期性，式⑴可以寫成

⑶其中（4a）（4b）由此可見，式⑷是兩個隻含有N/2個點的離散傅裡葉變換，G(k）僅包括原信号序列中的偶數點序列，H(k）則僅包括它的奇數點序列。雖然k=0，1，2，…，N-1，但是G(k）和H(k）的周期都是N/2，它們的數值以N/2周期重複。

因為于是由式⑶和式⑷得到（5a）（5b)

因此，一個抽樣點數為N 的信号序列x(n）的離散傅裡葉變換，可以由兩個 N/2抽樣點序列的離散傅裡葉變換求出。依此類推，這種按時間抽取算法是将輸入信号序列分成越來越小的子序列進行離散傅裡葉變換計算，最後合成為N點的離散傅裡葉變換。

通常用圖1中蝶形算法的信号流圖來表示式⑸的離散傅裡葉變換運算。例如，N=8=2的抽樣點的信号序列x(n）的離散傅裡葉變換，可用如圖2所示的FET算法的信号流圖來計算。

①N=2點的離散傅裡葉變換的計算全由蝶形運算組成，需要M級運算，每級包括N/2個蝶形運算，總共有個蝶形運算。所以，總的計算量為次複數乘法運算和N log2N次複數加法運算。

②FFT算法按級叠代進行，計算公式可以寫成

⑹N抽樣點的輸入信号具有N個原始數據x0(n），經第一級運算後，得出新的N個數據x1(n），再經過第二級叠代運算，又得到另外N個數據x2(n），依此類推，直至最後的結果x(k)=xM(k)=X(k）在逐級叠代計算中，每個蝶形運算的輸出數據存放在原來存貯輸入數據的單元中，實行所謂“即位計算”，這樣可以節省大量存放中間數據的寄存器。

③蝶形運算中加權系數随叠代級數成倍增加。由圖2可以看出系數的變化規律。對于N=8,M=3情況，需進行三級叠代運算。在第一級叠代中，隻用到一種加權系數；蝶形運算的跨度間隔等于1。在第二級叠代中，用到兩種加權系數即、；蝶形運算的跨度間隔等于2。在第三級叠代中，用到4種不同的加權系數即、、、；蝶形運算的跨度間隔等于4。可見，每級叠代的不同加權系數的數目比前一級叠代增加一倍；跨度間隔也增大一倍。

④輸入數據序列x(n）需重新排列為x(0）、x⑷、x⑵、x⑹、x⑴、x⑸、x⑶、x⑺，這是按照二進制數的碼位倒置所得到的反序數，例如N=8中數“1”的二進制數為“001”，将其碼位倒轉變為“100”，即為十進制數“4”。

頻率抽取算法

按頻率抽取的 FFT算法是将頻域信号序列X(k）分解為奇偶兩部分，但算法仍是由時域信号序列開始逐級運算，同樣是把N點分成N/2點計算FFT，可以把直接計算離散傅裡葉變換所需的N次乘法縮減到次。

在N=2的情況下，把N點輸入序列x(n）分成前後兩半

⑺時間序列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基本蝶形運算公式為

⑼

其計算量完全和時間抽取算法一樣，即隻需次乘法運算和Nlog2N次加（減）法運算。圖3 表示N=8=2點的離散傅裡葉變換的信号流圖。由圖可見，它以三級叠代進行即位計算，輸入數據是按自然次序存放，使用的系數也是按自然次序，而最後結果則以二進制反序存放。

實際上，頻率抽取算法與時間抽取算法的信号流圖之間存在着轉置關系，如将流圖适當變形，可以得出多種幾何形狀。

除了基2的FFT算法之外，還有基4、基8等高基數的FFT算法以及任意數為基數的FFT算法。

應用

計算量小的顯着的優點，使得FFT在信号處理技術領域獲得了廣泛應用，結合高速硬件就能實現對信号的實時處理。例如，對語音信号的分析和合成，對通信系統中實現全數字化的時分制與頻分制(TDM/FDM)的複用轉換，在頻域對信号濾波以及相關分析，通過對雷達、聲納、振動信号的頻譜分析以提高對目标的搜索和跟蹤的分辨率等等，都要用到FFT。可以說FFT的出現，對數字信号處理學科的發展起了重要的作用。