數(shù)字信號處理 吳鎮(zhèn)揚(yáng)_CHP3快速傅立葉變換

1、 快速傅里葉變換快速傅里葉變換(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ù)乘法和次復(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)算

2、量將非常龐大；同時(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ù)。在正交矩陣中，雖然有在正交矩陣中，雖然有N N2 2個(gè)元素，但只有個(gè)元素，但只有N N個(gè)不同個(gè)不同的值，且有些取值特別簡單，主要由于旋轉(zhuǎn)因子具的值，且有些取值特別簡單，主要由于旋轉(zhuǎn)因子具有如下的特點(diǎn)：有如下的特點(diǎn)：對稱性對稱性周期性周期性下面以四點(diǎn)下面以四點(diǎn)DFT為例來說明快速算法的思路。為例來說明快速算法的思

3、路。01.1W 2.1,1NmNWW3.N rrWW24.1NW 25.NrrWW 如何充分利用這些關(guān)系* ( )( )( )( )( )( )( )( )=jjjjjjjjjXxeeeXxXxeeeXxeeeWWWW2221 12 13 14442221 22 23 24442221 32 33 34441111111100111221331111111111111( )( ) ( )( )xxxx 0123( )( )( )( ) ( )( )( )( ) ( )( ) ( )( ) ( )( ) ( )( )= ( )( ) ( )( ) ( )( ) ( )( ) XxXWWxXxXW

4、WxxxxxxxxxWxxxxxxxxW111111011110111221111131130213021302130213交換矩陣第二列和第三列得交換矩陣第二列和第三列得從上面的結(jié)果可以看出從上面的結(jié)果可以看出, ,利用對稱性和周期性，求利用對稱性和周期性，求四點(diǎn)四點(diǎn)DFTDFT只需要一次復(fù)數(shù)乘法，稱為只需要一次復(fù)數(shù)乘法，稱為Coolkey-TukeyCoolkey-Tukey算法。算法。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(

5、1)(3)xx(0)(1)XX(2)(3)XX111W(0)(2)xx(0)(2)xx(1)(3)xx(1)(3)xx概述概述u算法分類：算法分類：N N為為2 2的整次冪的整次冪：按基數(shù)分為按基數(shù)分為基基-2FFT-2FFT算法算法、基基-4FFT-4FFT算法算法、混合基混合基FFTFFT算法算法、分裂基分裂基FFTFFT算法算法; ;當(dāng)當(dāng)N N不是不是2 2的整次冪的整次冪: :典型的有典型的有Winograd Winograd 算法算法. .按抽取方法分：按抽取方法分：時(shí)間抽取時(shí)間抽取(Decimation(DecimationininTimeTime，簡稱，簡稱DIT)DIT)；頻率

6、抽??；頻率抽取(Decimation(DecimationininFrequencyFrequency，簡稱，簡稱DIF)DIF) 為了將大點(diǎn)數(shù)的為了將大點(diǎn)數(shù)的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）/

7、()/( )()()()()NNrkrkNNrrNNrkkrkNNNrrX kxr WxrWxr WWxrW2 12 1221002 12 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、序

8、列、序列x(n)x(n)按奇偶項(xiàng)分解為兩組，將按奇偶項(xiàng)分解為兩組，將DFTDFT運(yùn)算也運(yùn)算也相應(yīng)分為兩組相應(yīng)分為兩組則則/( )()( )()( )( )( )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 k23.3.1 3.3.

9、1時(shí)間抽?。〞r(shí)間抽?。―IT）基）基2FFT算法算法3 3、繼續(xù)分解（一直分解到兩點(diǎn)、繼續(xù)分解（一直分解到兩點(diǎn)DFTDFT變換）變換） A(K)和和B(K)仍是高復(fù)合數(shù)仍是高復(fù)合數(shù)(N2)的的DFT，我們可，我們可按上述方法繼續(xù)以分解。令按上述方法繼續(xù)以分解。令r2l，r2l十十1，l0，1，N4-1，則，則A(K)和和B(K)可分別表示為可分別表示為3.3.1時(shí)間抽?。〞r(shí)間抽?。―IT）基）基2FFT算法算法3.3.1時(shí)間抽?。〞r(shí)間抽?。―IT）基）基2FFT算法算法令令則則3.3.1時(shí)間抽?。〞r(shí)間抽?。―IT）基）基2FFT算法算法同理，令同理，令則則按此方法一直分解下去直到按此方法一直分

10、解下去直到2 2點(diǎn)點(diǎn)DFTDFT，當(dāng)，當(dāng)N=8N=8時(shí)，如下：時(shí)，如下：3.3.1時(shí)間抽?。〞r(shí)間抽?。―IT）基）基2FFT算法算法下面通過討論尋找下面通過討論尋找FFTFFT的一般規(guī)律。的一般規(guī)律。二、算法的討論二、算法的討論1 1、“級級”的概念的概念 在分解過程中，每分一次，在分解過程中，每分一次，稱為一級運(yùn)算稱為一級運(yùn)算。因?yàn)?。因?yàn)镸=log2M=log2N N，所以，所以N N點(diǎn)點(diǎn)DFTDFT可以分解為可以分解為M M級，級，按抽取算法的信號流圖中來定義，從左到右分按抽取算法的信號流圖中來定義，從左到右分別稱為別稱為0 0級、級、1 1級到級到M-1M-1級。級。( )( )( )(

11、 )( )( )rmmNmrmmNmxpxpW xqxqxpW xq112 2、蝶形單元、蝶形單元 在算法的信號流圖中，第在算法的信號流圖中，第m m級存在這種運(yùn)級存在這種運(yùn)算，這種結(jié)構(gòu)幾何形狀像蝴蝶，稱為蝶形單元算，這種結(jié)構(gòu)幾何形狀像蝴蝶，稱為蝶形單元p p、q q是參于本蝶形單元運(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)。由于

