CHP快速傅立葉變換

會計(jì)學(xué)1CHP快速傅立葉變換目錄4.1概述4.2時(shí)間抽?。―IT）基2FFT算法4.3頻率抽?。―IF）基2FFT算法

4.5分裂基算法

4.6線性調(diào)頻Z變換

4.7與本章有關(guān)節(jié)MATLAB文件第1頁/共60頁4.1概述

快速傅里葉變換(FFT)是求解離散傅里葉變換(DFT)的快速算法。問題的提出

直接計(jì)算N點(diǎn)DFT需要的計(jì)算量是多少？

計(jì)算一個X(k)需要N次復(fù)數(shù)乘法和N一1次復(fù)數(shù)加法。算出全部N點(diǎn)X(k)共需N2次復(fù)數(shù)乘法和N(N一1)次復(fù)數(shù)加法.

總運(yùn)算量近似地正比于N2

。當(dāng)N值很大（如2-D圖像處理），運(yùn)算量將非常龐大；同時(shí)，對于實(shí)時(shí)性很強(qiáng)的信號處理來說，必將對計(jì)算速度有十分苛刻的要求。為此，需要改進(jìn)對DFT的計(jì)算方法，以減少總的運(yùn)算次數(shù)。第2頁/共60頁4.1概述在正交矩陣中，雖然有N2個元素，但只有N個不同的值，且有些取值特別簡單，主要由于旋轉(zhuǎn)因子具有如下的特點(diǎn)：對稱性周期性下面以四點(diǎn)DFT為例來說明快速算法的思路。如何充分利用這些關(guān)系？第3頁/共60頁4.1概述第4頁/共60頁4.1概述交換矩陣第二列和第三列得從上面的結(jié)果可以看出,利用對稱性和周期性，求四點(diǎn)DFT只需要一次復(fù)數(shù)乘法，稱為Coolkey-Tukey算法。第5頁/共60頁4.1概述第6頁/共60頁算法分類：N為2的整次冪：按基數(shù)分為基-2FFT算法、基-4FFT算法、混合基FFT算法、分裂基FFT算法;當(dāng)N不是2的整次冪:典型的有Winograd算法.按抽取方法分：時(shí)間抽取(Decimation－in－Time，簡稱DIT)；頻率抽取(Decimation－in－Frequency，簡稱DIF)

4.1概述第7頁/共60頁4.2時(shí)間抽取（DIT）基2FFT算法

為了將大點(diǎn)數(shù)的DFT分解為小點(diǎn)數(shù)的DFT運(yùn)算，要求序列的長度N為N＝2M(M為正整數(shù))。該情況下的變換稱為基2FFT。核心思想是N點(diǎn)DFTN/2點(diǎn)

DFTN/4點(diǎn)

DFT2點(diǎn)

DFT

1個2個4個N/2個問題是如何分最有效？可以對時(shí)間變量分（DIT)，也可對頻率變量分(DIF）第8頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法基本思路：從時(shí)域?qū)點(diǎn)序列x(n)按奇偶項(xiàng)分解為兩組，分別計(jì)算兩組N/2點(diǎn)DFT，然后再合成一個N點(diǎn)DFT，按此方法繼續(xù)下去，直到2點(diǎn)DFT，從而減少運(yùn)算量。算法具體步驟：一、算法的推導(dǎo)1、序列x(n)按奇偶項(xiàng)分解為兩組，將DFT運(yùn)算也相應(yīng)分為兩組則第9頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法2、兩個N/2點(diǎn)的DFT合成一個N點(diǎn)DFT問題：A(k)，B(k)都只有N/2個點(diǎn)，怎樣得到X(k)的后N/2點(diǎn)？利用周期性和對稱性得第10頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法4.2時(shí)間抽?。―IT）基2FFT算法第11頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法3、繼續(xù)分解（一直分解到兩點(diǎn)DFT變換）A(K)和B(K)仍是高復(fù)合數(shù)(N／2)的DFT，我們可按上述方法繼續(xù)以分解。令r＝2l，r＝2l十1，l＝0，1，…，N／4-1，則A(K)和B(K)可分別表示為4.2時(shí)間抽?。―IT）基2FFT算法第12頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法4.2時(shí)間抽?。―IT）基2FFT算法令則第13頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法4.2時(shí)間抽?。―IT）基2FFT算法同理，令則按此方法一直分解下去直到2點(diǎn)DFT，當(dāng)N=8時(shí)，如下：第14頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法4.2時(shí)間抽取（DIT）基2FFT算法第15頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法下面通過討論尋找FFT的一般規(guī)律。二、算法的討論1、“級”的概念在分解過程中，每分一次，稱為一級運(yùn)算。因?yàn)镸=log2N，所以N點(diǎn)DFT可以分解為M級，按抽取算法的信號流圖中來定義，從左到右分別稱為0級、1級到M-1級。第16頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法2、蝶形單元在算法的信號流圖中，第m級存在這種運(yùn)算，這種結(jié)構(gòu)幾何形狀像蝴蝶，稱為蝶形單元p、q是參于本蝶形單元運(yùn)算的上、下節(jié)點(diǎn)的序號。由于第m級序號的兩點(diǎn)只參于這一個蝶形單元的運(yùn)算，其輸出在第m十l級。且這一蝶形單元也不再涉及別的點(diǎn)。由于這一特點(diǎn)，在計(jì)算機(jī)編程時(shí)，我們可將蝶形單元的輸出仍放在輸入數(shù)組中，這一特點(diǎn)稱為“同址運(yùn)算”。第17頁/共60頁4.2時(shí)間抽取（DIT）基2FFT算法4.2時(shí)間抽?。―IT）基2FFT算法第18頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法

