快速傅里葉變換

1、第四章 快速傅里葉變換 有限長序列可以通過離散傅里葉變換(DFT)將其頻域也離散化成有限長序列.但其計算量太大,很難實時地處理問題,因此引出了快速傅里葉變換(FFT). 1965年，Cooley和Tukey提出了計算離散傅里葉變換（DFT）的快速算法，將DFT的運(yùn)算量減少了幾個數(shù)量級。從此，對快速傅里葉變換（FFT）算法的研究便不斷深入，數(shù)字信號處理這門新興學(xué)科也隨FFT的出現(xiàn)和發(fā)展而迅速發(fā)展。根據(jù)對序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法，基本算法是基DIT和基DIF。FFT在離散傅里葉反變換、線性卷積和線性相關(guān)等方面也有重要應(yīng)用?？焖俑道锶~變換（FFT）是計算離散傅里葉變換（DFT

2、）的快速算法。 DFT的定義式為=在所有復(fù)指數(shù)值的值全部已算好的情況下，要計算一個需要N次復(fù)數(shù)乘法和N1次復(fù)數(shù)加法。算出全部N點(diǎn)共需次復(fù)數(shù)乘法和次復(fù)數(shù)加法。即計算量是與成正比的。FFT的基本思想：將大點(diǎn)數(shù)的DFT分解為若干個小點(diǎn)數(shù)DFT的組合，從而減少運(yùn)算量。因子具有以下兩個特性，可使DFT運(yùn)算量盡量分解為小點(diǎn)數(shù)的DFT運(yùn)算：（1） 周期性：（2） 對稱性：利用這兩個性質(zhì)，可以使DFT運(yùn)算中有些項合并，以減少乘法次數(shù)。例子：求當(dāng)N4時，X(2)的值 通過合并，使乘法次數(shù)由4次減少到1次，運(yùn)算量減少。FFT的算法形式有很多種，但基本上可以分為兩大類：按時間抽?。―IT）和按頻率抽取（DIF）。4

3、.1 按時間抽?。―IT）的FTT 為了將大點(diǎn)數(shù)的DFT分解為小點(diǎn)數(shù)的DFT運(yùn)算，要求序列的長度N為復(fù)合數(shù)，最常用的是的情況（M為正整數(shù)）。該情況下的變換稱為基2FFT。下面討論基2情況的算法。 先將序列x(n)按奇偶項分解為兩組 將DFT運(yùn)算也相應(yīng)分為兩組 （因為）其中、分別是的N/2點(diǎn)的DFT至此，一個N點(diǎn)DFT被分解為兩個N/2點(diǎn)的DFT。 上面是否將全部N點(diǎn)的求解出來了？分析：和只有N/2個點(diǎn)（），則由只能求出的前N/2個點(diǎn)的DFT，要求出全部N點(diǎn)的，需要找出、和的關(guān)系，其中。由式子可得化簡得，這樣N點(diǎn)DFT可全部由下式確定出來： （）上式可用一個專用的碟形符號來表示，這個符號對應(yīng)一次

4、復(fù)乘和兩次復(fù)加運(yùn)算。圖蝶形運(yùn)算符號通過這樣的分解以后，每一個N2點(diǎn)的DFT只需要次復(fù)數(shù)乘法，兩個N/2點(diǎn)的DFT需要次復(fù)乘，再加上將兩個N2點(diǎn)DFT合并成為N點(diǎn)DFT時有N2次與W因子相乘，一共需要次復(fù)乘?？梢?，通過這樣的分解，運(yùn)算量節(jié)省了近一半。因為，N/2仍然是偶數(shù)，因此可以對兩個N/2點(diǎn)的DFT再分別作進(jìn)一步的分解，將兩個N/2點(diǎn)的DFT分解成兩個N/4點(diǎn)的DFT。例如對，可以在按其偶數(shù)部分及奇數(shù)部分進(jìn)行分解： 則的運(yùn)算可相應(yīng)分為兩組： 將系數(shù)統(tǒng)一為以為周期，即，可得 同樣，對也可進(jìn)行類似的分解。一直分解下去，最后是點(diǎn)的DFT，點(diǎn)DFT的運(yùn)算也可用碟形符號來表示。這樣，對于一個的DFT運(yùn)

5、算，其按時間抽取的分解過程及完整流圖如下圖所示。這種方法，由于每一步分解都是按輸入序列在時域上的次序是屬于偶數(shù)還是奇數(shù)來抽取的，故稱為“時間抽取法”。分析上面的流圖，一共要進(jìn)行M次分解，構(gòu)成了從x(n)到X(k)的M級運(yùn)算過程。每一級運(yùn)算都是由N/2個蝶形運(yùn)算構(gòu)成，因此每一級運(yùn)算都需要N/2次復(fù)乘和N次復(fù)加，則按時間抽取的M級運(yùn)算后總共需要復(fù)數(shù)乘法次數(shù)：復(fù)數(shù)加法次數(shù)：根據(jù)上面的流圖，分析算法的兩個特點(diǎn)，它們對的軟硬件構(gòu)成產(chǎn)生很大的影響。（） 原位運(yùn)算也稱為同址運(yùn)算，當(dāng)數(shù)據(jù)輸入到存儲器中以后，每一級運(yùn)算的結(jié)果仍然存儲在原來的存儲器中，直到最后輸出，中間無需其它的存儲器。根據(jù)運(yùn)算流圖分析原位運(yùn)算是