12、這一特點(diǎn)，在計(jì)算機(jī)編程時(shí)，我們可將蝶形單元的輸出仍放在輸入數(shù)組中，這一特點(diǎn)稱為單元的輸出仍放在輸入數(shù)組中，這一特點(diǎn)稱為“同址同址運(yùn)算運(yùn)算”。3.3.1時(shí)間抽?。〞r(shí)間抽?。―IT）基）基2FFT算法算法loglogcaNMNMNMNNMN2222 由于一級都含有由于一級都含有N/2N/2個(gè)蝶形單元，每個(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成正比

13、的。所以采用成正比的。所以采用FFTFFT算法使運(yùn)算量大大減少。顯算法使運(yùn)算量大大減少。顯然，然，N N值愈大，節(jié)省的運(yùn)算量愈多。值愈大，節(jié)省的運(yùn)算量愈多。3 3、“組組”的概念的概念 在分解過程中，每一級的在分解過程中，每一級的N/2N/2個(gè)蝶形單元個(gè)蝶形單元可以分成若干組，每一組具有相同的結(jié)構(gòu)和可以分成若干組，每一組具有相同的結(jié)構(gòu)和W W因子分布。第因子分布。第m m級可分成級可分成N/2N/2m+1m+1組。組。例：例：N=8=23，分分3級。級。第一級的分組及第一級的分組及Wr因子如下：因子如下：m=0級級,分成四組：因子為分成四組：因子為m=1級級,分成二組分成二組,因子因子為為m=

14、2級級,分成一組分成一組,因子因子為為/NWWW000428/,NNNNWWW WW W0102022288,NNNNW W W WW W W W0123012388884 4、W Wr r因子的分布因子的分布 由上分析可知由上分析可知結(jié)論：結(jié)論：每由后向前（每由后向前（m由由M-1-0級）推進(jìn)一級，則級）推進(jìn)一級，則此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。5 5、碼位倒置、碼位倒置 在在FFTFFT算法中，輸出的頻譜依照正常次序算法中，輸出的頻譜依照正常次序排列，但輸入的序列排列，但輸入的序列x(n)x(n)是按奇偶分開的，分是按奇偶分開的，分開的規(guī)律，以開的

15、規(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(111)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(0),x(4), x(3), x(3)，x(7)x(7)。 這就是按奇偶抽取得到的順

16、序。這就是按奇偶抽取得到的順序。說明：說明： 在上述的基在上述的基2FFT2FFT算法中，由于每一算法中，由于每一步分解都是按輸入序列步分解都是按輸入序列x(n)x(n)在時(shí)域上的次在時(shí)域上的次序是屬于偶數(shù)還是奇數(shù)來抽取的，所以稱序是屬于偶數(shù)還是奇數(shù)來抽取的，所以稱為為“按時(shí)間抽取法按時(shí)間抽取法”或或“時(shí)間抽取時(shí)間抽取”。 上述的基上述的基2FFT2FFT算法中，抽取也可在算法中，抽取也可在頻域進(jìn)行，引出頻率抽?。l域進(jìn)行，引出頻率抽取（DIFDIF）基）基2FFT2FFT算法。算法。 設(shè)輸入序列長度為設(shè)輸入序列長度為N=2M(M為正整數(shù)為正整數(shù))，頻率抽取法將輸入序列不是按奇、偶分組，頻率抽

17、取法將輸入序列不是按奇、偶分組，而是按前后對半分開，這樣可將而是按前后對半分開，這樣可將N點(diǎn)點(diǎn)DFT寫成前后兩部分寫成前后兩部分;將該序列的頻域的輸出序?qū)⒃撔蛄械念l域的輸出序列列X(k)(也是也是N點(diǎn)序列，按其點(diǎn)序列，按其頻域順序的奇頻域順序的奇偶分解偶分解為越來越短的子序列，稱為為越來越短的子序列，稱為基基2按按頻率抽取的頻率抽取的FFT算法算法。也稱為。也稱為Sander-Tukey算法。算法。算法分析算法分析 現(xiàn)將輸入現(xiàn)將輸入x(n)按按n的順序分前后兩部分的順序分前后兩部分:前半子序列前半子序列x(n),0nN/2-1;后半子序列后半子序列x(n+N/2),0nN/2-1;例：例：N=

18、8時(shí)，前半序列為：時(shí)，前半序列為：x(0),x(1),x(2),x(3); 后半序列為：后半序列為： x(4),x(5),x(6),x(7); 考慮考慮N點(diǎn)的點(diǎn)的DFT,由由DFT定義定義得得()()( ) ( )()( )() ( )()NNNnknknkNNNnnNNNnknkNNnnNNknkNNnNkNNjkkNj kNNNkNNX kx n Wx n Wx nWNx n Wx nWNx nx nWWkWWeekW 112200112220012202222222211（偶又奇/( ) ( )(), ,() ( )(), ,(NnkNnNnrNnjnrjnrnrnrnrNNNNNNX

19、kx nx nWkNkrNNXrx nx nWrWWeeW2 102 12022222220 222220 1122代入又）按按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令令/( ) ( )(), ,() ( )(), ,NnkNnNnr nNnNX kx nx nWkNkrNNXrx nx nWr2 102 1200 22221210 1122代入考慮考慮k k為奇數(shù)情況

20、為奇數(shù)情況/( ) ( )(), ,()( )nNNnrNnNNh nx nx nWnXrh n W2 1200 1 212221令令結(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)算而形成，直至最后的輸入上、下對

21、半分后通過蝶形運(yùn)算而形成，直至最后為為2點(diǎn)點(diǎn)DFT。/( )( )(), ,( ) ( )(), ,()( ),()( )nNNNnrnrNNnnNNg nx nx nnNNh nx nx nWnXrg nWXrh nW2 12 122000 1 21220 1 21222218點(diǎn)點(diǎn)DIF基基2FFT算法流圖算法流圖 3.3.2 頻率抽?。l率抽?。―IF）基）基2FFT算法算法3.3.2 頻率抽?。l率抽?。―IF）基）基2FFT算法算法DITDIT與與DIFDIF的相同之處：的相同之處：（1 1）DIFDIF與與DITDIT兩種算法均為原位運(yùn)算。兩種算法均為原位運(yùn)算。（2 2）DIFDIF

22、與與DITDIT運(yùn)算量相同。運(yùn)算量相同。DITDIT與與DIFDIF的不同之處：的不同之處：（1 1）DIFDIF與與DITDIT兩種算法結(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ù)相乘

23、出現(xiàn)在減法之后。的復(fù)數(shù)相乘出現(xiàn)在減法之后。 以上討論的都是以以上討論的都是以2為基數(shù)的為基數(shù)的FFT算法，即算法，即N=2M，這，這種情況實(shí)際上使用得最多。種情況實(shí)際上使用得最多。 優(yōu)點(diǎn)：程序簡單，效率高，使用方便。優(yōu)點(diǎn)：程序簡單，效率高，使用方便。 實(shí)際應(yīng)用時(shí)，有限長序列的長度實(shí)際應(yīng)用時(shí)，有限長序列的長度N很大程度上由人很大程度上由人為因素確定，因此多數(shù)場合可取為因素確定，因此多數(shù)場合可取 N=2M，從而直接使用，從而直接使用以以 2 為基數(shù)的為基數(shù)的FFT算法。算法。 如如N不能人為確定不能人為確定 , N的數(shù)值也不是以的數(shù)值也不是以2為基數(shù)的整為基數(shù)的整數(shù)次方數(shù)次方,處理方法有兩種處理方

24、法有兩種: 補(bǔ)零補(bǔ)零:將將x(n)補(bǔ)零補(bǔ)零 , 使使N=2M. 例如例如N=30,補(bǔ)上補(bǔ)上x(30)=x(31)=0兩點(diǎn)兩點(diǎn),使使N=32=25,這這樣可直接采用以樣可直接采用以2為基數(shù)為基數(shù)M=5的的FFT程序。程序。 有限長度序列補(bǔ)零后并不影響其頻譜有限長度序列補(bǔ)零后并不影響其頻譜 X(ej ) ，只是，只是頻譜的采樣點(diǎn)數(shù)增加了頻譜的采樣點(diǎn)數(shù)增加了,上例中由上例中由30點(diǎn)增加到點(diǎn)增加到32點(diǎn)，所點(diǎn)，所以在許多場合這種處理是可接受的。以在許多場合這種處理是可接受的。 如要求準(zhǔn)確的如要求準(zhǔn)確的N點(diǎn)點(diǎn)DFT值值,可采用任意數(shù)為基數(shù)的可采用任意數(shù)為基數(shù)的 FFT 算法算法 , 其其 計(jì)算效率低于以

25、計(jì)算效率低于以2為基數(shù)為基數(shù)FFT算法。算法。 如如 N 為復(fù)合數(shù)，可分解為兩個(gè)整數(shù)為復(fù)合數(shù)，可分解為兩個(gè)整數(shù)p與與q的乘積的乘積,像前面以像前面以2為基數(shù)時(shí)一樣為基數(shù)時(shí)一樣,FFT的基本思想是將的基本思想是將DFT的的運(yùn)算盡量分小運(yùn)算盡量分小,因此因此,在在N=pq情況下情況下,也希望將也希望將N點(diǎn)的點(diǎn)的DFT分解為分解為p個(gè)個(gè)q點(diǎn)點(diǎn)DFT或或q個(gè)個(gè)p點(diǎn)點(diǎn)DFT,以減少計(jì)算量。以減少計(jì)算量。步驟：步驟：1010nnQnkk Pk01,n k分別為0, 1,，Q-1; 10,n k分別為0, 1,，P-1。 N點(diǎn)點(diǎn)DFT可以重新寫成為可以重新寫成為 101010( )(),( )NknNnX

26、kX k PkX k kx n W10100111()()1000QPk P kn Q nNnnx nQn W0 11 00 01 1010 11 00 00111101000111000,QPk n Qk n Pk nk n PQNNNNnnQPk n Qk n Pk nNNNnnX k kx n n WWWWx n n WWW考慮到 再令1010nkPQnkNWW令 1010010100100110,QnnkQnkNPnnkPWWWnnxkkXPnnkPWnnxnkX,01000,0011001nkQnkNQnWWnkXkkX00001001,nkNWnkXnkXQnnkQWnkXkkX,

27、(1) 先將先將 x(n)通過通過 x(n1Q+n0)改寫成改寫成 x(n1,n0)。因?yàn)?。因?yàn)?Q=4, n1=0,1,2, n0=0,1,2,3,故輸入是按自然順序的，即故輸入是按自然順序的，即x(0,0)=x(0) x(0,1)=x(1) x(0,2)=x(2) x(0,3)=x(3)x(1,0)=x(4) x(1,1)=x(5) x(1,2)=x(6) x(1,3)=x(7)x(2,0)=x(8) x(2,1)=x(9) x(2,2)=x(10) x(2,3)=x(11)以以P=3，Q=4, N=12為例為例 (2) 求個(gè)點(diǎn)的求個(gè)點(diǎn)的DFT 20301001110,nnkWnnxnkX

28、（）（）X1(k0,n0)乘以得到乘以得到X1(k0,n0)。（）求（）求P個(gè)個(gè)點(diǎn)的點(diǎn)的DFT，參變量是，參變量是k0（）將（）將X2(k0,k1)通過通過X(k0+k1P)恢復(fù)為恢復(fù)為X(k)N=12為組合數(shù)時(shí)的為組合數(shù)時(shí)的FFT（）求（）求個(gè)個(gè)P點(diǎn)點(diǎn)DFT需要需要P2次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和P(P-1)次復(fù)數(shù)加法；次復(fù)數(shù)加法；（）乘（）乘個(gè)個(gè)W因子需要因子需要次復(fù)數(shù)乘法；次復(fù)數(shù)乘法；（）求（）求P個(gè)個(gè)點(diǎn)點(diǎn)DFT需要需要PQ2 次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和P（-1)次復(fù)數(shù)加法。次復(fù)數(shù)加法?？偟膹?fù)數(shù)乘法量總的復(fù)數(shù)乘法量: QP2+N+PQ2=N(P+Q+1)；總的復(fù)數(shù)加法量總的復(fù)數(shù)加法量: QP(

29、P-1)+PQ(Q-1)=N(P+Q-2) 例例: N=23*29=667, N2=444889, N(P+Q+1)=35351當(dāng)組合數(shù)當(dāng)組合數(shù) N N= =P P1 1P P2 2P P3 3P Pm m中所有的中所有的P Pi i均為均為4 4時(shí)，就是時(shí)，就是基四基四FFTFFT算法算法 以上提出以上提出FFT算法，可以很快地求出全部算法，可以很快地求出全部DFT值。值。即求出有限長序列即求出有限長序列x(n)的的z變換變換X(z)在單位園上在單位園上N個(gè)等個(gè)等間隔抽樣點(diǎn)間隔抽樣點(diǎn)zk處的抽樣值。它要求處的抽樣值。它要求N為高度復(fù)合數(shù)。為高度復(fù)合數(shù)。即即N可以分解成一些因子的乘積。例可以分

