CHP4快速傅立葉變換（經(jīng)典實(shí)用）

1、CHP4快速傅立葉變換物電學(xué)院CHP4快速傅立葉變換4.1概述概述4.2時(shí)間抽?。〞r(shí)間抽?。―IT）基）基2FFT算法算法4.3頻率抽?。l率抽取（DIF）基）基2FFT算法算法4.5分裂基算法分裂基算法4.6線性調(diào)頻線性調(diào)頻Z變換變換4.7與本章有關(guān)節(jié)與本章有關(guān)節(jié)MATLAB文件文件CHP4快速傅立葉變換 快速傅里葉變換快速傅里葉變換(FFT)(FFT)是求解離散傅里葉變換是求解離散傅里葉變換(DFT)(DFT)的快速算法。的快速算法。問題的提出問題的提出 直接計(jì)算直接計(jì)算N N點(diǎn)點(diǎn)DFTDFT需要的計(jì)算量是多少？需要的計(jì)算量是多少？ 計(jì)算一個(gè)計(jì)算一個(gè)X(k)X(k)需要需要N N次復(fù)數(shù)乘法

2、和次復(fù)數(shù)乘法和N N一一1 1次復(fù)數(shù)次復(fù)數(shù)加法。算出全部加法。算出全部N N點(diǎn)點(diǎn)X(k)X(k)共需共需N N2 2次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和N(NN(N一一1)1)次復(fù)數(shù)加法次復(fù)數(shù)加法. . 總運(yùn)算量近似地正比于總運(yùn)算量近似地正比于N N2 2 。當(dāng)。當(dāng)N N值很大（如值很大（如2-D2-D圖像處理），運(yùn)算量將非常龐大；同時(shí)，對于圖像處理），運(yùn)算量將非常龐大；同時(shí)，對于實(shí)時(shí)性很強(qiáng)的信號處理來說，必將對計(jì)算速度有實(shí)時(shí)性很強(qiáng)的信號處理來說，必將對計(jì)算速度有十分苛刻的要求。為此，需要改進(jìn)對十分苛刻的要求。為此，需要改進(jìn)對DFTDFT的計(jì)算方的計(jì)算方法，以減少總的運(yùn)算次數(shù)。法，以減少總的運(yùn)算次數(shù)。CH

3、P4快速傅立葉變換在正交矩陣中，雖然有在正交矩陣中，雖然有N N2 2個(gè)元素，但只有個(gè)元素，但只有N N個(gè)不同個(gè)不同的值，且有些取值特別簡單，主要由于旋轉(zhuǎn)因子具的值，且有些取值特別簡單，主要由于旋轉(zhuǎn)因子具有如下的特點(diǎn)：有如下的特點(diǎn)：對稱性對稱性周期性周期性下面以四點(diǎn)下面以四點(diǎn)DFT為例來說明快速算法的思路。為例來說明快速算法的思路。01.1W 2.1,1NmNWW3.N rrWW24.1NW 25.NrrWW 如何充分利用這些關(guān)系CHP4快速傅立葉變換* ( )( )( )( )( )( )( )( )=jjjjjjjjjXxeeeXxXxeeeXxeeeWWWW2221 12 13 1444

4、2221 22 23 24442221 32 33 34441111111100111221331111111111111( )( ) ( )( )xxxx 0123CHP4快速傅立葉變換( )( )( )( ) ( )( )( )( ) ( )( ) ( )( ) ( )( ) ( )( )= ( )( ) ( )( ) ( )( ) ( )( ) XxXWWxXxXWWxxxxxxxxxWxxxxxxxxW111111011110111221111131130213021302130213交換矩陣第二列和第三列得交換矩陣第二列和第三列得從上面的結(jié)果可以看出從上面的結(jié)果可以看出, ,利用對稱

5、性和周期性，求利用對稱性和周期性，求四點(diǎn)四點(diǎn)DFTDFT只需要一次復(fù)數(shù)乘法，稱為只需要一次復(fù)數(shù)乘法，稱為Coolkey-TukeyCoolkey-Tukey算法。算法。CHP4快速傅立葉變換11(0) (0)(2) (1)(3)(1) (0)(2) (1)(3)(2) (0)(2) (1)(3)(3) (0)(2) (1)(3)XxxxxXxxxxWXxxxxXxxxxW11(0)(2)xx(1)(3)xx(0)(1)XX(2)(3)XX111W(0)(2)xx(0)(2)xx(1)(3)xx(1)(3)xxCHP4快速傅立葉變換u算法分類：算法分類：N N為為2 2的整次冪的整次冪：按基數(shù)分

