DSP4_快速傅里葉變換

1、1第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）4.1 概述概述4.2 時間抽取基時間抽取基 2 算法算法4.3 頻率抽取基頻率抽取基 2 算法算法4.4 減少運算量的措施減少運算量的措施4.5 分裂基算法分裂基算法4.6 輸入、輸出取少數(shù)點的簡化算法輸入、輸出取少數(shù)點的簡化算法4.7 線性調(diào)頻線性調(diào)頻 Z 變換變換24.14.1 概述120120)( )0,1,11( )( )0,1,1Njnk NnNjnk NkX kx n ekNx nX k enNN（Fast Fourier-TransformFFT是是DFT的快速算法，的快速算法，不是新的變換方法不是新的變換方法3直

2、接計算直接計算DFTDFT的復(fù)雜度為的復(fù)雜度為O(NO(N2 2) )計算計算DFTDFT的計算量的計算量： 每算一個每算一個X X(k)(k)，需要，需要N N次復(fù)數(shù)乘法，次復(fù)數(shù)乘法，N-1N-1次加法次加法 因此，因此，N N點點DFTDFT需要需要N N* *N N次復(fù)數(shù)乘法，次復(fù)數(shù)乘法，N(N-1)N(N-1)次復(fù)數(shù)加法次復(fù)數(shù)加法盡管預(yù)先算好并保存旋轉(zhuǎn)因子盡管預(yù)先算好并保存旋轉(zhuǎn)因子 可節(jié)省部分運算，可節(jié)省部分運算，但按定義求但按定義求DFT的運算量仍然很大的運算量仍然很大kNW42421,212( ):10241048576():512,262144 !x nNNx n nNNN，解決

3、耗時的乘法問題是將解決耗時的乘法問題是將DSPDSP理論用于實際的理論用于實際的關(guān)鍵。特別是關(guān)鍵。特別是4040年前，計算機的速度相當慢。年前，計算機的速度相當慢。很多學(xué)者致力于解決很多學(xué)者致力于解決DFTDFT的快速計算問題。的快速計算問題。Cooley J W, Tukey J W. An algorithm for the machine computation of complex Fourier series.Mathematics of Computation, 1965, pp297301DSP的正式開端！5FFT 的思路：的思路：10)( )0,1,1NnknX kx n Wk

4、N（2/jNWe01.1W 2.1,1NmNWW3.N rrWW24.1NW 25.NrrWW 如何充分利用這些關(guān)系,4jWNjWN43/2/2kmkkNmNNWWW6.換底換底6 經(jīng)過周期性與對稱性簡化后經(jīng)過周期性與對稱性簡化后, ,容易容易發(fā)現(xiàn)發(fā)現(xiàn)DFTDFT運算中存在著不必要的重運算中存在著不必要的重復(fù)計算復(fù)計算 避免這種重復(fù)避免這種重復(fù), ,是簡化運算的關(guān)鍵是簡化運算的關(guān)鍵nknkWWN)(2DFTDFT的復(fù)雜度與點數(shù)的復(fù)雜度與點數(shù)N N有關(guān)！有關(guān)！7四點四點 DFT11111111(0)11(1)(2)1111(3)11xWWxxxWW0000012302460369(0)(0)(1

5、)(1)(2)(2)(3)(3)WWWWXxXWWWWxXxWWWWXxWWWW11111111(0)11(2)(1)1111(3)11xWWxxxWW16乘，乘，12加加811(0) (0)(2) (1)(3)(1) (0)(2) (1)(3)(2) (0)(2) (1)(3)(3) (0)(2) (1)(3)XxxxxXxxxxWXxxxxXxxxxW幾個乘法？幾個乘法？11(0)(2)xx(1)(3)xx(0)(1)XX(2)(3)XX111W(0)(2)xx(0)(2)xx(1)(3)xx(1)(3)xx94.2 4.2 時間抽取基時間抽取基 2 2 算法算法 N點點DFTN/2點點

6、DFTN/4點點 DFT 2點點 DFT 1個 2個 4個 N/2個問題是如何分最有效？可以對時間變量分問題是如何分最有效？可以對時間變量分（DIT)，也可對頻率變量分，也可對頻率變量分(DIF）（庫里（庫里-圖基算法）圖基算法）1010/2 1/2 12(21)00)( )(2 )(21)NnknNNrkrkNNrrX kx n Wxr WxrW（令：令：0,1,2 1rN21nr2nr/2 1/2 1/2/200(2 )(21)NNrkkrkNNNrrxr WWxrW11/2 1/2 1/2/200)(2 )(21)NNrkkrkNNNrrX kxrxrWWW（( )B k0,1,/2 1

