數(shù)字信號(hào)處理第四章

1、數(shù)字信號(hào)處理周治國2010.03第四章快速傅里葉變換§4-8 線性調(diào)頻變換Z (Chirp-Z Transform)變換一、問題的提出- j 2p knN -1DX (k ) = DFTx(n) = å xn(" xn(), n= 0,1,.,N -1= X (z ) eNj 2 ke Nkz k =n=0i) N=ML，2 FFT算法 （基-2，統(tǒng)一，0k , =1基）,.,N-1i(i) FF) T ® X ,zk = 0,1N -,.,1j 2p kkz k =eN（X(z)在 |z|=1 上等間隔取樣值）問題：$X=0,M-11)(), kzk,

2、.,1?¹1zk2) $ X (k ) ,k = 0,1,., M -1, M < N ?¹質(zhì))數(shù)）, ，X $k= 01-M,.,N3)M（L(k,Chirp-Z 變換§4-8 線性調(diào)頻 Z 變換(Chirp-Z Transform)二、算法原理" x(n),0 £ n £ N1«N -1X (z) = å x(n)z -n n=0令D= AW,-kk = 0,1,.,M -1zkDA = A e j圖4-26(P.152)00D- jf0W =W0ek = 0,1,., M -1,jq×W -

3、k × e jkf0z= A e k = 0,1,., M -10k00Djq= A Ðqz=A e00000q +f )-z =1j (A We00100q +kf )z=- kj (A We00k00q +( M -1)f -( M -= A W1)jze00M -100圖4-26(P.152)參數(shù)幾何意義(, A £ 1), 取樣起始點(diǎn)的矢量長度1)A0：z02) q0 ： argz0,(> 0 / < 0), 取樣起始點(diǎn)的相角（角頻率）f0 ： 取樣點(diǎn)z3)k ,zk +1間的角頻率差f0 >0,zk的路徑為逆時(shí)針旋轉(zhuǎn)zk的路徑為順時(shí)針旋

4、轉(zhuǎn)< ,004)W0 ： 取值決定zk的路徑是向內(nèi)/ 外盤旋W0 <,1zk的路徑是向外彎曲k的z 路徑是向內(nèi)彎曲k的z 路徑是半徑為A0的一段圓弧W1>,0W1=0A0 = 1時(shí), 即圓上的一部分1) A0 =1,可見，= 00= 2pN= 1, f¾¾®X ( z ) = X (k ) = DFTx(n)2) W00kk0,1,., N13) M = NDFT也可視為CZT的一種特例一般情況：N -1X (z ) = å x(n) A-nW nk0 £ k £ M -1(4-62)kn=0利用公式：nk = 1

5、n2 + k 2 - (k - n)2 2nk = 1 n22式(4-62)變?yōu)椋? k 2- (k - n)2 N -1X (z ) = å x(n) A-nW nkkn=0N -1n22 Wk 22- 12(k -n)2= å x(n) A-nWWn=0k 22n22- 1N -12(k -n)2åx(n) A-nW= WWn=0 N -1k 22å f (n)h(k - n)= Wk = 0,1 . M -1式中：n=0n22(4-65)Dn = 0,1 .N -1f (n) = x(n) A-nW()2n- n22DFn = ?jh(n) =W=

6、 e2W =1時(shí)00n2F對(duì)時(shí)間序數(shù)n的微分值為nF0角位移02瞬時(shí)頻率隨時(shí)間成線性變化® Chirp Signal ® CZTN -1ån=0n22-nX (z ) =nkx(n) AWDf (n) = x(n) A-nWk()n2k 22n22N -1Då f (n)h(k - n)n=0-Fj= Weh(n) =W=20f(n)g(k)x(n),n=0,1,N-1X(zk),k=0,1,M-1h(n)n22k 22A-nWW圖4-27 CZT的運(yùn)算流程圖三、運(yùn)算/實(shí)現(xiàn)步驟：x(n),n=0,1,N-1f(n)g(k)X(zk),k=0,1,M-1h

7、(n)n22k 22A-nWW1 要求X(zk)n2A ,q ,W ,f® A-nW,n = 0,1,.,N -120000- n20 £ n £ N -1x(n),W2f (n), 0 £ n £ N -1h(n), "n´ N(2)計(jì)算 f(n)*h(n)，f (n),0 £ n £ N -1n=0,1,M-1f ¢(n)補(bǔ)零至L點(diǎn)f (n) * h(n)LL > N + M -1L = 2nh(n),-(N -1) £ n £ M -1(3)計(jì)算 F(r)H(r)