6、為基：按基數(shù)分為基-2FFT-2FFT算法、算法、基基-4FFT-4FFT算法、混合基算法、混合基FFTFFT算法、分裂基算法、分裂基FFTFFT算法算法; ;當(dāng)當(dāng)N N不是不是2 2的整次冪的整次冪: :典型的有典型的有Winograd Winograd 算法算法. .按抽取方法分：時(shí)間抽取按抽取方法分：時(shí)間抽取(Decimation(DecimationininTimeTime，簡稱，簡稱DIT)DIT)；頻率抽取；頻率抽取(Decimation(DecimationininFrequencyFrequency，簡稱，簡稱DIF)DIF) CHP4快速傅立葉變換 為了將大點(diǎn)數(shù)的為了將大點(diǎn)數(shù)

7、的DFT DFT 分解為小點(diǎn)數(shù)的分解為小點(diǎn)數(shù)的DFTDFT運(yùn)算，要求序列的長度運(yùn)算，要求序列的長度N N為為N N2 2M M (M (M為正為正整數(shù)整數(shù)) )。該情況下的變換稱為基。該情況下的變換稱為基2 FFT2 FFT。 N點(diǎn)DFTN/2點(diǎn) DFTN/4點(diǎn) DFT 2點(diǎn) DFT 1個(gè) 2個(gè) 4個(gè) N/2個(gè)問題是如何分最有效？可以對時(shí)間變量分問題是如何分最有效？可以對時(shí)間變量分（DIT)，也可對頻率變量分，也可對頻率變量分(DIF）CHP4快速傅立葉變換/()/( )()()()()NNrkrkNNrrNNrkkrkNNNrrX kxr WxrWxr WWxrW2 12 1221002 1

8、2 12200221221()(), ,/xrxrrN2210 12 1和，基本思路：從時(shí)域?qū)⒒舅悸罚簭臅r(shí)域?qū) N點(diǎn)序列點(diǎn)序列x(n)x(n)按奇偶項(xiàng)分解為按奇偶項(xiàng)分解為兩組，分別計(jì)算兩組兩組，分別計(jì)算兩組N/2N/2點(diǎn)點(diǎn)DFTDFT，然后再合成一個(gè)，然后再合成一個(gè)N N點(diǎn)點(diǎn)DFTDFT，按此方法繼續(xù)下去，直到，按此方法繼續(xù)下去，直到2 2點(diǎn)點(diǎn)DFTDFT，從而減，從而減少運(yùn)算量。少運(yùn)算量。算法具體步驟：算法具體步驟：一、算法的推導(dǎo)一、算法的推導(dǎo)1 1、序列、序列x(n)x(n)按奇偶項(xiàng)分解為兩組，將按奇偶項(xiàng)分解為兩組，將DFTDFT運(yùn)算也運(yùn)算也相應(yīng)分為兩組相應(yīng)分為兩組則則CHP4快速傅立

9、葉變換/( )()( )()( )( )( )NrkNrNrkNrkNA kxr WB kxrWX kA kW B k2 1202 1202212 2、兩個(gè)、兩個(gè)N/2N/2點(diǎn)的點(diǎn)的DFTDFT合成一個(gè)合成一個(gè)N N點(diǎn)點(diǎn)DFTDFT問題：問題：A(k)A(k)，B(k)B(k)都只有都只有N/2N/2個(gè)點(diǎn)，怎樣得到個(gè)點(diǎn)，怎樣得到X(k)X(k)的后的后N/2N/2點(diǎn)？利用周期性和對稱性得點(diǎn)？利用周期性和對稱性得 (/ )( )( )kNX kNA kW B k2CHP4快速傅立葉變換CHP4快速傅立葉變換3 3、繼續(xù)分解（一直分解到兩點(diǎn)、繼續(xù)分解（一直分解到兩點(diǎn)DFTDFT變換）變換） A(K

10、)和和B(K)仍是高復(fù)合數(shù)仍是高復(fù)合數(shù)(N2)的的DFT，我們可，我們可按上述方法繼續(xù)以分解。令按上述方法繼續(xù)以分解。令r2l，r2l十十1，l0，1，N4-1，則，則A(K)和和B(K)可分別表示為可分別表示為CHP4快速傅立葉變換令令則則CHP4快速傅立葉變換同理，令同理，令則則按此方法一直分解下去直到按此方法一直分解下去直到2 2點(diǎn)點(diǎn)DFTDFT，當(dāng)，當(dāng)N=8N=8時(shí)，如下：時(shí)，如下：CHP4快速傅立葉變換CHP4快速傅立葉變換下面通過討論尋找下面通過討論尋找FFTFFT的一般規(guī)律。的一般規(guī)律。二、算法的討論二、算法的討論1 1、“級級”的概念的概念 在分解過程中，每分一次，稱為一級運(yùn)算

