同济大学：《数字信号处理（DSP）》课程教学资源（PPT课件讲稿）第四章 快速傅里叶变换（8/9）

FFT不适用于 只研究信号的某一频段,要求对该频段抽样密 集,提高分辨率 ◆研究非单位圆上的抽样值; ◆需要准确计算N点DFT,且N为大的素数;等等 CZT算法:对z变换采用螺线抽样, chirp=z变换 线性调频z变换

八 、线性调频 z变换（CZT)算法 FFT不适用于： ¨ 只研究信号的某一频段，要求对该频段抽样密 集，提高分辨率； ¨ 研究非单位圆上的抽样值； ¨ 需要准确计算N点DFT，且N为大的素数；等等。 CZT算法：对z变换采用螺线抽样，chirp-z变换 线性调频 z变换

1、算法原理 N点有限长序列,其变换:X(=)=∑x(m)n 0 沿平面上的一段螺线作等分角抽样,抽样点 AW-K k=0.LM-1 其中: iIm[z 平面 AeW=Wne确 M为要分析的复频谱点数 0 Rell A kj(Bo+kpo)

1、算法原理 N点有限长序列，其z变换： 1 0 ( ) ( ) N n n X z x n z      k k z AW   k  0,1,...,M 1 0 0 0 j z A e   0 0 j W W e    沿z平面上的一段螺线作等分角抽样，抽样点zk： 其中： M为要分析的复频谱点数 0 0 ( ) 0 0 k j k k z A W e      则

抽样点: ilma z平面 k=Aw-/( o+ko (M-1)中 A:起始抽样点的矢量半径长度 Rell G:起始抽样点的相角 如:相邻抽样点的角度差 >0:逆时针<0:顺时针 W:螺线的伸展率 W1:螺线内缩W。<1:螺线外伸 当W=1,则表示半径为4的一段圆弧 若又有A0=1,则表示单位圆上的一段圆弧 若又有=0,0=2x/N,M=N,即为序列的DFT

抽样点： 0 0 ( ) 0 0 k j k k z A W e      A0：起始抽样点的矢量半径长度 0 ：起始抽样点的相角 0 ：相邻抽样点的角度差 0   0 0 ： 逆时针   0：顺时针 W0：螺线的伸展率 W0>1：螺线内缩 W0<1： 螺线外伸 当W0=1，则表示半径为A0的一段圆弧 若又有A0=1，则表示单位圆上的一段圆弧 若又有 0  0, 0  2 / N ，M=N ，即为序列的DFT

求抽样点处的变换 X(=k)=2x(n)="=∑x(m)4Wk=0.1,,M n=0 NM次复乘(N-1)M次复加 由mk=12|n2+k2-(k=n) 得X(=k)=∑x(n)AW2W2W2 (k+n) W2∑x(n)4W2W

求抽样点处的z变换： 1 1 0 0 ( ) ( ) ( ) N N n n nk k k n n X z x n z x n A W           k  0,1,...,M 1 2 2 2 nk 1/ 2 n  k  (k  n)  由   2 2 2 1 ( ) 2 2 2 0 ( ) ( ) N n k n k n k n X z x n A W W W      得   2 2 2 1 ( ) 2 2 2 0 ( ) k N n k n n n W x n A W W              NM次复乘 (N-1) M次复加

x(=)=W2∑x0 g(n=x(n)a W2 n=0.1.N-1 h(n)=w 则X()=W2∑g(m)(k-m)=W2[g(k)*() k=0,1,…,M-1 n g(n) h(n) X(En) n=0,1,,N-1 n=0,1,…,M-1 h(n=w h(n) 6)

2 2 ( ) ( ) n n g n x n A W  令  2 2 ( ) n h n W   n  0,1,...,N 1   2 2 1 2 2 0 ( ) ( ) ( ) ( )* ( ) k N k k n X z W g n h k n W g k h k   则     k  0,1,...,M 1   2 2 2 1 ( ) 2 2 2 0 ( ) k N n k n n k n X z W x n A W W             

Q2、Cm的实现步骤及运算量的估算 (k-) X(=)=W2x(n)4W2w k=0,1,…,M-1 其中g(n)=x(n)AwW2 n=0.1.N-1 h(n)=w 8(n):0~N-1h(n):-(N-1)~(M-1) N+M-1点 h(n)*g(n):2N+M-2 X(EKk=oM-1 L≥N+M-1且L=2m

2、CZT的实现步骤及运算量的估算 2 2 ( ) ( ) n n g n x n A W  其中  2 2 ( ) n h n W   n  0,1,...,N 1   2 2 2 1 ( ) 2 2 2 0 ( ) k N n k n n k n X z W x n A W W              k  0,1,...,M 1 g(n): 0 ~ N 1 h(n): (N 1) ~ (M 1) N  M 1点 h(n)* g(n): 2N  M 2 ( ) 0 ~ 1 X k  z k  M  1 2 m L  N  M  且L 

N-1) M-1 M-1 L-N+ L-1 A(n-m))eR(m) N-1 L-M+1 L-1 h(0-m)R(m) h(n-m))ER() L-1 H M-1

1)选择L≥N+M-1,且L=2m 2)形成L点序列g(m) (3N 8(n)=4 W2x(n)0snsN-I 0 N<n<L-1 系数 A W n2/2 Cn1=AmnW(m2=AwWn2WwW2A)=CnDn D=W WA=W WWA=WD D=WA C=1 求其L点FFT: (L/2*log2L) G()=FIg(m)=∑g(m)0≤r5L-1

2 2 ( ) 0 1 ( ) 0 1 n n g n A W x n n N N n L             1 2 0 ( ) [ ( )] ( ) L j rn L n G r FFT g n g n e        0  r  L 1 L  N  M 1 2 m 1) 选择 ，且 L  2) 形成L点序列g(n)： (3N) 求其L点FFT： ( L/2*log2L) 2 n n / 2 Cn A W  系数  2 2 ( 1) ( 1) / 2 / 2 1/ 2 1 1 ( ) n n n n n Cn A W A W W W A CnDn           1/ 2 1 1 1/ 2 1 1 n n Dn W W A W W W A WDn         1/ 2 1 0 0 D W A C 1   

3)形成L点序列n) (2N 0<n<M-1 h(n) 0 M<n<-n L-N+1<n≤L-1 求其L点FFT (L/2*logo) H(r)=FFT[M(m=∑h(n)e0≤r≤L-1

3）形成L点序列h(n): 2 2 2 ( ) 2 0 1 ( ) 0 1 1 n L n W n M h n M n L N W L N n L                     1 2 0 ( ) [ ( )] ( ) L j rn L n H r FFT h n h n e        0  r  L 1 求其L点FFT: (L/2*log2L) (2N)

4)求乘积 (L O(r)=H(r).G(r) 5)求L点FF的q(k) (L/2 logo) g(k)=IFFTIO(]=H(G(r)e L 取q(k)=q(k)R/(k 6)求得抽样点的z变换: (M) X(=k)=W2q(k)0≤k≤M-1 总运算量:m Llog, L+ 5N+L+M

4）求乘积 Q(r)  H(r)G(r) 1 2 0 1 ( ) [ ( )] ( ) ( ) L j rn L n q k IFFT Q r H r G r e L       ( ) ( ) ( ) M 取 q k  q k R k 2 2 ( ) ( ) k X k z W q k 0  k  M 1 (M) (L) 5）求L点IFFT的 q (k) (L/2*log2L) 6）求得抽样点的z变换: 总运算量: 2 3 log 5 2 mF  L L  N  L  M