由于一級都含有N/2個蝶形單元，每個蝶形單元需要1次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法，因此完成log2N級共需要的復(fù)數(shù)乘法和加法分別為

直接計(jì)算DFT時(shí)所需的復(fù)乘數(shù)與復(fù)加數(shù)都是與N2成正比的。所以采用FFT算法使運(yùn)算量大大減少。顯然，N值愈大，節(jié)省的運(yùn)算量愈多。第19頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法3、“組”的概念在分解過程中，每一級的N/2個蝶形單元可以分成若干組，每一組具有相同的結(jié)構(gòu)和W因子分布。第m級可分成N/2m+1組。第20頁/共60頁例：N=8=23，分3級。第一級的分組及Wr因子如下：m=0級,分成四組：因子為m=1級,分成二組,因子為m=2級,分成一組,因子為4.2時(shí)間抽?。―IT）基2FFT算法4、Wr因子的分布由上分析可知結(jié)論：每由后向前（m由M-1-->0級）推進(jìn)一級，則此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。第21頁/共60頁4.2時(shí)間抽取（DIT）基2FFT算法5、碼位倒置在FFT算法中，輸出的頻譜依照正常次序排列，但輸入的序列x(n)是按奇偶分開的，分開的規(guī)律，以N=8為例，按如下方法進(jìn)行排序（1）、將x(n)的序號寫成二進(jìn)制

x(000),x(001),…,x(110)

，x(111)。（2）將二進(jìn)制的碼進(jìn)行翻轉(zhuǎn)，得

x(000),x(100),…,x(011)

，

x(111)。（3）將二進(jìn)制的翻轉(zhuǎn)碼轉(zhuǎn)換為對應(yīng)的十進(jìn)制

x(0),x(4),…,x(3)，x(7)。這就是按奇偶抽取得到的順序。第22頁/共60頁4.2時(shí)間抽?。―IT）基2FFT算法說明：①在上述的基2FFT算法中，由于每一步分解都是按輸入序列x(n)在時(shí)域上的次序是屬于偶數(shù)還是奇數(shù)來抽取的，所以稱為“按時(shí)間抽取法”或“時(shí)間抽取”。

②上述的基2FFT算法中，抽取也可在頻域進(jìn)行，引出頻率抽?。―IF）基2FFT算法。第23頁/共60頁4.3頻率抽?。―IF）基2FFT算法