11、在分解過程中，每分一次，稱為一級運(yùn)算。因?yàn)椤Ｒ驗(yàn)镸=log2NM=log2N，所以，所以N N點(diǎn)點(diǎn)DFTDFT可以分解為可以分解為M M級，級，按抽取算法的信號流圖中來定義，從左到右分按抽取算法的信號流圖中來定義，從左到右分別稱為別稱為0 0級、級、1 1級到級到M-1M-1級。級。CHP4快速傅立葉變換( )( )( )( )( )( )rmmNmrmmNmxpxpW xqxqxpW xq112 2、蝶形單元、蝶形單元 在算法的信號流圖中，第在算法的信號流圖中，第m m級存在這種運(yùn)級存在這種運(yùn)算，這種結(jié)構(gòu)幾何形狀像蝴蝶，稱為蝶形單元算，這種結(jié)構(gòu)幾何形狀像蝴蝶，稱為蝶形單元p p、q q是參于

12、本蝶形單元運(yùn)算的上、下節(jié)點(diǎn)的序號。由是參于本蝶形單元運(yùn)算的上、下節(jié)點(diǎn)的序號。由于第于第m m級序號的兩點(diǎn)只參于這一個(gè)蝶形單元的運(yùn)算，級序號的兩點(diǎn)只參于這一個(gè)蝶形單元的運(yùn)算，其輸出在第其輸出在第m m十十l l級。且這一蝶形單元也不再涉及別的級。且這一蝶形單元也不再涉及別的點(diǎn)。由于這一特點(diǎn)，在計(jì)算機(jī)編程時(shí)，我們可將蝶形點(diǎn)。由于這一特點(diǎn)，在計(jì)算機(jī)編程時(shí)，我們可將蝶形單元的輸出仍放在輸入數(shù)組中，這一特點(diǎn)稱為單元的輸出仍放在輸入數(shù)組中，這一特點(diǎn)稱為“同址同址運(yùn)算運(yùn)算”。CHP4快速傅立葉變換CHP4快速傅立葉變換loglogcaNMNMNMNNMN2222 由于一級都含有由于一級都含有N/2N/2個(gè)蝶

13、形單元，每個(gè)蝶形單元個(gè)蝶形單元，每個(gè)蝶形單元需要需要1 1次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法，因此完成次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法，因此完成loglog2 2N N級級共需要的復(fù)數(shù)乘法和加法分別為共需要的復(fù)數(shù)乘法和加法分別為 直接計(jì)算直接計(jì)算DFTDFT時(shí)所需的復(fù)乘數(shù)與復(fù)加數(shù)都是與時(shí)所需的復(fù)乘數(shù)與復(fù)加數(shù)都是與N2N2成正比的。所以采用成正比的。所以采用FFTFFT算法使運(yùn)算量大大減少。顯算法使運(yùn)算量大大減少。顯然，然，N N值愈大，節(jié)省的運(yùn)算量愈多。值愈大，節(jié)省的運(yùn)算量愈多。CHP4快速傅立葉變換3 3、“組組”的概念的概念 在分解過程中，每一級的在分解過程中，每一級的N/2N/2個(gè)蝶形單元個(gè)蝶形單元可以分

14、成若干組，每一組具有相同的結(jié)構(gòu)和可以分成若干組，每一組具有相同的結(jié)構(gòu)和W W因子分布。第因子分布。第m m級可分成級可分成N/2N/2m+1m+1組。組。CHP4快速傅立葉變換例：例：N=8=23，分，分3級。第一級的分組及級。第一級的分組及Wr因子如下：因子如下：m=0級級,分成四組：因子為分成四組：因子為m=1級級,分成二組分成二組,因子為因子為m=2級級,分成一組分成一組,因子為因子為/NWWW000428/,NNNNWWW WW W0102022288,NNNNW W W WW W W W0123012388884 4、W Wr r因子的分布因子的分布 由上分析可知由上分析可知結(jié)論：結(jié)