30、解成一些因子的乘積。例N=2L 實(shí)際上：實(shí)際上：（1）也許對其它圍線上也許對其它圍線上z變換取樣發(fā)生興趣變換取樣發(fā)生興趣。（2）只需要計(jì)算單位圓上某一段的頻譜只需要計(jì)算單位圓上某一段的頻譜,即即M不等于不等于N。如窄帶信號，希望在窄帶頻率內(nèi)頻率抽樣能夠非常如窄帶信號，希望在窄帶頻率內(nèi)頻率抽樣能夠非常密集，提高分辨率，帶外則不考慮。密集，提高分辨率，帶外則不考慮。（3）若若N是大素?cái)?shù)時(shí)，不能加以分解，又如何有效計(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)。問題提出問題提出 為

31、了提高為了提高DFT的靈活性，須用新的方法。線性調(diào)的靈活性，須用新的方法。線性調(diào)頻頻z變換變換(CZT)就是適用這種更為一般情況下，由就是適用這種更為一般情況下，由x(n)求求X(zk)的快速變換的快速變換。CZT 來自于雷達(dá)專業(yè)的專用詞匯。來自于雷達(dá)專業(yè)的專用詞匯。Z 變換采用螺線抽變換采用螺線抽樣樣,可計(jì)算單位圓上任一段曲線的可計(jì)算單位圓上任一段曲線的Z變換，適用于變換，適用于更一般情況下（更一般情況下（M不等于不等于N）由）由x(n)求求X(zr)的快速的快速算法算法, 達(dá)到頻域細(xì)化的目的，這種變換稱為線性調(diào)達(dá)到頻域細(xì)化的目的，這種變換稱為線性調(diào)頻頻Z變換變換(簡稱簡稱CZT )。 為適