7、kN()( )( )0,1,122kNNNX kA kW B kk( )A k( )X k( )A k( )B kkNW1()2NX k ( )( )( )0,1,12kNNX kA kW B kkA(k), B(k)為為N/2點的點的DFT12/2 1/4 1/4 1/4 1/4 12(21)/2/2/2/4/2/400000/2( ) , ( )221,0,1,.,/4 1,( )(2 )(4 )(42)(4 )(42)( )( )0,.,NNNNNrklklklkklkNNNNNNrllllkNA kB krlrllNA kxr Wxl WxlWxl WWxlWC kWD kkN繼續(xù)按照

8、上述方法分解，令：和則：/2/4 1/20/4 1/20/2 1/4 12/2/200/4 1(/4)( )( )0,.,/4 1( )(4 );0,1,.,/4 1/4( )(42);0,1,.,/4 1( )(21)(41)(4kNNrkNlNrkNlNNrklkNNrlA kNC kWD kkNC kxl WkNNDFTD kxlWkNB kxrWxlWxl兩個點的同理：/4 1/4 1/4 1(21)/2/4/2/4000/2/2/4 1/20/23)(41)(43)( )( )0,1,.,/4 1(/4)( )( )0,.,/4 1( )(41);0,1,.,/4 1( )(43)N

9、NNlklkklkNNNNlllkNkNNrkNlrNWxlWWxlWE kWF kkNB kNE kWF kkNE kxlWkNF kxlW/4 10/4;0,1,.,/4 1NklNDFTkN兩個點的13( ),( )A kB k 都是都是 N/2 點的點的 DFT，它們各自又，它們各自又可分成可分成 N/4 點的點的DFT，如此繼續(xù)分下去，直至，如此繼續(xù)分下去，直至兩點兩點DFT。兩點。兩點DFT不需要乘法運算：不需要乘法運算：(0)(0)(1)(1)(0)(1)XxxXxx20,1,1MNMmM對， 共可分次，即，每一級有每一級有 N/2 個如下的個如下的“蝶形蝶形”單元：單元：( )

10、mxp( )mxqrNW11( )mxp1( )mxq每分一次每分一次稱一稱一“級級”1411( )( )( )( )( )( )rNmmmrNmmmxpxpxq Wxqxpxq W即即: 每一個蝶形單元僅需一個復(fù)數(shù)乘法，兩個復(fù)每一個蝶形單元僅需一個復(fù)數(shù)乘法，兩個復(fù)數(shù)加法。數(shù)加法。p,q兩點構(gòu)成一個蝶形單元，并且這兩兩點構(gòu)成一個蝶形單元，并且這兩點不再參與別的蝶形單元的運算：點不再參與別的蝶形單元的運算：同址運算同址運算( )mxp( )mxqrNW11( )mxp1( )mxq15同址同址（in place）計算計算l每一級的蝶形運算的輸入和輸出在運算前后每一級的蝶形運算的輸入和輸出在運算前

11、后可以存儲在同一地址的存儲單元中，這種存可以存儲在同一地址的存儲單元中，這種存儲策略稱為同址計算儲策略稱為同址計算l同址計算可以節(jié)省存儲單元，從而降低算法同址計算可以節(jié)省存儲單元，從而降低算法對計算機存儲容量的要求，降低了硬件實現(xiàn)對計算機存儲容量的要求，降低了硬件實現(xiàn)的成本的成本16 所需運算量所需運算量：22log22logcaNNMMNMNMNN注意：注意： 因子的規(guī)律；因子的規(guī)律； 輸入序列的順序輸入序列的順序 碼位倒置碼位倒置rWcA第第0級級第第1級級第第2級級4組組2組組1組組17FFT算法與直接算法與直接DFT算法運算量的比較算法運算量的比較NN2計算計算量之量之比比 NN2計算