8、h¢(n)´ 3logl + L22四、運(yùn)算量估算3： Llog + N + L + ML*22(M,N>50CZT優(yōu)于直接計(jì)算)五、CZT算法的特點(diǎn)1) " x(n),$ X ( zk ),0 £ n £ N -10 £ k £ M -1M ¹ N ,¹ 1zk2),均可為質(zhì)數(shù) 任意情況z0 ¹ A0 ®q0 ¹ 03) 取樣起始點(diǎn)z0任選：k = 0,1,., M -1X (zk ),4) f0 可任意取值zk , zk +1 的角間隔（頻率）任意進(jìn)行窄帶高分辨分析

9、2pM=¹ 0,00頻率分辨率可變M > N , A = 1,W = 100M ¹ pqj 2pN5) A = 1,W = e, "NCZT ® X (zk ) = DFTx(n),"M, ,., Mk =(N ¹ pl)DFT的推廣第三章 由DFT計(jì)算卷積如何由卷積計(jì)算DFT？§4-9 細(xì)化FFT算法(Zoom FFT or ZFFT)一、問題提出1) FFT/DFT：分辨率 fN=fs/N ，(0 fs)D¯® "N,¯？Ns® "fs , N ­

10、;®tp =NT ­？2) "N , fs , DfN ¯?(0, fs ) ® ( f1, f2 ),f1 , f2 < fsZoomFFT(ZFFT )二、算法原理 (詳見圖4-30/P157)"x(n),0 £ n £ N -1- j 2fd n- j 2pfd nT = x(n)e0 £ n £ N -1x (n) = x(n)ef s1Dwd = 2pfd)X (e jw ) = X (e j(w+wd ) )1¢X(e) = X (e jj)H (e j11L= 2p

11、 k,k = 0,1,., M -1, M= (N , ¹ N )重新取樣WkM¹ fsfsMx¢(n) ,0 £ n £ M -1, M = 2nfs¹fs1fAsMD¢A =0 £ k £ M -1X1 (k ) ,BB 要分析分頻寬§4-10 FFT的應(yīng)用一、利用FFT求卷積快速卷積" x(n)0 £ n £ N110 £ n £ N2 -1h(n)N1 1N2 1å x(l)h(n - l) = å h(l)x(n -

12、 l)$ x(n) * h(n) =l =0l =0x¢(n)h¢(n)x(n)h(n)FFTIFFT補(bǔ)零X ¢(k )H ¢(k )N1 » N2N1 >> N21.2.3.運(yùn)算量比較：分段卷積x(n) = x*(n),h(n) = h*(n)思考：補(bǔ)零會(huì)造成卷積計(jì)算誤差嗎？1. 直接卷積：N22. 快速卷積：3Nlog2N一、利用FFT求卷積快速卷積計(jì)算步驟(1)x(n) N1 h(n) N2y(n) = x(n) * h(n)(2)補(bǔ)零N ³ N + NN = 2v12x '(n)h '(n)N -1

13、y '(n) = x '(n) Ä h '(n) = å x '(k)h '(n - k)Nk0RN (n)(3)FFT : x '(n) ® X '(k )(4)Y ' k= X ' k H ' kh '(n) ® H '(k )ù*éN -1N -1115 IFFT : y ' n = åk =0(6) y(n)åW - nk=Y '*W nkY ' kkêúNNNN

14、35; k =0û一、利用FFT求卷積高效的FFT卷積"實(shí)序列 g(n), s(n), h(n)0 £ n £ N -1G(k ), S (k), H (k ) 0 £ k £ N -1用一次FFT實(shí)現(xiàn)兩個(gè)卷積運(yùn)算ì y1(n) = g(n) Ä h(n)í y(n) = s(n) Ä h(n)：p(n) = g(n) + js(n)î 2則：DFT p(n) = P(k) = G(k) + jS (k )令：Y (k) = H (k )P(k )y(n) = IFFTY (k ) =

15、 p(n) Ä h(n)= (n) +s(n) Ä h(n) =(n) Ä h(n) +s(n) Ä h(n)ì y1 (n) = g(n) Ä h(n) = Re y(n)因此：í y(n) = s(n)h(n) = Im y(n)î2§4-10 FFT的應(yīng)用一、利用FFT求卷積高效的FFT卷積應(yīng)用：(1) 一個(gè)系統(tǒng)同時(shí)通過兩種輸入信號(hào)(2) 一個(gè)系統(tǒng)同時(shí)處理長序列分段過濾中的兩個(gè)片段(3)一個(gè)信號(hào)同時(shí)通過兩個(gè)系統(tǒng)二、利用FFT求相關(guān)快速相關(guān)"0 £ n £ N1 -10

