数字信号处理第四章

1、数字信号处理周治国2010.03第四章快速傅里叶变换§4-8 线性调频变换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，统一，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 ?¹质)数）, ，X $k= 01-M,.,N3)M（L(k,Chirp-Z 变换§4-8 线性调频 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)参数几何意义(, A £ 1), 取样起始点的矢量长度1)A0：z02) q0 ： argz0,(> 0 / < 0), 取样起始点的相角（角频率）f0 ： 取样点z3)k ,zk +1间的角频率差f0 >0,zk的路径为逆时针旋转zk的路径为顺时针旋

4、转< ,004)W0 ： 取值决定zk的路径是向内/ 外盘旋W0 <,1zk的路径是向外弯曲k的z 路径是向内弯曲k的z 路径是半径为A0的一段圆弧W1>,0W1=0A0 = 1时, 即圆上的一部分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)变为：+ 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时00n2F对时间序数n的微分值为nF0角位移02瞬时频率随时间成线性变化® 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的运算流程图三、运算/实现步骤：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)计算 f(n)*h(n)，f (n),0 £ n £ N -1n=0,1,M-1f ¢(n)补零至L点f (n) * h(n)LL > N + M -1L = 2nh(n),-(N -1) £ n £ M -1(3)计算 F(r)H(r)

8、h¢(n)´ 3logl + L22四、运算量估算3： Llog + N + L + ML*22(M,N>50CZT优于直接计算)五、CZT算法的特点1) " x(n),$ X ( zk ),0 £ n £ N -10 £ k £ M -1M ¹ N ,¹ 1zk2),均可为质数 任意情况z0 ¹ A0 ®q0 ¹ 03) 取样起始点z0任选：k = 0,1,., M -1X (zk ),4) f0 可任意取值zk , zk +1 的角间隔（频率）任意进行窄带高分辨分析

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计算卷积如何由卷积计算DFT？§4-9 细化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的应用一、利用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补零X ¢(k )H ¢(k )N1 » N2N1 >> N21.2.3.运算量比较：分段卷积x(n) = x*(n),h(n) = h*(n)思考：补零会造成卷积计算误差吗？1. 直接卷积：N22. 快速卷积：3Nlog2N一、利用FFT求卷积快速卷积计算步骤(1)x(n) N1 h(n) N2y(n) = x(n) * h(n)(2)补零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卷积"实序列 g(n), s(n), h(n)0 £ n £ N -1G(k ), S (k), H (k ) 0 £ k £ N -1用一次FFT实现两个卷积运算ì 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的应用一、利用FFT求卷积高效的FFT卷积应用：(1) 一个系统同时通过两种输入信号(2) 一个系统同时处理长序列分段过滤中的两个片段(3)一个信号同时通过两个系统二、利用FFT求相关快速相关"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)补零FFTIFFTX '* (k )Y ¢(k )z(n)N1 » N21.N1 » N21.2.x(n) = y(n) ® 2.N1 >> N 2x(n) = x*(n)N >> N12自相关3.x(n) = x*(n),y(n) = y*(n)3.二、利用FFT求相关快

17、速相关计算步骤(1)x(n) N1 y(n) N2N1z(n) = å x* (k ) y(n + k )k =0(2)补零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、设有两个有限长序列，试给出用基-2 FFT计算其线性卷积的方法步骤（要求尽量减少乘法运算次数），并与用线性卷积定义直接计算时的运算量做以比较。往年：5、已知序列xn和y(n)，长度分别为N和M，试给用仅用基-2 FFT正变换快速计算其线性卷积的方法步骤， 要求尽量减少乘法运算次数。§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三、运算量估算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.利用下标，把大N点的DFT化成互素的小N点的DFT；2.把小N点的DFT化成循环卷积；3.找出计算小N点卷积的快速算法，从而得到小N点的DFT的快速算法；4.由小N点的DFT求出大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)