12、計算量之量之比比2414.012816 38444836.641644.025665 5361 02464.0864125.4512262 1442 304113.816256328.010241 048 5765 120204.83210288012.820484 194 30411 264372.464404919221.4NN2log2NN2log218 所需運算量所需運算量：22log22logcaNNMMNMNMNN注意：注意： 因子的規(guī)律因子的規(guī)律； 輸入序列的順序輸入序列的順序 碼位倒置碼位倒置rWcA第第0級級第第1級級第第2級級4組組2組組1組組19旋轉(zhuǎn)因子（指數(shù)因子）旋轉(zhuǎn)因

13、子（指數(shù)因子） 的確定：的確定： 隨著蝶形運算在隨著蝶形運算在DIT中的中的級數(shù)級數(shù)以及該級以及該級DIT節(jié)點數(shù)節(jié)點數(shù)的不同而有規(guī)律的變化的：的不同而有規(guī)律的變化的： kNWkNW級級 數(shù)數(shù) 的取值范圍的取值范圍 重復(fù)組數(shù)重復(fù)組數(shù) 第第0級級 第第1級級 第第2級級 第第m-1級級 第第M-1級級 1kNW0NW2/N0NW4/NNW4/N0NW0NW0NW8/NNW8/2NNW8/3NNWmNNW2/mNNW2/mNNW2/2mNNW2/2mmNNW2/) 12(112/NNW8/NmN 2/)log(2NM 20 所需運算量所需運算量：22log22logcaNNMMNMNMNN注意：注意

14、： 因子的規(guī)律；因子的規(guī)律； 輸入序列的順序輸入序列的順序 碼位倒置碼位倒置rWcA第第0級級第第1級級第第2級級4組組2組組1組組21( )nx n( )X kk0 000 000 0 100 001 1 010 010 2 110 011 3 001 100 4 101 101 5 011 110 67 111 111 7碼位倒置（倒讀，碼位倒置（倒讀，倒位序）：倒位序）：是指按二進制表是指按二進制表示的數(shù)字首尾位示的數(shù)字首尾位置顛倒，重新按置顛倒，重新按十進制讀數(shù)十進制讀數(shù)22倒位序的樹狀圖（倒位序的樹狀圖（N=8） 第一次分組觀察最低位第一次分組觀察最低位n023)0(x)4(x)2(

15、x)6(x) 1 (x)5(x)3(x)7(x)0(X) 1 (X)2(X)3(X)4(X)5(X)6(X)7(XDIT-FFT運算流程圖運算流程圖)0(2x) 1 (2x)2(2x)3(2x)4(2x)5(2x)6(2x)7(2x)0( 1x) 1 ( 1x)2( 1x)3( 1x)4( 1x)5( 1x)6( 1x)7( 1x組（群）組（群）mpq224DIT-FFT算法流程算法流程 全部計算分解為全部計算分解為M級，或稱為級，或稱為M次迭代次迭代 輸入序列輸入序列x(n)按碼位倒置順序排列，輸出序按碼位倒置順序排列，輸出序列列X(k)按自然順序排列按自然順序排列 每級都包含每級都包含N/

16、2個蝶形單元個蝶形單元 每級的若干蝶形單元組成每級的若干蝶形單元組成“組（或稱群）組（或稱群）”。第第0級群數(shù)為級群數(shù)為N/2，第，第1級群數(shù)為級群數(shù)為N/4，第第i級群數(shù)為級群數(shù)為N/2i+1，最后一級的群數(shù)為，最后一級的群數(shù)為1 每個蝶形單元都包含乘每個蝶形單元都包含乘W與加、減法各一次與加、減法各一次 同一級中，各個群的同一級中，各個群的W分布規(guī)律分布規(guī)律完全相同完全相同254.3 4.3 頻率抽取基頻率抽取基 2 2 算法算法/2 110/2/2 1/2 1/200/2 10)( )( )( )(/2) ( )( 1)(/2)NNnknkNNnn NNNnknkNkNNNnnNnkkN