15、論：每由后向前（每由后向前（m由由M-1-0級）推進(jìn)一級，則級）推進(jìn)一級，則此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。CHP4快速傅立葉變換5 5、碼位倒置、碼位倒置 在在FFTFFT算法中，輸出的頻譜依照正常次序算法中，輸出的頻譜依照正常次序排列，但輸入的序列排列，但輸入的序列x(n)x(n)是按奇偶分開的，分是按奇偶分開的，分開的規(guī)律，以開的規(guī)律，以N=8N=8為例，按如下方法進(jìn)行排序?yàn)槔?，按如下方法進(jìn)行排序（1 1）、將）、將x(n)x(n)的序號寫成二進(jìn)制的序號寫成二進(jìn)制 x(000),x(001), x(000),x(001), x(110) ，x(11

16、1)x(111)。（2 2）將二進(jìn)制的碼進(jìn)行翻轉(zhuǎn)，得）將二進(jìn)制的碼進(jìn)行翻轉(zhuǎn)，得 x(000),x(100), x(000),x(100), x(011) ， x(111)x(111)。（3 3）將二進(jìn)制的翻轉(zhuǎn)碼轉(zhuǎn)換為對應(yīng)的十進(jìn)制）將二進(jìn)制的翻轉(zhuǎn)碼轉(zhuǎn)換為對應(yīng)的十進(jìn)制 x(0),x(4), x(3)x(0),x(4), x(3)，x(7)x(7)。 這就是按奇偶抽取得到的順序。這就是按奇偶抽取得到的順序。CHP4快速傅立葉變換說明：說明： 在上述的基在上述的基2FFT2FFT算法中，由于每一算法中，由于每一步分解都是按輸入序列步分解都是按輸入序列x(n)x(n)在時(shí)域上的次在時(shí)域上的次序是屬于偶數(shù)

