当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

同济大学:《数字信号处理(DSP)》课程教学资源(PPT课件讲稿)第四章 快速傅里叶变换(习题讲解)

资源类别:文库,文档格式:PPT,文档大小:415KB,文档页数:19,团购合买
点击下载完整版文档(PPT)

第四章习题讲解

第四章习题讲解

1如果一台通用计算机的速度为平均每次复乘5, 每次复加0,用它来计算512点的DF[x(m) 直接计算需要多少时间,用FFT运算需要多少时间。 解:(1)直接利用DF7计算: 复乘次数为N2,复加次数为N(N-1) 复乘所需时间 7=5×106×N2=5×10×5122=131072s 复加所需时间 72=0.5×106×N×(N-1) =0.5×106×512×(512-1)=0.130816 所以直接利用DFT计算所需时间 T=71+72=1.441536

1.如果一台通用计算机的速度为平均每次复乘 , 每次复加 ,用它来计算512点的 ,问 直接计算需要多少时间,用 运算需要多少时间。 5s 0.5s DFT x n   ( )   FFT 解:(1)直接利用 计算: 复乘次数为 ,复加次数为 。 DFT 2 N N N( −1) 复乘所需时间 6 2 6 2 1T N s 5 10 5 10 512 1.31072 − − =   =   = 复加所需时间 ( ) ( ) 6 2 6 0.5 10 1 0.5 10 512 512 1 0.130816 T N N s − − =    − =    − = 所以直接利用DFT 计算所需时间: 1 2 T T T s = + =1.441536

(2)利用FFT计算: N 复乘次数为log2N,复加次数为Nlog2No 复乘所需时间 T1=5×106×xlog2N 512 5×103×log,512=0.01152s 复加所需时间 T2=0.5×106×Nlog2N =0.5×10×512log2512=0.002304 所以用FFT计算所需时间 T=71+72=0.013824s

复乘所需时间 6 1 2 6 2 5 10 log 2 512 5 10 log 512 0.01152 2 N T N s − − =   =   = 6 2 2 6 2 0.5 10 log 0.5 10 512log 512 0.002304 T N N s − − =   =   = 复加所需时间 所以用 FFT 计算所需时间 1 2 T T T s = + = 0.013824 (2) 利用 计算: 复乘次数为 ,复加次数为 。 FFT 2 log 2 N N 2 N N log

2已知X(k),()是两个N点实序列x(m),y()的DFT 值,今需要从X(k),Y(k)求x(m),y(m)的值,为了提 高运算效率,试用一个N点FFT运算一次完成

2.已知 , 是两个N点实序列 , 的 值,今需要从 , 求 , 的值,为了提 高运算效率,试用一个N点 运算一次完成。 X k( ) Y k( ) x n( ) y n( ) DFT X k( ) Y k( ) x n( ) y n( ) IFFT

例:设x1(n)和x2(n)都是N点的实数序列,试用 次N点DFT运算来计算它们各自的DFT DFTIx, (n)]=X,(k) DFTIx,(n)=X,(k) 解:利用两序列构成一个复序列 w(n)=x,(n)+jx, (n W(k)=DFTIw(n]= DFTIX, (n)+jx,(n) DFTL,(n]+jDFT[,(n)] =X1(k)+j2(k) Rely(nI We(k) jImw(n) W(k

例:设x1 (n)和x2 (n)都是N点的实数序列,试用 一次N点DFT运算来计算它们各自的DFT: 1 1 DFT x n X k [ ( )] ( ) = 2 2 DFT x n X k [ ( )] ( ) = 解:利用两序列构成一个复序列 1 2 w n x n jx n ( ) ( ) ( ) = + 1 2 W k DFT w n DFT x n jx n ( ) [ ( )] [ ( ) ( )] = = + 则 1 2 = + DFT x n jDFT x n [ ( )] [ ( )] 1 2 = + X k jX k ( ) ( ) Re[ ( )] ( ) w n W k ep Im[ ( )] ( ) op j w n W k

由x(n)=Re[v(m)得 X(k)=DFTIX, (n)= DFTRelw(n)=Wen(k) WW((K))N+W((N-KDNIrn(k) 由x2(m)=Imw(n)得 X(k)=DFTIx, (n]= DFT(Imw(n==Won(k) 2 W(K)N-W((N-k)R(k)

1 由 得 x n w n ( ) Re[ ( )] = 1 1 ( ) [ ( )] {Re[ ( )]} ( ) X k DFT x n DFT w n W k = = = ep 1 * [ (( )) (( )) ] ( ) 2 = + − W k W N k R k N N N 2 由 得 x n w n ( ) Im[ ( )] = 2 2 1 ( ) [ ( )] {Im[ ( )]} ( ) X k DFT x n DFT w n W k op j = = = 1 * [ (( )) (( )) ] ( ) 2 W k W N k R k N N N j = − −

、解:由题意X(k)=DFT[x(m)],Y()=DFTy(n) 构造序列z(k)=X(k)+jY(k) 对z(k)作一次N点F可得序列(n) E(n)=IDFT Z(k)I 又根据DF/的线性性质 =(n)=IDFT Z(k )=IDFTLX(k)+jY(k IDFTLX()+jIDFTLY(K) x(n)+jy(n 而x(n),y(m)都是实序列x(n)=Re[(n)] y(m)=m[=(n)

解:由题意 X k DFT x n Y k DFT y n ( ) = =     ( ) ( ) ( )     , 构造序列 Z k X k jY k ( ) = + ( ) ( ) 对 Z k( ) 作一次N点IFFT可得序列 z n( ) 又根据DFT的线性性质 = + IDFT X k jIDFT Y k     ( ) ( )     而 x n( ) , y n( ) 都是实序列 ( ) ( ) ( ) ( ) Re Im x n z n y n z n  =     =     z n IDFT Z k ( ) =   ( )   z n IDFT Z k IDFT X k jY k ( ) = = +     ( ) ( ) ( )     = + x n jy n ( ) ( )

3.N=16时,画出基-2按时间抽取法及按频率抽取法 的FF流图(时间抽取采用输入倒位序,输出自然数 顺序,频率抽取采用输入自然顺序,输出倒位序) 解 自然序倒位序 自然序倒位序 0000000000 8100000011 1000110008 9100110019 2001001004 10101001015 30011110012 111011110113 4010000102 12110000113 50101101010 31101101111 6011001106 14111001117 70111111014 151111111115

3. N=16 时,画出基 -2 按时间抽取法及按频率抽取法 的 FFT 流图(时间抽取采用输入倒位序,输出自然数 顺序,频率抽取采用输入自然顺序,输出倒位序)。 解: 自然序 倒位序 0 0000 0000 0 1 0001 1000 8 2 0010 0100 4 3 0011 1100 12 4 0100 0010 2 5 0101 1010 10 6 0110 0110 6 7 0111 1110 14 自然序 倒位序 8 1000 0001 1 9 1001 1001 9 10 1010 0101 5 11 1011 1101 13 12 1100 0011 3 13 1101 1011 11 14 1110 0111 7 15 1111 1111 15

(1)按时间抽取的基2FFT流图 N=16=2.L=4 共有L=4级蝶形运算,每级N2=8个蝶形运算 Xm(k) Xm(k) Xm=1() Xm( 每个蝶形的两节点距离为2m,即从第一级到 第四级两节点距离分别为1,2,4,8。 系数W的确定:r=(k) 即k的二进制左移L-m位补零

(1) 按时间抽取的基-2FFT流图 16 2 , 4 L N L = = = 共有L = 4级蝶形运算,每级N / 2 = 8个蝶形运算 每个蝶形的两节点距离为 ,即从第一级到 第四级两节点距离分别为1,2,4,8。 1 2 m− - 2 ( ) 2 r L m W r k N k L m =  − 系数 的确定: 即 的二进制左移 位补零 r WN 1 ( ) X k m− 1 ( ) X j m− ( ) X k m ( ) X j m -1

4))+JXX x(8) X(1) X(2) X(3) x(2) X(4) 116 X(5) X(6 (14) X(7) (1) X(8) (9) X(9) (5) X(10) HI (13) X(11 (3) WI X(12) WI X(13) X// X(14) t(15) 图P4-3

点击下载完整版文档(PPT)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共19页,试读已结束,阅读完整版请下载
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有