17、nX kx nx nx nx nNx nx nNWWWW WW （2 ,210,1,2 1krkrrN令：（Sande-Tukey算法）算法）26/2 1/20/2 1/20(2 ) ( )(/2)(21) ( )(/2)NnrNnNnrNnXrx nx nNnXrx nx nNNWWW/2 1/20/2 1/20(2 )( )(21)( )NnrNnNnrNnXrg nXrh nWW各是各是 N/2 點的點的 DFT( )g n( )h n（換底）（換底）27( )( )(/2)( ) ( )(/2)nNg nx nx nNh nx nx nNW0,1,2Nn (0)x(0)h(0)g(1)

18、x(2)x(3)x(4)x(5)x(6)x(7)x(1)g(2)g(3)g(1)h(2)h(3)h111138W28W18W08W28將將 分解：分解： Decimation In Time, DIT 時間抽取時間抽取將將 分解：分解： Decimation In Freq. ,DIF 頻率抽取頻率抽取nk/2 1/20/2 1/20(2 )( )(21)( )NnrNnNnrNnXrg nXrh nWW各是各是 N/2 點的點的 DFT繼續(xù)分解，直到兩點繼續(xù)分解，直到兩點DFT DFT 注意注意 DIT DIT 和和 DIF DIF 的對偶性質(zhì)的對偶性質(zhì)29DIT分解規(guī)則：分解規(guī)則：規(guī)則規(guī)則

19、1 對時間進行偶奇分；對時間進行偶奇分；規(guī)則規(guī)則2 對頻率進行前后分。對頻率進行前后分。DIF分解規(guī)則：分解規(guī)則：規(guī)則規(guī)則1 對時間進行前后分；對時間進行前后分；規(guī)則規(guī)則2 對頻率進行偶奇分對頻率進行偶奇分 。30輸入正序，輸出倒序。注意輸入正序，輸出倒序。注意 因子的位置因子的位置rW31DIT與與DIF的異同的異同1. 相同運算量，相同運算量，相同分級數(shù)、每級蝶形數(shù)，相同分級數(shù)、每級蝶形數(shù)，同址運算特點同址運算特點2. DIT輸入碼位倒置，輸入碼位倒置，DIF輸出碼位倒置輸出碼位倒置不是本質(zhì)區(qū)別不是本質(zhì)區(qū)別：輸入輸出可以重排：輸入輸出可以重排3. 蝶形單元不同：蝶形單元不同：DIT先復(fù)乘后

20、加減，先復(fù)乘后加減， DIF先減再復(fù)乘先減再復(fù)乘 本質(zhì)區(qū)別！本質(zhì)區(qū)別！4. DIF、DIT蝶形單元互為蝶形單元互為易位易位（轉(zhuǎn)置）（轉(zhuǎn)置）（交換輸入輸出，所有支路反向）（交換輸入輸出，所有支路反向）32作業(yè)作業(yè) l 畫出畫出DIF蝶形單元，寫出迭蝶形單元，寫出迭代公式代公式33第第0級級第第1級級第第2級級4組組2組組1組組4.4 4.4 進一步減少運算量的措施進一步減少運算量的措施34,0,1,2 1rNWrNFFT中乘法運算主要來自和復(fù)指數(shù)相乘：中乘法運算主要來自和復(fù)指數(shù)相乘：/2,0,1,4 1rNWrN/4,0,1,8 1rNWrN42,0,1,0rrWrWr（1 組）（2 組）（4

21、組）（N/2 組）復(fù)數(shù)復(fù)數(shù)乘法乘法數(shù)數(shù)2log2NN（N/4 組）4.4.1 多類蝶形單元多類蝶形單元3582,0,1,2,3rmWr41,0,1rmWr20,0rmWr1,0,1,2 1rNmMWrN0141WWj 不需要乘法：不需要乘法：平凡平凡（trivial ）旋旋轉(zhuǎn)因子轉(zhuǎn)因子 旋轉(zhuǎn)因子旋轉(zhuǎn)因子（twiddle factor)36M 級，前兩級都是級，前兩級都是 ，去除之：，去除之：014,WW(2)2cNMM后后 M-2 級，含有級，含有248/22NNNNN個個014,NWW再去除之：再去除之：(3)22cNMM（復(fù)乘）（復(fù)乘）（ 如第如第2級共有級共有 N/8 組，組，每組每組2

