第四章习题讲解 2024/10/21
第四章习题讲解 2024/10/21 1
1.如果一台通用计算机的速度为平均每次复乘54s, 每次复加0.5us,用它来计算512点的DFTx(n)],问 直接计算需要多少时间，用FFT运算需要多少时间。 (1)直接利用DFT计算： 复乘次数为N,复加次数为N(N-1)。 复乘所需时间 T=5×106×W2=5×106×5122=1.31072s 复加所需时间 T2=0.5×106×N×(N-1) =0.5×106×512×(512-1)=0.130816s 所以直接利用DFT计算所需时间： T=T+T,=1.441536s 2024/10/21 2
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 2024/10/21 2
2)利用FFT计算： 复乘次数为。log2N,复加次数为N1og,N。 2 复乘所需时间 7=5x10×Y1og,N =5x106×512 og2512=0.01152s 复加所需时间 T2=0.5×10-6×N1og2N =0.5×106×5121og2512=0.002304s 所以用FFT计算所需时间 T=T+T3=0.013824s 2024/10/21 3
复乘所需时间 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 2024/10/21 3
2.已知X(k),Y(k)是两个N点实序列x(n),y(n)的DFT 值，今需要从X(k),Y(k)求x(n),y(n)的值，为了提 高运算效率，试用一个N点FFT运算一次完成。 2024/10/21
2.已知 ， 是两个N点实序列 ， 的 值，今需要从 ， 求 ， 的值，为了提 高运算效率，试用一个N点 运算一次完成。 X k( ) Y k( ) x n( ) y n( ) DFT X k( ) Y k( ) x n( ) y n( ) IFFT 2024/10/21 4
例：设x(n)和x(n)都是N点的实数序列，试用 一次N点DFT运算来计算它们各自的DFT: DFT[x (n)=X (k) DFT[x,(n)]=X,(k) 解：利用两序列构成一个复序列 w(n)=x (n)+jx,(n) 则 W(k)=DFT[w(n)]=DFT[x (n)+jx2 (n)] DFT[x (n)]+jDFT[x,(n)] X(k)+jX2(k) Re[w(n】>W,() Jlm[w(n】>Wp() 2024/10/21
例：设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 2024/10/21 5