6、如何進(jìn)行的。原位運(yùn)算的結(jié)構(gòu)可以節(jié)省存儲單元，降低設(shè)備成本。（） 變址分析運(yùn)算流圖中的輸入輸出序列的順序，輸出按順序，輸入是“碼位倒置”的順序。見圖。自然順序二進(jìn)制表示碼位倒置碼位倒置順序0000000010011004201001023011110641000011510110156110011371111117碼位倒置順序在實際運(yùn)算中，直接將輸入數(shù)據(jù)x(n)按碼位倒置的順序排好輸入很不方便，一般總是先按自然順序輸入存儲單元，然后通過變址運(yùn)算將自然順序的存儲換成碼位倒置順序的存儲，這樣就可以進(jìn)行FFT的原位運(yùn)算。變質(zhì)的功能如圖所示。用軟件實現(xiàn)是通用采用雷德（Rader）算法，算出I的倒序以后立

7、即將輸入數(shù)據(jù)X(I)和X(J)對換。盡管變址運(yùn)算所占運(yùn)算量的比例很小，但對某些高要求的應(yīng)用（尤其在實時信號處理中），也可設(shè)法用適當(dāng)?shù)碾娐方Y(jié)構(gòu)直接實現(xiàn)變址。例如單片數(shù)字信號處理器TMS320C25就有專用于FFT的二進(jìn)制碼變址模式。4. 按頻率抽取（DIF）的FTT除時間抽取法外，另外一種普遍使用的FFT結(jié)構(gòu)是頻率抽取法。頻率抽取法將輸入序列不是按奇、偶分組，而是將點(diǎn)DFT寫成前后兩部分： 因為，k為偶數(shù)時，k為奇數(shù)時，由此可將X(k)分解為偶數(shù)組和奇數(shù)組：令這兩個序列都是N/2點(diǎn)的序列，對應(yīng)的是兩個N/2點(diǎn)的DFT運(yùn)算：這樣，同樣是將一個N點(diǎn)的DFT分解為兩個N/2點(diǎn)的DFT了。頻率抽選法對應(yīng)

8、的碟形運(yùn)算關(guān)系圖如下：對于N=8時頻率抽取法的FFT流圖如下：這種分組的辦法由于每次都是按輸出X(k)在頻域的順序上是屬于偶數(shù)還是奇數(shù)來分組的，稱為頻率抽取法。與前面按時間抽取的方法相比，相同點(diǎn)問題：如何利用快速算法計算IDFT？分析IDFT的公式：比較DFT的公式：得知可用兩種方法來實現(xiàn)IDFT的快速算法：（）只要把DFT運(yùn)算中的每一個系數(shù)該為，并且最后再乘以常數(shù)，就可以用時間抽取法或頻率抽取的FFT算法來直接計算IDFT。這種方法需要對FFT的程序和參數(shù)稍加改動才能實現(xiàn)。（）因為，也就是說，可先將X(k)取共軛變換，即將X(k)的虛部乘以，就可直接調(diào)用FFT的程序，最后再對運(yùn)算結(jié)果取一次共

9、軛變換并乘以常數(shù)1/N即可得到x(n)的值。這種方法中，F(xiàn)FT運(yùn)算和IFFT運(yùn)算都可以共用一個子程序塊，在使用通用計算機(jī)或用硬件實現(xiàn)時比較方便。4.1.3 混合基FFT算法以上討論的是基2的FFT算法，即的情況，這種情況實際上使用得最多，這種FFT運(yùn)算，程序簡單，效率很高，用起來很方便。另外，在實際應(yīng)用時，有限長序列的長度N到底是多少在很大程度時是由人為因素確定的，因此，大多數(shù)場合人們可以將N選定為，從而可以直接調(diào)用以為基數(shù)的FFT運(yùn)算程序。如果長度N不能認(rèn)為確定，而N的數(shù)值又不是以2為基數(shù)的整數(shù)次方，一般可有以下兩種處理方法：（） 將x(n)用補(bǔ)零的方法延長，使N增長到最鄰近的一個數(shù)值。例如