22、個平凡因子個平凡因子）014,WW37 兩個復(fù)數(shù)相乘，需要四次實乘、兩次實加。兩個復(fù)數(shù)相乘，需要四次實乘、兩次實加。實現(xiàn)和實現(xiàn)和 的相乘，需兩次實乘，兩次實加。的相乘，需兩次實乘，兩次實加。N點點FFT中，有多少個中，有多少個 18(1) 2 /2Wjcjc虛實部相等，虛實部相等，trivial 18W 將所有平凡旋轉(zhuǎn)因子去除，或單獨考慮將所有平凡旋轉(zhuǎn)因子去除，或單獨考慮18W248/22NNNNN個個18WjccjW2/2)1 (3838W第第2級起，每組各有級起，每組各有138(27) 123(1)4RRMNMAN M實乘實乘實加實加各種算法比較的基礎(chǔ)各種算法比較的基礎(chǔ) 以上稱為多蝶形單元

23、運算以上稱為多蝶形單元運算 計算量的減少以增加程序復(fù)雜度為代價計算量的減少以增加程序復(fù)雜度為代價4(3)2(2)2(2)222RNNNMM39多蝶形單元運算所需計算量的比較多蝶形單元運算所需計算量的比較4404.4.2 旋轉(zhuǎn)因子的生成旋轉(zhuǎn)因子的生成產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運算速度。產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運算速度。方法一：方法一：在每一級運算中直接產(chǎn)生；在每一級運算中直接產(chǎn)生；方法二：方法二：在在FFT程序開始前預(yù)先計算出旋程序開始前預(yù)先計算出旋轉(zhuǎn)因子，存放在一個數(shù)組中，作為轉(zhuǎn)因子，存放在一個數(shù)組中，作為旋轉(zhuǎn)旋轉(zhuǎn)因子表因子表，在程序執(zhí)行過程中采用查表法，在程序執(zhí)行過程中采用查表法，這樣運算

24、速度可大大提高，缺點是旋轉(zhuǎn)這樣運算速度可大大提高，缺點是旋轉(zhuǎn)因子表要因子表要占用較多的內(nèi)存占用較多的內(nèi)存41作業(yè)作業(yè)2 P 181， T 實序列的實序列的FFT42 基基2 算法算法： 1965年，年， DSP 發(fā)展里程碑；發(fā)展里程碑； 基基4 算法算法 : 對基對基2 算法的改進；算法的改進； 分裂基算法分裂基算法： 1984年，年， 接近最優(yōu)的接近最優(yōu)的 FFT！4.5 4.5 分裂基分裂基 (Split-radix) (Split-radix) 算法算法2MN Winograd 算法算法：1976年提出，是具有鮮明特年提出，是具有鮮明特色的色的FFT! 用到較多的數(shù)論知識

25、，可用于用到較多的數(shù)論知識，可用于N不不等于等于2的整次冪情形的整次冪情形4311(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)xx= -j44(0)(1)xx(2)(3)xx(0)(2)XX(1)(3)XX1111j基基4 DIF 的基本單元：的基本單元：以以 4 為基，分解時級數(shù)可減少為基，分解時級數(shù)可減少1半，因此可半，因

26、此可減少乘法次數(shù)。減少乘法次數(shù)。242MMN 不需要乘法！45/2 1/20/2 1/20(2 ) ( )(/2)(21) ( )(/2)0,1,12NnrNnNnrNnXrx nx nNnXrx nx nNNNrWWW基基2 DIF: 旋轉(zhuǎn)因子都出現(xiàn)在奇序號項輸出，在求旋轉(zhuǎn)因子都出現(xiàn)在奇序號項輸出，在求出偶序號項時不需要乘法出偶序號項時不需要乘法。每一級都是如此每一級都是如此基基2 2 和基和基4 4 算法的比較：算法的比較：基基 4 446/4 1/40/4 1/40/4 1/40/4 1/40(4 ) ( )( )2(42) ( )( )(41) ( )( )3(43) ( )( )Nn

27、rNnNnrNnNnrNnNnrNnXra nc nnXra nc nNnXrb njd nNnXrb njd nNWWWWWWW3( )( )()( )()()2443( )( )()( )()()244NNNa nx nx nc nx nx nNNNb nx nx nd nx nx n令令則則47分析上述結(jié)果可知，在基分析上述結(jié)果可知，在基4 算法中，算法中，N/4個個偶序號輸出也要乘偶序號輸出也要乘W因子。而基因子。而基2 算法的算法的偶序號項都不要乘偶序號項都不要乘W因子。因子。如何將基2和基4的優(yōu)點都兼收？對偶序號項輸出用基對偶序號項輸出用基2 算法，算法， 對奇序號項輸出用基對奇序

28、號項輸出用基4算法。算法。48/2 1/20/4 1/40/4 1/40(2 )( )(41) ( )( )3(43) ( )( )NnrNnNnrNnNnrNnXra nnXrb njd nNnXrb njd nNWWWWW3( )( )()( )()()2443( )( )()( )()()244NNNa nx nx nc nx nx nNNNb nx nx nd nx nx n令令則則基基 2 / 4 算法算法4950 各種算法所需計算量的比較各種算法所需計算量的比較5143826( 1)39981622( 1)399MRMRMMNNAMNN 358211138463RRMMNNAMNN

29、2712334RRMMNNAMNN基基2基基4分裂基分裂基使使用用四四類類蝶蝶形形時時所所需需計計算算量量222RMNMM極限極限524.6 4.6 輸入輸出點數(shù)較少時的輸入輸出點數(shù)較少時的FFTFFTDFT：輸入：輸入N點，輸出點，輸出N點點, 輸入、輸出點數(shù)輸入、輸出點數(shù)相同。輸出的相同。輸出的N點均勻分布于單位圓上，頻域點均勻分布于單位圓上，頻域分辨率為分辨率為 2sNfN120120)( )0,1,11( )( )0,1,1Njnk NnNjnk NkX kx n ekNx nX k enNN（53在實際應(yīng)用中：在實際應(yīng)用中：1 1. . 當輸入點數(shù)極少時，若希望頻率分點較多，當輸入點