16、£ n £ N 2 -1x(n)y(n)N1 -1N2 -1z(n) = å x*(l) y(n + l)l =0= å y*(l)x(n + l)l =0$x¢(n)y¢(n)x(n)y(n)補(bǔ)零FFTIFFTX '* (k )Y ¢(k )z(n)N1 » N21.N1 » N21.2.x(n) = y(n) ® 2.N1 >> N 2x(n) = x*(n)N >> N12自相關(guān)3.x(n) = x*(n),y(n) = y*(n)3.二、利用FFT求相關(guān)快

17、速相關(guān)計(jì)算步驟(1)x(n) N1 y(n) N2N1z(n) = å x* (k ) y(n + k )k =0(2)補(bǔ)零N ³ N + NN = 2v12x '(n)y '(n)(3)FFT : x '(n) ® X '(k )(4)Z (k ) = X '* (k )Y '(k )y '(n) ® Y '(k )ù*N -1éN -111(5)IFFT : z '(n) = åZ (k )W -nk = åZ * (k )W nk

18、4;úNNNNë k =0ûk =0(6)z(n)往年：4、設(shè)有兩個(gè)有限長序列，試給出用基-2 FFT計(jì)算其線性卷積的方法步驟（要求盡量減少乘法運(yùn)算次數(shù)），并與用線性卷積定義直接計(jì)算時(shí)的運(yùn)算量做以比較。往年：5、已知序列xn和y(n)，長度分別為N和M，試給用僅用基-2 FFT正變換快速計(jì)算其線性卷積的方法步驟， 要求盡量減少乘法運(yùn)算次數(shù)。§4-11 2-D DFT/FFT 算法一、2-D DFT" x(m,n)0 £ n £ N -10 £ m £ M -1N = 2M = 221DX (k, l) =

19、 DFTx(m, n)0 £ k £ M -10 £ l £ N -1M -1 N -1åå=kmln Nx(m, n)WWMm=0 n=0M -1 N -Dx(m, n) 1 10 £ m £ M -10 £ n £ N -1åå-km-ln=MNX (k, l)WMWNk =0 l =0二、2-D FFT1. " n,A(k, n)n = 0,1,., N -1M -1å=k = 0,1,., M -1kmx(m, n)W,列Mm=0M* N 

20、0;logM222. " k,k = 0,1,., M -1N -1ån=0X (k, l) =l = 0,1,., N -1lnA(k, n)W,行NN2* M ´N2log三、運(yùn)算量估算1、2-D FFTNM= MNMNM ´log+N ´+ log) =NM2N2MMN2loglolog2222222、2-D DFT= (MN)2N2M 2§4-12 FFT的其它形式Winograd Fourier Transform Algorithm (WFTA):2 3 4 5 6 DFT ® X (k ),0 £ k

21、 £ N-1N DFT7 8 例：16 ´ 9 ´ 7 ´ 5 = 5040DFT9 16 2 4 833算法步驟：1.利用下標(biāo)，把大N點(diǎn)的DFT化成互素的小N點(diǎn)的DFT；2.把小N點(diǎn)的DFT化成循環(huán)卷積；3.找出計(jì)算小N點(diǎn)卷積的快速算法，從而得到小N點(diǎn)的DFT的快速算法；4.由小N點(diǎn)的DFT求出大N點(diǎn)的DFT。x(n)= x(0), x(1), x(2)x(14) = 0,1,2,14FFTX(k)= 1.0e+002 *x(n)= 051627384910111213142D-FFTX(k)= 1.0e+002 *1.0500-0.0750 + 0.

22、1032i-0.0750 + 0.0244i-0.0750 - 0.0244i-0.0750 - 0.1032i-0.3750 + 0.2165i0000-0.3750 - 0.2165i00001.0500-0.0750 + 0.3528i-0.0750 + 0.1685i-0.0750 + 0.1032i-0.0750 + 0.0675i-0.0750 + 0.0433i-0.0750 + 0.0244i-0.0750 + 0.0079i-0.0750 - 0.0079i-0.0750 - 0.0244i-0.0750 - 0.0433i-0.0750 - 0.0675i-0.0750 - 0.1032i-0.0750 - 0.1685i-0.0750 - 0.3528ix(n)= x(0), x(1), x(2)x(14) = 0,1,2,14 X(k)= 1.0e+002 *FFTx(n)= X(k)