第四章习题讲解
第四章习题讲解
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