30、數(shù)極少時，若希望頻率分點較多，則需要補零，結(jié)果是增加了計算量則需要補零，結(jié)果是增加了計算量; ;2. 2. 對于對于窄帶窄帶信號，信號，我們只希望通帶內(nèi)分點密，我們只希望通帶內(nèi)分點密，帶外可以較疏，或根本不用計算。帶外可以較疏，或根本不用計算。1.Pruning1.Pruning（簡化（簡化FFTFFT）2. CZT2. CZT54（一）輸入端（一）輸入端 Pruning（ DIF ）不需要的不計算！不需要的不計算！一一. Pruning（剪枝）（剪枝）55 （二）輸出端（二）輸出端 Pruning（窄帶情況）（窄帶情況）不需要的不計算！56二、二、CZT（Chirp-Z變換）變換）線性調(diào)頻線

31、性調(diào)頻Z變換變換0)()(nnznxzX()sssssTjTTj Tjzeeeere 其中：其中：Z在其在其 ROC 內(nèi)取值，現(xiàn)為內(nèi)取值，現(xiàn)為Z指定一離散路徑：指定一離散路徑：00000000,0,1,1,rrjjrjjrrzAWrMAA eWW ezA eWeZ變換：變換：571100()( )( )NNnnnrrrnnX zx n zx n A W信號點數(shù)信號點數(shù) N 和變換路徑點數(shù)和變換路徑點數(shù) M 可以可以不相等！不相等！1, 1 , 0Mr58做做DFT時，時，Z變換在變換在單位圓上的等分的單位圓上的等分的 N個點上取值個點上取值CZT時，離散路時，離散路徑可在單位圓內(nèi)、徑可在單位圓

32、內(nèi)、外，或圓上外，或圓上rjrjreWeAz00002/jk Nkze59rjrjreWeAz0000CZT在在Z平面上的變換平面上的變換路徑是一條螺旋線：路徑是一條螺旋線：決定決定CZT的起點；的起點；決定變換路徑如決定變換路徑如何傾斜；何傾斜；決定變換的步長決定變換的步長00,A00W00APQ0ArW60rjrjreWeAz000001A 01W 001AW CZT變成了變成了DFT0001,0,AWMN00APQ0 時，起點在單位圓外，時，起點在單位圓外，反之在圓內(nèi)反之在圓內(nèi)時內(nèi)旋，反之外旋；時內(nèi)旋，反之外旋； 時時 CZT變換變換路徑路徑 為單位圓上一段弧，為單位圓上一段弧，ArW6

33、1CZT的特點的特點CZT可計算可計算單位圓上（單位圓上（希望得到的是信號希望得到的是信號的頻譜分析，故常在單位圓上實現(xiàn)的頻譜分析，故常在單位圓上實現(xiàn)CZT，即取即取A0=W0=1 ）任一段曲線上的任一段曲線上的Z 變換，變換，可任意給定起止頻率；可任意給定起止頻率；作變換時輸入的點數(shù)作變換時輸入的點數(shù)N和輸出點數(shù)和輸出點數(shù)M可以可以不相等；不相等；可達到頻域可達到頻域“細化細化”的目的。的目的。62CZT的計算：的計算：由定義：由定義：0000jjrrrrzAWA eWe22/2/2( )( )( )nnng nx n A Wh nW令令1100()( )( )NNnnnrrrnnX zx

34、n zx n A W由于：由于：2221() 2nrrnrn所以所以2221/2/2() /20()( )Nrnnr nrnX zWx n A WW二次相位復(fù)指數(shù)序列二次相位復(fù)指數(shù)序列或或Chirp信號信號或線性調(diào)頻信號或線性調(diào)頻信號6322221/20/2/21() /20()( ) () ( )* ( )( )( )( )* ( )( )0,1,1NrrnrrNr nnX zWg n h rnWg rh rWy ry rg rh rg n WrM，則：則：式中：式中：64 65CZT CZT 的實際計算方法：的實際計算方法：21() /20( )( )* ( )( )0,1,1Nr nny

35、 rg rh rg n WrM，( )g nN1. 是是 點系列，由點系列，由 所決定：所決定：( )x n2/2( )nh nW2/2( )( )nng nx n A W2. 是雙邊無窮長序列，由定義所決定：是雙邊無窮長序列，由定義所決定：( )h n663. 是是 點序列，由需要所決定。點序列，由需要所決定。 ()rX zM0n( )g n1N 0n( )h n0r( )y r1M r希望用希望用DFT實現(xiàn)實現(xiàn)截短截短延拓延拓67Step1( )01( )0()11h nnMh nMnLNh LnLNnL ) 1(MNL68Step 2.( ),0,1,1( ),0,1,1( )01g n

36、nNg nnNg nNnL求出( ),( ):g nh nL點序列點序列2/2Step 3.( ),( )( ),( );Step4.( )( )( ),( );Step5.()( )rrg nh nH k G kY kH k G ky rX zy r W（取前（取前M個點）個點）69與本章有關(guān)的與本章有關(guān)的MATLAB文件主要是文件主要是fft, ifft和和 czt.m。fft實現(xiàn)快速傅立葉變換，實現(xiàn)快速傅立葉變換，ifft實現(xiàn)快實現(xiàn)快速傅立葉反變換，速傅立葉反變換，czt.m實現(xiàn)線性調(diào)頻實現(xiàn)線性調(diào)頻Z變換變換 fft的調(diào)用格式是：的調(diào)用格式是：X=fft(x), 或或 X=fft(x，N)1. czt.m 調(diào)用格式是：調(diào)用格式是： Xczt(x, M, W, A) 。x是待變換的時域信號，其長度設(shè)為是待變換的時域信號，其長度設(shè)為N，M是是變換的長度，變換的長度，W確定變換的步長，確定變換的步長，A確定變確定變換的起點。若換的起點。若M=N, A=1, 則則CZT變成變成DFT70例例 設(shè)模擬信號設(shè)模擬信號 ，以，以 t = 0.01n (n=0: N-1) 進行取樣，試用進行取樣，試用fft函數(shù)對其做頻函數(shù)對其做頻譜分析。譜分析。N分別為：分別為：(1) N=45；(2