第四章习题讲解
第四章习题讲解
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点的 ，问 直接计算需要多少时间，用 运算需要多少时间。 5s 0.5s 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