17、還是奇數(shù)來抽取的，所以稱序是屬于偶數(shù)還是奇數(shù)來抽取的，所以稱為為“按時(shí)間抽取法按時(shí)間抽取法”或或“時(shí)間抽取時(shí)間抽取”。 上述的基上述的基2FFT2FFT算法中，抽取也可在算法中，抽取也可在頻域進(jìn)行，引出頻率抽?。l域進(jìn)行，引出頻率抽?。―IFDIF）基）基2FFT2FFT算法。算法。CHP4快速傅立葉變換 設(shè)輸入序列長度為設(shè)輸入序列長度為N=2M(M為正整數(shù)為正整數(shù))，頻率抽取法將輸入序列不是按奇、偶分組，頻率抽取法將輸入序列不是按奇、偶分組，而是按前后對半分開，這樣可將而是按前后對半分開，這樣可將N點(diǎn)點(diǎn)DFT寫成前后兩部分寫成前后兩部分;將該序列的頻域的輸出序?qū)⒃撔蛄械念l域的輸出序列列X(k

18、)(也是也是N點(diǎn)序列，按其點(diǎn)序列，按其頻域順序的奇頻域順序的奇偶分解偶分解為越來越短的子序列，稱為為越來越短的子序列，稱為基基2按按頻率抽取的頻率抽取的FFT算法算法。也稱為。也稱為Sander-Tukey算法。算法。CHP4快速傅立葉變換算法分析算法分析 現(xiàn)將輸入現(xiàn)將輸入x(n)按按n的順序分前后兩部分的順序分前后兩部分:前半子序列前半子序列x(n),0nN/2-1;后半子序列后半子序列x(n+N/2),0nN/2-1;例：例：N=8時(shí)，前半序列為：時(shí)，前半序列為：x(0),x(1),x(2),x(3); 后半序列為：后半序列為： x(4),x(5),x(6),x(7); 考慮考慮N點(diǎn)的點(diǎn)的

19、DFT,由由DFT定義得定義得CHP4快速傅立葉變換()()( ) ( )()( )() ( )()NNNnknknkNNNnnNNNnknkNNnnNNknkNNnNkNNjkkNj kNNNkNNX kx n Wx n Wx nWNx n Wx nWNx nx nWWkWWeekW 112200112220012202222222211（偶又奇CHP4快速傅立葉變換/( ) ( )(), ,() ( )(), ,(NnkNnNnrNnjnrjnrnrnrnrNNNNNNX kx nx nWkNkrNNXrx nx nWrWWeeW2 102 12022222220 222220 1122代

20、入又）按按k k的奇偶將的奇偶將X(k)X(k)分成奇偶兩部分分成奇偶兩部分, k=2r, k=2r和和k=2r+1,k=2r+1,考慮考慮k k為偶數(shù)情況為偶數(shù)情況/( )( )(), ,()( )NnrNnNNg nx nx nnXrg n W2 1200 1 21222令令CHP4快速傅立葉變換/( ) ( )(), ,() ( )(), ,NnkNnNnr nNnNX kx nx nWkNkrNNXrx nx nWr2 102 1200 22221210 1122代入考慮考慮k k為奇數(shù)情況為奇數(shù)情況/( ) ( )(), ,()( )nNNnrNnNNh nx nx nWnXrh n

21、 W2 1200 1 212221令令CHP4快速傅立葉變換結(jié)論結(jié)論 一個(gè)一個(gè)N點(diǎn)的點(diǎn)的DFT被分解為兩個(gè)被分解為兩個(gè)N/2點(diǎn)點(diǎn);與時(shí)間抽取法的推與時(shí)間抽取法的推演過程一樣，由于演過程一樣，由于N=2M,因此因此,N/2仍為偶數(shù)，所以可以將仍為偶數(shù)，所以可以將N/2點(diǎn)點(diǎn)DFT的輸出的輸出X(k)再分為偶數(shù)組和奇數(shù)組，這樣就將一個(gè)再分為偶數(shù)組和奇數(shù)組，這樣就將一個(gè)N/2點(diǎn)的點(diǎn)的DFT分成兩個(gè)分成兩個(gè)N/4點(diǎn)點(diǎn)DFT的輸入，也是將的輸入，也是將N/2點(diǎn)的點(diǎn)的DFT的輸入上、下對半分后通過蝶形運(yùn)算而形成，直至最后的輸入上、下對半分后通過蝶形運(yùn)算而形成，直至最后為為2點(diǎn)點(diǎn)DFT。/( )( )(),

22、,( ) ( )(), ,()( ),()( )nNNNnrnrNNnnNNg nx nx nnNNh nx nx nWnXrg n WXrh n W2 12 122000 1 21220 1 2122221CHP4快速傅立葉變換8點(diǎn)點(diǎn)DIF基基2FFT算法流圖算法流圖 CHP4快速傅立葉變換CHP4快速傅立葉變換DITDIT與與DIFDIF的相同之處：的相同之處：（1 1）DIFDIF與與DITDIT兩種算法均為原位運(yùn)算。兩種算法均為原位運(yùn)算。（2 2）DIFDIF與與DITDIT運(yùn)算量相同。運(yùn)算量相同。DITDIT與與DIFDIF的不同之處：的不同之處：（1 1）DIFDIF與與DITDI

23、T兩種算法結(jié)構(gòu)倒過來。兩種算法結(jié)構(gòu)倒過來。DIFDIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)二進(jìn)制倒讀制倒讀”程序。程序。DITDIT為輸入亂序，輸出順序。先運(yùn)行為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀二進(jìn)制倒讀”程序，再進(jìn)行求程序，再進(jìn)行求DFTDFT。（2 2）DIFDIF與與DITDIT根本區(qū)別：在于蝶形結(jié)不同。根本區(qū)別：在于蝶形結(jié)不同。DITDIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。的復(fù)數(shù)相乘出現(xiàn)在減法之前。DIFDIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。的復(fù)數(shù)相乘出現(xiàn)在減法之后。CHP4快速傅立葉變換u自從基自從基2快速算法出現(xiàn)以來，人們?nèi)栽诓粩鄬で罂焖偎惴ǔ霈F(xiàn)以