10、，N=30，可以在序列x(n)中補(bǔ)進(jìn)x(30)x(31)兩個零值點(diǎn)，使N=32。如果計算FFT的目的是為了了解整個頻譜，而不是特定頻率點(diǎn)，則此法可行。因為有限長序列補(bǔ)零以后并不影響其頻譜，只是頻譜的采樣點(diǎn)數(shù)增加而已。（） 如果要求特定頻率點(diǎn)的頻譜，則N不能改變。如果N為復(fù)合數(shù)，則可以用以任意數(shù)為基數(shù)的FFT算法來計算。快速傅里葉變換的基本思想就是要將DFT的運(yùn)算盡量分小。例如，N=6時，可以按照N=3×分解，將點(diǎn)DFT分解為組點(diǎn)DFT。舉例：N=9時的快速算法。4.2 快速傅里葉變換的應(yīng)用凡是可以利用傅里葉變換來進(jìn)行分析、綜合、變換的地方，都可以利用FFT算法及運(yùn)用數(shù)字計算技術(shù)加以實

11、現(xiàn)。FFT在數(shù)字通信、語音信號處理、圖像處理、匹配濾波以及功率譜估計、仿真、系統(tǒng)分析等各個領(lǐng)域都得到了廣泛的應(yīng)用。但不管FFT在哪里應(yīng)用，一般都以卷積積分或相關(guān)積分的具體處理為依據(jù)，或者以用FFT作為連續(xù)傅里葉變換的近似為基礎(chǔ)。4.2.1 利用FFT求線性卷積快速卷積在實際中常常遇到要求兩個序列的線性卷積。如一個信號序列x(n)通過FIR濾波器時，其輸出y(n)應(yīng)是x(n)與h(n)的卷積：有限長序列x(n)與h(n)的卷積的結(jié)果y(n)也是一個有限長序列。假設(shè)x(n)與h(n)的長度分別為N1和N2，則y(n)的長度為N=N1+N2-1。若通過補(bǔ)零使x(n)與h(n)都加長到N點(diǎn)，就可以用圓

12、周卷積來計算線性卷積。這樣得到用FFT運(yùn)算來求y(n)值（快速卷積）的步驟如下：（） 對序列x(n)與h(n)補(bǔ)零至長為N，使NN1+N2-1，并且，即（） 用FFT計算x(n)與h(n)的離散傅里葉變換（N點(diǎn)）（N點(diǎn)）（） 計算Y(k)=X(k)H(k)（） 用IFFT計算Y(k)的離散傅里葉反變換得：y(n)=IFFTY(k)（N點(diǎn)）4.2.2 利用FFT求相關(guān)快速相關(guān)互相關(guān)及自相關(guān)的運(yùn)算已廣泛的應(yīng)用于信號分析與統(tǒng)計分析，應(yīng)用于連續(xù)時間系統(tǒng)也用于離散事件系統(tǒng)。用FFT計算相關(guān)函數(shù)稱為快速相關(guān)，它與快速卷積完全類似，不同的是一個應(yīng)用離散相關(guān)定理，另一個應(yīng)用離散卷積定理。同樣都要注意到離散傅里

13、葉變換固有的周期性，也同樣用補(bǔ)零的方法來繞過這個障礙。設(shè)兩個離散時間信號x(n)與y(n)為已知，離散互相關(guān)函數(shù)記作，定義為如果x(n)與y(n)的序列長度分別為N1和N2，則用FFT求相關(guān)的計算步驟如下：（）對序列x(n)與y(n)補(bǔ)零至長為N，使NN1+N2-1，并且，即（）用FFT計算x(n)與y(n)的離散傅里葉變換（N點(diǎn)）（N點(diǎn)）（）將X(k)的虛部ImX(k)改變符號，求得其共軛X*(k)（）計算=X*(k)Y(k)（） 用IFFT求得相關(guān)序列IFFT（N點(diǎn)）如果x(n)y(n)，則求得的是自相關(guān)序列4.2.3 ChirpZ變換采用FFT算法可以很快的計算出全部DFT值，也即Z變換

14、在單位圓上的全部等間隔采樣值。但是，很多場合下，并非整個單位圓上的頻譜都是很有意義的，例如對于窄帶信號過程，往往只需要對信號所在的一段頻帶進(jìn)行分析，這是，希望采樣能密集在這段頻帶內(nèi)，而對頻帶以外的部分，則可以完全不管。另外，有時也希望采樣能不局限于單位圓上，例如，語音信號處理中，往往需要知道其Z變換的極點(diǎn)所在頻率，如果極點(diǎn)位置離單位圓較遠(yuǎn)，則其單位圓上的頻譜就很平滑，如圖所示，這是很難從中識別出極點(diǎn)所在的頻率。要是采樣不是沿單位圓而是沿一條接近這些極點(diǎn)的弧線進(jìn)行，則所得的結(jié)果將會在極點(diǎn)所在頻率上出現(xiàn)明顯的尖峰，從而可以較準(zhǔn)確的測定極點(diǎn)頻率。螺線采樣就是一種適用于這種需要的變換，并且可以采用FFT