設(shè)輸入序列長度為N=2M(M為正整數(shù))，頻率抽取法將輸入序列不是按奇、偶分組，而是按前后對半分開，這樣可將N點(diǎn)DFT寫成前后兩部分;將該序列的頻域的輸出序列X(k)(也是N點(diǎn)序列，按其頻域順序的奇偶分解為越來越短的子序列，稱為基2按頻率抽取的FFT算法。也稱為Sander-Tukey算法。第24頁/共60頁4.3頻率抽?。―IF）基2FFT算法算法分析

現(xiàn)將輸入x(n)按n的順序分前后兩部分:前半子序列x(n),0≤n≤N/2-1;后半子序列x(n+N/2),0≤n≤N/2-1;例：N=8時(shí)，前半序列為：x(0),x(1),x(2),x(3);后半序列為：x(4),x(5),x(6),x(7);考慮N點(diǎn)的DFT,由DFT定義得第25頁/共60頁4.3頻率抽?。―IF）基2FFT算法第26頁/共60頁4.3頻率抽?。―IF）基2FFT算法按k的奇偶將X(k)分成奇偶兩部分,k=2r和k=2r+1,考慮k為偶數(shù)情況令第27頁/共60頁4.3頻率抽?。―IF）基2FFT算法考慮k為奇數(shù)情況令第28頁/共60頁4.3頻率抽?。―IF）基2FFT算法結(jié)論

一個N點(diǎn)的DFT被分解為兩個N/2點(diǎn);與時(shí)間抽取法的推演過程一樣，由于N=2M,因此,N/2仍為偶數(shù)，所以可以將N/2點(diǎn)DFT的輸出X(k)再分為偶數(shù)組和奇數(shù)組，這樣就將一個N/2點(diǎn)的DFT分成兩個N/4點(diǎn)DFT的輸入，也是將N/2點(diǎn)的DFT的輸入上、下對半分后通過蝶形運(yùn)算而形成，直至最后為2點(diǎn)DFT。第29頁/共60頁8點(diǎn)DIF基2FFT算法流圖4.3頻率抽?。―IF）基2FFT算法第30頁/共60頁4.3頻率抽?。―IF）基2FFT算法第31頁/共60頁4.3頻率抽取（DIF）基2FFT算法DIT與DIF的相同之處：（1）DIF與DIT兩種算法均為原位運(yùn)算。（2）DIF與DIT運(yùn)算量相同。DIT與DIF的不同之處：（1）DIF與DIT兩種算法結(jié)構(gòu)倒過來。DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀”程序。DIT為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀”程序，再進(jìn)行求DFT。（2）DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。第32頁/共60頁4.5分裂基算法自從基2快速算法出現(xiàn)以來，人們?nèi)栽诓粩鄬で蟾斓乃惴ā?984年，法國的杜梅爾(P.Dohamel)和霍爾曼(H.Hollmann)將基2分解和基4分解糅合在一起，提出了分裂基FFT算法。其運(yùn)算量比前幾種算法都有所減少，運(yùn)算流圖卻與基2FFT很接近，運(yùn)算程序也很短。它是目前一種實(shí)用的高效新算法。第33頁/共60頁4.5分裂基算法

分裂基算法又稱基2/4算法,算法的基本思路是:對偶號輸出使用基2算法,對奇號輸出使用基4算法。下面首先介紹基4算法：令N=4M，對N點(diǎn)DFT可按下面方法進(jìn)行頻率抽取分別令k=4r，k=4r+2，k=4r+1，k=4r+3，其中，r=0，1，2，…N/4-1，有第34頁/共60頁4.5分裂基算法第35頁/共60頁4.5分裂基算法4.5分裂基算法第36頁/共60頁4.5分裂基算法算法分析對于N=4M點(diǎn)DFT，當(dāng)輸出項(xiàng)k為偶數(shù)時(shí)，采用基2算法，即當(dāng)輸出項(xiàng)k為奇數(shù)時(shí)，采用基4算法，即第37頁/共60頁4.5分裂基算法第38頁/共60頁4.5分裂基算法第39頁/共60頁4.5分裂基算法分析：一個N點(diǎn)DFT可以分解為一個N/2點(diǎn)DFT和兩個N/4點(diǎn)DFT。由x(n)x(n+N/4)x(n+N/2)和x(n+3N/4)求N/2點(diǎn)DFT和N/4的DFT只需要兩次乘法，可以減少運(yùn)算量。

N/2點(diǎn)DFT可進(jìn)一步分解為一個N/4點(diǎn)DFT和兩個N/8的DFT。N/4的點(diǎn)DFT進(jìn)一步分解為一個N/8點(diǎn)DFT和兩個N/16的DFT。

這樣一直下去，直到分解為兩點(diǎn)或4點(diǎn)DFT為止。第40頁/共60頁4.5分裂基算法結(jié)論：分裂基FFT算法結(jié)構(gòu)同基2FFT算法結(jié)構(gòu)相似，適用于N=2M的場合，并由M級運(yùn)算實(shí)現(xiàn)。運(yùn)算流圖輸入為順序，輸出為倒序。分裂基FFT算法的計(jì)算量第41頁/共60頁

以上提出FFT算法，可以很快地求出全部DFT值。即求出有限長序列x(n)的z變換X(z)在單位園上N個等間隔抽樣點(diǎn)zk處的抽樣值。它要求N為高度復(fù)合數(shù)。即N可以分解成一些因子的乘積。例N=2L