32、應(yīng)為適應(yīng)z可以沿平面內(nèi)更一般的路徑取值，可以沿平面內(nèi)更一般的路徑取值，我們我們沿沿z平面上的一段螺線作平面上的一段螺線作等分角的抽樣等分角的抽樣，則，則z的取樣點(diǎn)的取樣點(diǎn)Zr可表示為：可表示為：)( )NnnX zx n z10（, ,rrzAWrM0 11,jjAA eWW e0000 已已 知知 N點(diǎn)序列點(diǎn)序列x(n) ，0nN-1,其其z變換為變換為其中其中M：表示欲分析的復(fù)頻譜的點(diǎn)數(shù)。：表示欲分析的復(fù)頻譜的點(diǎn)數(shù)。M不一定等于不一定等于N。A，W 都為任意復(fù)數(shù)都為任意復(fù)數(shù),令令 一、一、CZTCZT的定義的定義( ) ( )( )( )NnkrnNnnrnzX zCZT x nx n z

33、x n A W1010代入中得, ,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 ej j0 0是是CZTCZT的起點(diǎn)的起點(diǎn), ,隨著隨著r r的變化的變化,r,r0 0,r,r1 1, ,r,rM-1M-1構(gòu)成構(gòu)成CZTCZT的變化路徑，對于的變化路徑，對于M-1M-1點(diǎn)其極坐標(biāo)為點(diǎn)其極坐標(biāo)為()()jj MMQA eWe001100CZTCZT在現(xiàn)在現(xiàn)Z Z平面上的變換路徑是一條平面上的變換路徑是一條螺旋線螺旋線

