信号分析与处理课后习题答案.pdf

信号分析与处理课后习题答案

第五章快速傅里叶变换

1.如果一台通用算机的速度为平均每次复乘需要50us,每次复加需要10us,

用来就散N=1024点的DFT,问：

(1)直接算需要多少时间？用FFT算呢？

(2)照这样算，用FFT算快速卷积对信号正行处理是，估可实现实时处

理的信号最高频率？

解：

分析：直接利用DFT算：复乘次数为N2,复加次数为N(NT)；

利用FFT算：复乘次数为OSNbgzN,复加次数为NlogzN；

(1)直接DFT算：

2

复乘所需时间7；=x50W5=1024x50us=52.42885

复加所需时间石=N(N-1)x1Ous=1024(1024-1)x1Ous=10.47552s

所以总时间T=T+T=62.904325

DFT}2

FFT算:

复乘所需时间7；=0.5NlogNx50us=0.5xl024xlog1024x50us=0.256s

22

复加所需时间logNx1=1024xlog1024x1Ous=0.1024s

22

所以总时间为=A+1=0.3584s

T

(2)假设算两个N长序列王(〃)和马(〃)的卷积

算过程为如下：

第一步：求X仆)，X(k)；所需时间为2x%『

2

第二步：算X(Q=X四)，共需要N次复乘运算

所需时间为7b=Nx50us=1024x50〃s=0.051Is

第三步：算/T(X(幻)，所需时间为乙口

所以总时间为『二2、74+70=3x0.3584s+0.0512s=1.1264s

容许算信号频率为N/T=911.3Hz

2.设x(n)是长度为2N的有限长实序列，X/)为x(n)的2N点得DFT。

(1)试设用一次N点FFT完成算X(Zr)的高效算法；

(2)若已知X(Q,试设用一次N点IFFT实现x(n)的2N点IDFT运算。

解：本题的解题思路就是DIT-FFT思想。

(1)分析2N点的FFT,如下

在始于分别抽取偶数点和奇数点x(n)得到两个N长的实序列xl(n)和

x2(n)；

XI(n)=x：2n),n=0,1,…，N-l

X2(n)=x⑵i+l),n=0,1,-,N-l

根据DIT-FFT的思想,只要球的xl(n)和x2(n)的N电DFT,再经过

简单的一级蝶形运算就可得到x(n)的2N点的DFT。因为xl(n)和x2(n)

均为实序列，所以根据DFT的共舸对称性，可以用一次N点FFT求得Xl(k)

和X2(k)。具体方法如下：

令y(n)=xl(n)+jx2(n)

Y(k)=D