快速傅里葉變換

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

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

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

4、復(fù)乘和兩次復(fù)加運(yùn)算。圖蝶形運(yùn)算符號(hào)通過這樣的分解以后，每一個(gè)N2點(diǎn)的DFT只需要次復(fù)數(shù)乘法，兩個(gè)N/2點(diǎn)的DFT需要次復(fù)乘，再加上將兩個(gè)N2點(diǎn)DFT合并成為N點(diǎn)DFT時(shí)有N2次與W因子相乘，一共需要次復(fù)乘?？梢?，通過這樣的分解，運(yùn)算量節(jié)省了近一半。因?yàn)?，N/2仍然是偶數(shù)，因此可以對兩個(gè)N/2點(diǎn)的DFT再分別作進(jìn)一步的分解，將兩個(gè)N/2點(diǎn)的DFT分解成兩個(gè)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)算也可用碟形符號(hào)來表示。這樣，對于一個(gè)的DFT運(yùn)

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

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

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

8、的碟形運(yùn)算關(guān)系圖如下：對于N=8時(shí)頻率抽取法的FFT流圖如下：這種分組的辦法由于每次都是按輸出X(k)在頻域的順序上是屬于偶數(shù)還是奇數(shù)來分組的，稱為頻率抽取法。與前面按時(shí)間抽取的方法相比，相同點(diǎn)問題：如何利用快速算法計(jì)算IDFT？分析IDFT的公式：比較DFT的公式：得知可用兩種方法來實(shí)現(xiàn)IDFT的快速算法：（）只要把DFT運(yùn)算中的每一個(gè)系數(shù)該為，并且最后再乘以常數(shù)，就可以用時(shí)間抽取法或頻率抽取的FFT算法來直接計(jì)算IDFT。這種方法需要對FFT的程序和參數(shù)稍加改動(dòng)才能實(shí)現(xiàn)。（）因?yà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)算都可以共用一個(gè)子程序塊，在使用通用計(jì)算機(jī)或用硬件實(shí)現(xiàn)時(shí)比較方便。4.1.3 混合基FFT算法以上討論的是基2的FFT算法，即的情況，這種情況實(shí)際上使用得最多，這種FFT運(yùn)算，程序簡單，效率很高，用起來很方便。另外，在實(shí)際應(yīng)用時(shí)，有限長序列的長度N到底是多少在很大程度時(shí)是由人為因素確定的，因此，大多數(shù)場合人們可以將N選定為，從而可以直接調(diào)用以為基數(shù)的FFT運(yùn)算程序。如果長度N不能認(rèn)為確定，而N的數(shù)值又不是以2為基數(shù)的整數(shù)次方，一般可有以下兩種處理方法：（） 將x(n)用補(bǔ)零的方法延長，使N增長到最鄰近的一個(gè)數(shù)值。例如

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

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

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

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

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