34、。（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的變換路徑為單位圓上的變換路徑為單位圓上的一段弧，起點(diǎn)為的一段弧，起點(diǎn)為P，終點(diǎn)為，終點(diǎn)為Q，且，且M不一定等不一定等于于N。變換求出該序列即由，為均勻分布在單位園上此時(shí)等分）時(shí)，（。即即（當(dāng)滿足下面特殊條件：DFTCZTzNNMWeeWWcAeAAbNMarNjjj221,)(01, 1)

35、(: )4(002000000()()() ()( )( ) ( )nr nrNNnnrnrnnrnr nNnnnrnrrnX zx n A Wx n A WWWWx n A WW22222222211222001222012利用 我們希望做的是頻譜分析，因此考慮我們希望做的是頻譜分析，因此考慮A0=W0=1時(shí)，時(shí)，在單位圓上在單位圓上CZT，且，且M不一定等于不一定等于N。( )( ), ( )()( ) (), ,()( )( )() ( )( ), ,( )nnnrNrnrrrrrg nx n A Wh nWX zWg n h rn rMX zg nh nWX zWg rh rkMWy

36、r222222221202220 110 11令由上式可知：可以由與的離散卷并乘得到，即：()rX z( )x nnnA W22rW22( )nh nW22( )g n( )y rCZTCZT的線性濾波計(jì)算步驟的線性濾波計(jì)算步驟二、二、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(

37、n)h(n)的實(shí)的實(shí)際長度應(yīng)為際長度應(yīng)為M M點(diǎn)。因此，可用點(diǎn)。因此，可用DFTDFT來實(shí)現(xiàn)兩者來實(shí)現(xiàn)兩者的卷積，具體步驟如下：的卷積，具體步驟如下：()( ),( )( ),.jjnnnnmAA eWW eAWA WnNg nnNnNAx ng nNnLLNML0022000000220101011012根據(jù)已知和即由已知 、求出的各值, 并得且使（1 1）計(jì)算并設(shè)置）計(jì)算并設(shè)置g(n)g(n)（2 2）計(jì)算并設(shè)置）計(jì)算并設(shè)置h(n)h(n)將將h(n)h(n)設(shè)置成長度為設(shè)置成長度為L L的序列，考慮到其為偶對的序列，考慮到其為偶對稱序列，且取稱序列，且取M M點(diǎn)（輸出點(diǎn)（輸出M M點(diǎn)序列

38、），取點(diǎn)序列），取()( )nL nWnMh nMnLNLNnLW 222201011如下圖所示如下圖所示（3 3）計(jì)算）計(jì)算h h(n)(n)和和g g(n)(n)的的DFTDFT，得到，得到L L點(diǎn)序列點(diǎn)序列H(k)和和G(k)。（4 4）令）令Y(k) =H(k) G(k)（乘積）后作乘積）后作Y(k) 的的IDFTIDFT（反變換）得到時(shí)域輸出序列反變換）得到時(shí)域輸出序列y(r) 。（5 5）?。┤(r)y(r)的前的前M M點(diǎn)，并乘以點(diǎn)，并乘以W W-r2/2-r2/2, ,則得最后的輸出則得最后的輸出X(zX(zr r) )，即，即()( )rrX zWg r22 與標(biāo)準(zhǔn)與標(biāo)準(zhǔn)F

39、FT算法相比，算法相比，CZT算法有以下特點(diǎn)：算法有以下特點(diǎn)：（1）輸入序列長）輸入序列長度度N及輸出序列長及輸出序列長度度M不需要相等不需要相等，且且N及及M不必是高度合成數(shù)，二者均可為素?cái)?shù)。不必是高度合成數(shù)，二者均可為素?cái)?shù)。（2）Zk的角間隔是任意的，的角間隔是任意的，說明說明其頻率分辨率也是其頻率分辨率也是任意任意可控可控的的，角間隔小，分辨率高，反之，分辨，角間隔小，分辨率高，反之，分辨率低。率低。（3）周線不必是）周線不必是z平面上的圓，在語音分析中螺旋平面上的圓，在語音分析中螺旋周線具有某些優(yōu)點(diǎn)。周線具有某些優(yōu)點(diǎn)。（4）由于由于起始點(diǎn)起始點(diǎn)z0可任意選定，因此可以從任意頻可任意選定

40、，因此可以從任意頻率上開始對輸入數(shù)據(jù)進(jìn)行窄帶高分辨率的分析。率上開始對輸入數(shù)據(jù)進(jìn)行窄帶高分辨率的分析?？傊?，總之，CZT算法具有很大的靈活性算法具有很大的靈活性。nkNW1)IDFT1)IDFT的運(yùn)算方法的運(yùn)算方法101( )IDFT( )( )NnkNkx nX kX k WN10()D FT ( )( )NnkNnXkx nx n WIDFT： DFT：以上所討論的以上所討論的FFTFFT算法可用于算法可用于IDFTIDFT運(yùn)算運(yùn)算簡稱為簡稱為IFFTIFFT比較比較IDFTIDFT的定義式：的定義式：IDFTIDFT與與DFTDFT的差別：的差別： 1 1）把）把DFTDFT中的每一個(gè)系