實(shí)際上：（1）也許對其它圍線上z變換取樣發(fā)生興趣。如語音處理中，常常需要知道某一圍線z變換的極點(diǎn)所處的復(fù)頻率。（2）只需要計(jì)算單位圓上某一段的頻譜,即M不等于N。如窄帶信號，希望在窄帶頻率內(nèi)頻率抽樣能夠非常密集，提高分辨率，帶外則不考慮。（3）若N是大素?cái)?shù)時(shí)，不能加以分解，又如何有效計(jì)算這種序列DFT。例N=311，若用基2則須補(bǔ)N=28=512點(diǎn)，要補(bǔ)211個零點(diǎn)。4.6線性調(diào)頻Z變換第42頁/共60頁4.6線性調(diào)頻Z變換問題提出為了提高DFT的靈活性，須用新的方法。線性調(diào)頻z變換(CZT)就是適用這種更為一般情況下，由x(n)求X(zk)的快速變換。CZT

來自于雷達(dá)專業(yè)的專用詞匯。Z變換采用螺線抽樣,可計(jì)算單位圓上任一段曲線的Z變換，適用于更一般情況下（M不等于N）由x(n)求X(zr)的快速算法,達(dá)到頻域細(xì)化的目的，這種變換稱為線性調(diào)頻Z變換(簡稱CZT)。第43頁/共60頁

為適應(yīng)z可以沿平面內(nèi)更一般的路徑取值，我們沿z平面上的一段螺線作等分角的抽樣，則z的取樣點(diǎn)Zr可表示為：

已知N點(diǎn)序列x(n)，0≤n≤N-1,其z變換為其中M：表示欲分析的復(fù)頻譜的點(diǎn)數(shù)。M不一定等于N。A，W都為任意復(fù)數(shù),令

4.6線性調(diào)頻Z變換一、CZT的定義第44頁/共60頁4.6線性調(diào)頻Z變換上式即為CZT的定義.現(xiàn)在討論A0,W0,θ0,φ0的含義:為輸出M點(diǎn)的變換域值.r=0時(shí)的A0ejθ0是CZT的起點(diǎn),隨著r的變化,r0,r1,…,RM-1構(gòu)成CZT的變化路徑，對于M-1點(diǎn)其極坐標(biāo)為第45頁/共60頁4.6線性調(diào)頻Z變換第46頁/共60頁4.6線性調(diào)頻Z變換CZT在現(xiàn)Z平面上的變換路徑是一條螺旋線。（1）A為起始樣點(diǎn)位置起點(diǎn)半徑，大于1時(shí)，表示螺旋線在單位圓外，反之，在單位圓內(nèi)。起點(diǎn)半相角。（2）當(dāng)W0>1,螺旋線內(nèi)旋，反之外旋。（3）當(dāng)A0=W0=1時(shí)，CZT的變換路徑為單位圓上的一段弧，起點(diǎn)為P，終點(diǎn)為Q，且M不一定等于N。第47頁/共60頁4.6線性調(diào)頻Z變換第48頁/共60頁4.6線性調(diào)頻Z變換

考慮A0=W0=1時(shí)，在單位圓上CZT，且M不一定等于N。第49頁/共60頁4.6線性調(diào)頻Z變換第50頁/共60頁4.6線性調(diào)頻Z變換CZT的線性濾波計(jì)算步驟第51頁/共60頁4.6線性調(diào)頻Z變換二、CZT的計(jì)算方法分析：從上面的推導(dǎo)過程可以看出，計(jì)算CZT關(guān)鍵是計(jì)算一個線性卷積其中，g(n)應(yīng)為N點(diǎn)序列，h(n)應(yīng)為偶對稱的無限長序列，考慮到輸出M點(diǎn)序列，h(n)的實(shí)際長度應(yīng)為M點(diǎn)。因此，可用DFT來實(shí)現(xiàn)兩者的卷積，具體步驟如下：第52頁/共60頁4.6線性調(diào)頻Z變換（1）計(jì)算并設(shè)置g(n)第53頁/共60頁4.6線性調(diào)頻Z變換（2）計(jì)算并設(shè)置h(n)將h(n)設(shè)置成長度為L的序列，考慮到其為偶對稱序列，且取M點(diǎn)（輸出M點(diǎn)序列），取如下圖所示第54頁/共60頁4.6線性調(diào)頻Z