24、來，人們?nèi)栽诓粩鄬で蟾斓乃惴?。更快的算法?984年，法國的杜梅爾年，法國的杜梅爾(P.Dohamel)和霍爾曼和霍爾曼(H.Hollmann)將基將基2分解和基分解和基4分解糅合分解糅合在一起，提出了在一起，提出了分裂基分裂基FFT算法算法。其運(yùn)算量比前。其運(yùn)算量比前幾種算法都有所減少，運(yùn)算流圖卻與基幾種算法都有所減少，運(yùn)算流圖卻與基2FFT很很接近，運(yùn)算程序也很短。接近，運(yùn)算程序也很短。它是目前一種實(shí)用的高它是目前一種實(shí)用的高效新算法。效新算法。CHP4快速傅立葉變換 分裂基算法分裂基算法又稱又稱基基2/42/4算法算法, ,算法的算法的基本基本思路思路是是: :對偶號輸出使用基對偶號輸

25、出使用基2 2算法算法, ,對奇號輸對奇號輸出使用基出使用基4 4算法。算法。下面首先介紹基下面首先介紹基4 4算法：算法：令令N=4N=4M M，對，對N N點(diǎn)點(diǎn)DFTDFT可按下面方法進(jìn)行頻率抽可按下面方法進(jìn)行頻率抽取取/( )( )( )( )( )NNNNnknknknkNNNNnn Nn NnNX kx nWx nWx nWx nW4 12 134 1104234分別令分別令k=4rk=4r， k=4r+2k=4r+2， k=4r+1k=4r+1， k=4r+3k=4r+3，其中，其中，r=0r=0，1 1，2 2，N/4-1N/4-1，有，有CHP4快速傅立葉變換/()( ( )(

26、) ( ()()()( ( )() ( ()()()( ( )()( ()()()NnrNnNnnrNNnNnnrNNnNNNXrx nx nx nx nWNNNXrx nx nx nx nW WNNNXrx nx nj x nx nW WXr4 1404 12404 1403424434224434124443/( ( )()( ()()NnnrNNnNNNx nx nj x nx nW W4 13403244CHP4快速傅立葉變換CHP4快速傅立葉變換/()( ( )()( ()()()( ( )()( ()()NnnrNNnNnnrNNnNNNX rx nx nj x nx nWWNNN

27、X rx nx nj x nx nW W 4 1404 1340341244343244算法分析算法分析 對于對于N=4N=4M M點(diǎn)點(diǎn)DFTDFT，當(dāng)輸出項(xiàng)，當(dāng)輸出項(xiàng)k k為偶數(shù)時(shí)，采用為偶數(shù)時(shí)，采用基基2 2算法，即算法，即/() ( )()NnrNnNXrx nx nW2 12022當(dāng)輸出項(xiàng)當(dāng)輸出項(xiàng)k k為奇數(shù)時(shí)，采用基為奇數(shù)時(shí)，采用基4 4算法，即算法，即CHP4快速傅立葉變換CHP4快速傅立葉變換CHP4快速傅立葉變換分析：分析： 一個(gè)一個(gè)N N點(diǎn)點(diǎn)DFTDFT可以分解為一個(gè)可以分解為一個(gè)N/2N/2點(diǎn)點(diǎn)DFTDFT和兩個(gè)和兩個(gè)N/4N/4點(diǎn)點(diǎn)DFTDFT。由。由x(n) x(n+N

28、/4) x(n+N/2)x(n) x(n+N/4) x(n+N/2)和和x(n+3N/4)x(n+3N/4)求求N/2N/2點(diǎn)點(diǎn)DFTDFT和和N/4N/4的的DFTDFT只需要兩次乘法只需要兩次乘法，可以減少運(yùn)算量。，可以減少運(yùn)算量。 N/2N/2點(diǎn)點(diǎn)DFTDFT可進(jìn)一步分解為可進(jìn)一步分解為一個(gè)一個(gè)N/4點(diǎn)點(diǎn)DFT和兩個(gè)和兩個(gè)N/8的的DFT。N/4N/4的點(diǎn)的點(diǎn)DFTDFT進(jìn)一步分解為進(jìn)一步分解為一個(gè)一個(gè)N/8點(diǎn)點(diǎn)DFT和兩和兩個(gè)個(gè)N/16的的DFT。 這樣一直下去，直到分解為兩點(diǎn)或這樣一直下去，直到分解為兩點(diǎn)或4 4點(diǎn)點(diǎn)DFTDFT為止。為止。CHP4快速傅立葉變換結(jié)論：結(jié)論： 分裂基分

29、裂基FFTFFT算法結(jié)構(gòu)同基算法結(jié)構(gòu)同基2FFT2FFT算法結(jié)構(gòu)相似，算法結(jié)構(gòu)相似，適用于適用于N=2N=2M M的場合，并由的場合，并由M M級運(yùn)算實(shí)現(xiàn)。運(yùn)算流圖輸級運(yùn)算實(shí)現(xiàn)。運(yùn)算流圖輸入為順序，輸出為倒序。入為順序，輸出為倒序。()()MRMRMNMNANMN 438261399816221399分裂基分裂基FFTFFT算法的計(jì)算量算法的計(jì)算量CHP4快速傅立葉變換 以上提出以上提出FFT算法，可以很快地求出全部算法，可以很快地求出全部DFT值。值。即求出有限長序列即求出有限長序列x(n)的的z變換變換X(z)在單位園上在單位園上N個(gè)等個(gè)等間隔抽樣點(diǎn)間隔抽樣點(diǎn)zk處的抽樣值。它要求處的抽樣

30、值。它要求N為高度復(fù)合數(shù)。為高度復(fù)合數(shù)。即即N可以分解成一些因子的乘積。例可以分解成一些因子的乘積。例N=2L 實(shí)際上：實(shí)際上：（1）也許對其它圍線上也許對其它圍線上z變換取樣發(fā)生興趣變換取樣發(fā)生興趣。如語音。如語音處理中，常常需要知道某一圍線處理中，常常需要知道某一圍線z變換的極點(diǎn)所處的變換的極點(diǎn)所處的復(fù)頻率。復(fù)頻率。（2）只需要計(jì)算單位圓上某一段的頻譜只需要計(jì)算單位圓上某一段的頻譜,即即M不等于不等于N。如窄帶信號，希望在窄帶頻率內(nèi)頻率抽樣能夠非常如窄帶信號，希望在窄帶頻率內(nèi)頻率抽樣能夠非常密集，提高分辨率，帶外則不考慮。密集，提高分辨率，帶外則不考慮。（3）若若N是大素?cái)?shù)時(shí)，不能加以分解

31、，又如何有效計(jì)是大素?cái)?shù)時(shí)，不能加以分解，又如何有效計(jì)算這種序列算這種序列DFT。例。例N=311，若用基，若用基2則須補(bǔ)則須補(bǔ)N=28=512點(diǎn)，要補(bǔ)點(diǎn)，要補(bǔ)211個(gè)零點(diǎn)。個(gè)零點(diǎn)。CHP4快速傅立葉變換問題提出問題提出 為了提高為了提高DFT的靈活性，須用新的方法。線性調(diào)的靈活性，須用新的方法。線性調(diào)頻頻z變換變換(CZT)就是適用這種更為一般情況下，由就是適用這種更為一般情況下，由x(n)求求X(zk)的快速變換。的快速變換。CZT 來自于雷達(dá)專業(yè)的專用詞匯。來自于雷達(dá)專業(yè)的專用詞匯。Z 變換采用螺線抽變換采用螺線抽樣樣,可計(jì)算單位圓上任一段曲線的可計(jì)算單位圓上任一段曲線的Z變換，適用于變換

32、，適用于更一般情況下（更一般情況下（M不等于不等于N）由）由x(n)求求X(zr)的快速的快速算法算法, 達(dá)到頻域細(xì)化的目的，這種變換稱為線性調(diào)達(dá)到頻域細(xì)化的目的，這種變換稱為線性調(diào)頻頻Z變換變換(簡稱簡稱CZT )。CHP4快速傅立葉變換 為適應(yīng)為適應(yīng)z可以沿平面內(nèi)更一般的路徑取值，我們沿可以沿平面內(nèi)更一般的路徑取值，我們沿z平面上的一段螺線作等分角的抽樣，則平面上的一段螺線作等分角的抽樣，則z的取樣點(diǎn)的取樣點(diǎn)Zr可表示為：可表示為：)()NnnXzx nz10（, ,rrzAWrM0 11,jjAA eWW e0000 已已 知知 N點(diǎn)序列點(diǎn)序列x(n) ，0nN-1,其其z變換為變換為其

33、中其中M：表示欲分析的復(fù)頻譜的點(diǎn)數(shù)。：表示欲分析的復(fù)頻譜的點(diǎn)數(shù)。M不一定等于不一定等于N。A，W 都為任意復(fù)數(shù)都為任意復(fù)數(shù),令令 一、一、CZTCZT的定義的定義CHP4快速傅立葉變換()()()()NnkrnNnnrnzXzC Z Tx nx n zx n AW1010代 入中 得, ,rM0 11上式即為上式即為CZTCZT的定義的定義. .現(xiàn)在討論現(xiàn)在討論A A0 0,W,W0 0,0 0,0 0的的含義含義: : 為輸出為輸出M M點(diǎn)的變換域值點(diǎn)的變換域值.r=0.r=0時(shí)的時(shí)的A A0 0e ej0j0是是CZTCZT的起點(diǎn)的起點(diǎn), ,隨著隨著r r的變化的變化,r,r0 0,r,r

34、1 1,R,RM-1M-1構(gòu)成構(gòu)成CZTCZT的變化路徑，對于的變化路徑，對于M-1M-1點(diǎn)其極坐標(biāo)為點(diǎn)其極坐標(biāo)為()()jj MMQA eWe001100CHP4快速傅立葉變換CHP4快速傅立葉變換CZTCZT在現(xiàn)在現(xiàn)Z Z平面上的變換路徑是一條平面上的變換路徑是一條螺旋線螺旋線。（1）A為起始樣點(diǎn)位置為起始樣點(diǎn)位置,jAA eA0000：起點(diǎn)半徑，大于起點(diǎn)半徑，大于1 1時(shí)，表示螺旋線在單位圓外時(shí)，表示螺旋線在單位圓外，反之，在單位圓內(nèi)。，反之，在單位圓內(nèi)。起點(diǎn)半相角。起點(diǎn)半相角。（2）當(dāng)）當(dāng)W01,螺旋線內(nèi)旋，反之外旋。螺旋線內(nèi)旋，反之外旋。（3）當(dāng)）當(dāng)A0=W0=1時(shí)，時(shí)，CZT的變換

35、路徑為單位圓上的變換路徑為單位圓上的一段弧，起點(diǎn)為的一段弧，起點(diǎn)為P，終點(diǎn)為，終點(diǎn)為Q，且，且M不一定等不一定等于于N。CHP4快速傅立葉變換。變換求出該序列即由，為均勻分布在單位園上此時(shí)等分）時(shí)，（。即即（當(dāng)滿足下面特殊條件：DFTCZTzNNMWeeWWcAeAAbNMarNjjj221,)(01, 1)(: )4(002000000CHP4快速傅立葉變換()()() ()( )( ) ( )nr nrNNnnknrnnrnr nNnnnrnrrnX zx n A Wx n A WWWWx n A WW22222222211222001222012利用 考慮考慮A0=W0=1時(shí)，在單位圓上

36、時(shí)，在單位圓上CZT，且，且M不一定等不一定等于于N。CHP4快速傅立葉變換( )( ), ( )()( ) (), ,()( )( )() ( )( ), ,( )nnnrNrnrrrrrg nx n A Wh nWX zWg n h rn rMX zg nh nWX zWg rh rkMWy r222222221202220 110 11令由上式可知：可以由與的離散卷并乘得到，即：CHP4快速傅立葉變換( )rX z( )x nnnA W22rW22( )nhn W22( )g n( )y rCZTCZT的線性濾波計(jì)算步驟的線性濾波計(jì)算步驟CHP4快速傅立葉變換二、二、CZTCZT的計(jì)算方法的計(jì)算方法分析：分析：從上面的推導(dǎo)過程可以看出，計(jì)算從上面的推導(dǎo)過程可以看出，計(jì)算CZTCZT關(guān)鍵是計(jì)算一個(gè)線性卷積關(guān)鍵是計(jì)算一個(gè)線性卷積( )( )( )y rg rh r其中，其中，g(n)g(n)應(yīng)為應(yīng)為N N點(diǎn)序列，點(diǎn)序列，h(n)h(n)應(yīng)為偶對稱的應(yīng)為偶對稱的無限長序列，考慮到輸出無限長序列，考慮到輸出M M點(diǎn)序列，點(diǎn)序列，h(n)h(n)的實(shí)的實(shí)際長度應(yīng)為際長度應(yīng)為M M點(diǎn)。因此，可用點(diǎn)。因此，可用DFTDFT來實(shí)現(xiàn)兩者來實(shí)現(xiàn)兩者的卷積，具體步驟如下：的卷積，具體步驟如下：CHP4快速傅立葉變換()( ),( )( ),.jjnnnnmAA eWW eA