41、數(shù)中的每一個(gè)系數(shù) 改為改為 ， 2 2）再乘以常數(shù)）再乘以常數(shù) 1/N 1/N ，nkNW10)(1)(NknkNWkXNnx)(1)(1)(10kXDFTNWkXNnxNknkN)(kX 第二種方法，完全不需要改動(dòng)第二種方法，完全不需要改動(dòng)FFT程序，而是直接利用它作程序，而是直接利用它作 IFFT。 考慮到考慮到 故故 IFFT計(jì)算分三步：計(jì)算分三步： 將將X（k）取共軛（虛部乘以）取共軛（虛部乘以-1） 對對 直接作直接作FFT 對對FFT的結(jié)果取共軛并乘以的結(jié)果取共軛并乘以1/N，得，得x（n）。）。2）實(shí)數(shù)序列的）實(shí)數(shù)序列的FFT 以上討論的以上討論的FFT算法都是復(fù)數(shù)運(yùn)算算法都是復(fù)

42、數(shù)運(yùn)算,包括序列包括序列x(n)也認(rèn)為是復(fù)數(shù)也認(rèn)為是復(fù)數(shù),但大多數(shù)場合但大多數(shù)場合,信號是實(shí)數(shù)序列信號是實(shí)數(shù)序列,任何實(shí)任何實(shí)數(shù)都可看成虛部為零的復(fù)數(shù)數(shù)都可看成虛部為零的復(fù)數(shù),例如例如,求某實(shí)信號求某實(shí)信號x(n)的復(fù)的復(fù)譜譜,可認(rèn)為是將實(shí)信號加上數(shù)值為零的虛部變成復(fù)信號可認(rèn)為是將實(shí)信號加上數(shù)值為零的虛部變成復(fù)信號(x(n)+j0),再用再用FFT求其離散傅里葉變換。這種作法很求其離散傅里葉變換。這種作法很不經(jīng)濟(jì)不經(jīng)濟(jì),因?yàn)榘褜?shí)序列變成復(fù)序列因?yàn)榘褜?shí)序列變成復(fù)序列,存儲器要增加一倍存儲器要增加一倍,且計(jì)算機(jī)運(yùn)行時(shí)且計(jì)算機(jī)運(yùn)行時(shí),即使虛部為零即使虛部為零,也要進(jìn)行涉及虛部的也要進(jìn)行涉及虛部的運(yùn)算

43、運(yùn)算,浪費(fèi)了運(yùn)算量。合理的解決方法是利用復(fù)數(shù)據(jù)浪費(fèi)了運(yùn)算量。合理的解決方法是利用復(fù)數(shù)據(jù)FFT對實(shí)數(shù)據(jù)進(jìn)行有效計(jì)算對實(shí)數(shù)據(jù)進(jìn)行有效計(jì)算,下面介紹兩種方法。下面介紹兩種方法。 （1）用）用 一個(gè)一個(gè)N點(diǎn)點(diǎn)FFT同時(shí)計(jì)算兩個(gè)同時(shí)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的點(diǎn)實(shí)序列的DFT 設(shè)設(shè)x (n)、y (n)是彼此獨(dú)立的兩個(gè)是彼此獨(dú)立的兩個(gè)N點(diǎn)實(shí)序列點(diǎn)實(shí)序列,且且 X (k)=DFTx (n) ， Y (k)=DFTy(n) 則則X (k)、Y(k)可通過一次可通過一次FFT運(yùn)算同時(shí)獲得。運(yùn)算同時(shí)獲得。 首先將首先將x (n)、y(n)分別當(dāng)作一復(fù)序列的實(shí)部及虛部分別當(dāng)作一復(fù)序列的實(shí)部及虛部,令令 g(n)=x (n

44、)+jy(n)通過通過FFT運(yùn)算可獲得運(yùn)算可獲得g(n)的的DFT值值 kjGkGkjYkjXkYkXkYkjYkjXkXkjYkXkGirriiririr kNGkGjkNGkGkNGkGkXngiirr212121ReDFT*利用離散傅里葉變換的共軛對稱性利用離散傅里葉變換的共軛對稱性通過通過g(n)的的FFT運(yùn)算結(jié)果運(yùn)算結(jié)果G(k),由上式也可得到由上式也可得到Y(jié)(k) 的值。的值。 kNGkGjkNGkGkNGkGkjYngjiirr212121ImDFT* kNGkGjkNGkGkYrrii2121 （2）用一個(gè)）用一個(gè)N點(diǎn)的點(diǎn)的FFT運(yùn)算獲得一個(gè)運(yùn)算獲得一個(gè)2N點(diǎn)實(shí)序列的點(diǎn)實(shí)序列的

45、DFT 設(shè)x(n)是2N點(diǎn)的實(shí)序列,現(xiàn)人為地將x(n)分為偶數(shù)組x1 (n)和奇數(shù)組x2 (n) x1 (n)= x(2n) n=0,1,N-1 x2 (n)= x(2n+1) n=0,1,N-1然后將x1 (n) 及x2 (n) 組成一個(gè)復(fù)序列： y(n)= x1 (n) +j x2 (n) 通過N點(diǎn)FFT運(yùn)算可得到：Y(k)=X1(k)+jX2(k) ，N點(diǎn)根據(jù)前面的討論，得到)()(2)()()(21)(*2*1kNYkYjkXkNYkYkX 為求為求 2N 點(diǎn)點(diǎn) x(n)所對應(yīng)所對應(yīng) X(k) ，需求出，需求出 X(k)與與 X1 (k) 、 X2 (k) 的的關(guān)系關(guān)系 ： 10)12

46、(21022120) 12()2()()(NnknNNnnkNNnnkWnxWnxWnxkX10210) 12()2(NnnkNkNNnnkNWnxWWnx 1011022101011) 12()()()2()()(NnnkNNnnkNNnNnnkNnkNWnxWnxkXWnxWnxkX而1）由）由x1(n)及及x2(n)組成復(fù)序列，經(jīng)組成復(fù)序列，經(jīng)FFT運(yùn)算求得運(yùn)算求得 Y(k)，2）利用共軛對稱性求出）利用共軛對稱性求出 X1(k)、X2(k)，3）最后利用上式求出）最后利用上式求出 X（k）, 達(dá)到用一個(gè)達(dá)到用一個(gè)N點(diǎn)的點(diǎn)的FFT計(jì)計(jì)算一個(gè)算一個(gè)2N點(diǎn)的實(shí)序列的點(diǎn)的實(shí)序列的DFT的目的。

47、的目的。 X(k)=X1(k)+W2Nk X2(k)所以所以 3) 線性卷積的線性卷積的FFT算法算法 線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一,許多許多重要應(yīng)用都建立在這一理論基礎(chǔ)上重要應(yīng)用都建立在這一理論基礎(chǔ)上,如卷積濾波等。如卷積濾波等。 以前曾討論了用圓周卷積計(jì)算線性卷積的方法歸納以前曾討論了用圓周卷積計(jì)算線性卷積的方法歸納如下如下: 將長為將長為N2的序列的序列x(n)延長到延長到L,補(bǔ)補(bǔ)L-N2個(gè)零，個(gè)零， 將長為將長為N1的序列的序列h(n)延長到延長到L,補(bǔ)補(bǔ)L-N1個(gè)零，個(gè)零， 如果如果LN1+N2-1,則圓周卷積與線性卷積相等則圓周卷積與

48、線性卷積相等,此時(shí)此時(shí),可用可用FFT計(jì)算線性卷積，方法如下計(jì)算線性卷積，方法如下: a.計(jì)算計(jì)算X(k)=FFTx(n)b. 求求H(k)=FFTh(n)c. 求求Y(k)=H(k)X(k) k=0-L-1d. 求求y(n)=IFFTY(k) n=0-L-1 可見，只要進(jìn)行二次可見，只要進(jìn)行二次FFT,一次一次IFFT就可完成就可完成線性卷積計(jì)算。線性卷積計(jì)算。 計(jì)算表明計(jì)算表明,L32時(shí)時(shí),上述計(jì)算線性卷積的方法比上述計(jì)算線性卷積的方法比直接計(jì)算線卷積有明顯的優(yōu)越性直接計(jì)算線卷積有明顯的優(yōu)越性,因此因此,也稱上述循也稱上述循環(huán)卷積方法為快速卷積法。環(huán)卷積方法為快速卷積法。 上述結(jié)論適用于上

49、述結(jié)論適用于 x(n)、h(n) 兩序列長度比較接近兩序列長度比較接近或相等的情況或相等的情況,如果如果x(n)、h(n) 長度相差較多長度相差較多,例如例如, h(n) 為某濾波器的單位脈沖響應(yīng)為某濾波器的單位脈沖響應(yīng),長度有限長度有限,用來處理一個(gè)用來處理一個(gè)很長的輸入信號很長的輸入信號 x(n)，或者處理一個(gè)連續(xù)不斷的信號，或者處理一個(gè)連續(xù)不斷的信號，按上述方法按上述方法,有三個(gè)問題：有三個(gè)問題：（1） h(n) 要補(bǔ)許多零再進(jìn)行計(jì)算要補(bǔ)許多零再進(jìn)行計(jì)算,計(jì)算量有很大的浪計(jì)算量有很大的浪費(fèi)，或者根本不能實(shí)現(xiàn)。費(fèi)，或者根本不能實(shí)現(xiàn)。（2）系統(tǒng)的存儲量要求極高。）系統(tǒng)的存儲量要求極高。（3）

50、帶來了很大的系統(tǒng)延遲。）帶來了很大的系統(tǒng)延遲。 為了克服上述三個(gè)問題，保持快速卷積法的優(yōu)越為了克服上述三個(gè)問題，保持快速卷積法的優(yōu)越性性,可將可將 x(n) 分為許多段分為許多段,每段的長度與每段的長度與 h(n) 接近接近 , 處處理方法有兩種：理方法有兩種：h(n)x(n)01) 1()()(22NiniNnxnxiiinxnx)()(iiiinynhnxnhnxny)()(*)()(*)()()(*)()(nhnxnyii則輸入序列可表為：于是輸出可分解為： 其中 假定 xi(n) 表示 x（n）序列的第i段 ： 1）先對 h（n）及 xi（n）補(bǔ)零，補(bǔ)到具有N點(diǎn)長度，N=N1+N2-1

51、。 一般選 N=2M。 iinyny)()(由于 yi（n）的長度為N1，而xi（n）的長度為N2，因此相鄰兩段 yi（n）序列必然有N-N2=N1-1點(diǎn)發(fā)生重疊。2）用基2 FFT計(jì)算 yi（n）=xi（n）*h（n）。3）重疊部分相加構(gòu)成最后的輸出序列。計(jì)算步驟：計(jì)算步驟：a. 事先準(zhǔn)備好濾波器參數(shù)事先準(zhǔn)備好濾波器參數(shù) H（k）=DFTh(n)，N點(diǎn)點(diǎn)b. 用用N點(diǎn)點(diǎn)FFT計(jì)算計(jì)算Xi（k）=DFTxi(n)c. Yi(k)=Xi(k)H(k)d. 用用N點(diǎn)點(diǎn)IFFT求求 yi（n）=IDFTYi(k)e. 將重疊部分相加將重疊部分相加 這種方法和第一種方法稍有不同，即將上面分段序列中補(bǔ)零

52、的部分不是補(bǔ)零，而是保留原來的輸入序列值，這時(shí)，如利用DFT實(shí)現(xiàn)h(n)和xi(n)的循環(huán)卷積，則每段卷積結(jié)果中有N1-1個(gè)點(diǎn)不等于線性卷積值需舍去。 重疊保留法與重疊相加法的計(jì)算量差不多，但省去了重疊相加法最后的相加運(yùn)算。 y0(n)中的中的N1 1, L 1點(diǎn)對應(yīng)于線性卷積點(diǎn)對應(yīng)于線性卷積 x(n) h(n)中的中的0 , N2-1點(diǎn)點(diǎn)y1(n)中的中的N1 1, L 1點(diǎn)對應(yīng)于線性卷積點(diǎn)對應(yīng)于線性卷積 x(n) h(n)中的中的N2,2N2-1點(diǎn)點(diǎn)y2(n)中的中的N1 1, L 1點(diǎn)對應(yīng)于線性卷積點(diǎn)對應(yīng)于線性卷積 x(n) h(n)中的中的2N2,3N2-1點(diǎn)點(diǎn)依此類推依此類推 ，并將

53、，并將yi(n)拼接起來構(gòu)成拼接起來構(gòu)成y (n) 4）用）用FFT計(jì)算相關(guān)函數(shù)計(jì)算相關(guān)函數(shù) 相關(guān)的概念很重要，互相關(guān)運(yùn)算廣泛應(yīng)用于信號分析與統(tǒng)計(jì)分析，如通過相關(guān)函數(shù)峰值的檢測測量兩個(gè)信號的時(shí)延差等。 兩個(gè)長為N的實(shí)離散時(shí)間序列 x（n）與y（n）的互相關(guān)函數(shù)定義為 1010)()()()()(NnNnxynynxnynxr則可以證明，則可以證明，rxy()的離散傅里葉變換為的離散傅里葉變換為 Rxy（k）=X*(k)Y(k) 其中其中 X(k)=DFTx(n), Y(k)=DFTy(n), Rxy(k)=DFTrxy() ， 0kN-1互相關(guān)函數(shù)定義為 x(n)及y(n)的卷積公式 相比較，

54、我們可以得到相關(guān)和卷積的時(shí)域關(guān)系： 1010)()()()()(NnNnxymnynxnymnxmr)()()()()(10mymxnynmxmfNn)()()()()()()(1010mymxnynmxnymnxmrNnNnxy10102)()(1)()()(NnNkkNjxyekYkXNnynxr因 得 證畢。)(*)()(DFTkXnRnxNN 當(dāng)x（n）=y（n）時(shí)，得到x（n）的自相關(guān)函數(shù)為： 維納辛欽定理： 自相關(guān)函數(shù)與信號功率譜互為傅立葉變換對。 10)()()(NnxxnxnxrkNjNkekXN2102| )(|1 上面的推導(dǎo)表明，互相關(guān)和自相關(guān)函數(shù)的計(jì)算可利用FFT實(shí)現(xiàn)。

55、由于離散傅里葉變換隱含著周期性，所以用FFT計(jì)算離散相關(guān)函數(shù)也是對周期序列而言的。 直接做N點(diǎn)FFT相當(dāng)于對兩個(gè)N點(diǎn)序列x(n)、y(n)作周期延拓，作相關(guān)后再取主值（類似圓周卷積）。 實(shí)際一般要求的是兩個(gè)有限長序列的線性相關(guān)，為避免混淆，需采用與循環(huán)卷積求線性卷積相類似的方法，先將序列延長補(bǔ)0后再用上述方法。11)(mNmrxy10)(Nmmrxy(5) 對R（k）作 IFFT，取后N-1項(xiàng)，得取前N項(xiàng)，得 （1） 設(shè)x(n)和y(n)的長均為N，求線性相關(guān)；（2）為了使兩個(gè)有限長序列的線性相關(guān)可用其循環(huán)相關(guān)代替而不產(chǎn)生混淆，選擇周期 L2N-1，且L=2m，以使用FFT，將x(n)，y(n)補(bǔ)零至長為L。 （3） 用FFT計(jì)算X(k)，Y(k)（k=0，1，L-1）（4） R（k）=X*（k）y（k）幅度例8-20-1001020-50050100150200250300m-20-1001020-50050100150200250300m幅度幅度(a) (b)延遲序列的互相關(guān)函數(shù)(a)和自相關(guān)函數(shù)(b) 5）用）用FFT計(jì)算二維離散的傅里葉變換計(jì)算二維離散的傅里葉變換 二維信號有圖象信號、時(shí)空信號、時(shí)頻信號等。二維離散傅里葉變換可用于處