信号分析与处理课后习题答案
第五章快速傅里叶变换
1.如果一台通用计算机的速度为平均每次复乘需要50us，每次复加需要10us，用来就散N=1024点的DFT，问：
（1）直接计算需要多少时间？用FFT计算呢？
（2）照这样计算，用FFT计算快速卷积对信号进行处理是，估计可实现实时处理的信号最高频率？ 解：
分析：直接利用DFT计算：复乘次数为N2，复加次数为N(N-1)；
利用FFT计算：复乘次数为0.5Nlog2N，复加次数为Nlog2N；
（1） 直接DFT计算：
复乘所需时间T1?N2?50us?10242?50us?52.4288s
复加所需时间T2?N(N?1)?10us?1024(1024?1)?10us?10.47552s 所以总时间TDFT?T1?T2?62.90432s
FFT计算：
复乘所需时间T3?0.5Nlog2N?50us?0.5?1024?log21024?50us?0.256s 复加所需时间T4?Nlog2N?10us?1024?log21024?10us?0.1024s 所以总时间为TFFT?T3?T4?0.3584s （2） 假设计算两个N长序列x1(n)和x2(n)的卷积
计算过程为如下：
第一步：求X1(k)，X2(k)；所需时间为2?TFFT
第二步：计算X(k)?X1(k)?X2(k)，共需要N次复乘运算
所需时间为To?N?50us?1024?50us?0.0512s
第三步：计算IFFT(X(k))，所需时间为TFFT
所以总时间为T?2?TFFT?To?3?0.3584s?0.0512s?1.1264s 容许计算信号频率为N/T=911.3Hz
2.设x(n)是长度为2N的有限长实序列，X(k)为x(n)的2N点得DFT。
1
（1）试设计用一次N点FFT完成计算X(k)的高效算法；
（2）若已知X(k)，试设计用一次N点IFFT实现x(n)的2N点IDFT运算。
解：本题的解题思路就是DIT-FFT思想。 （1） 分析2N点的FFT，如下
在始于分别抽取偶数点和奇数点x(n)得到两个N长的实序列x1(n)和x2(n);
X1(n) = x(2n), n = 0,1,…, N-1 X2(n) = x(2n+1), n = 0,1,…, N-1
根据DIT-FFT的思想，只要球的x1(n)和x2(n)的N电DFT，再经过简单的一级蝶形运算就可得到x(n)的2N点的DFT。因为x1(n)和x2(n)均为实序列，所以根据DFT的共轭对称性，可以用一次N点FFT求得X1(k)和X2(k)。具体方法如下：
令 y(n) = x1(n) + jx2(n)
Y(k) = DFT[y(n)], k = 0,1,…, N-1
则 X1(k) = DFT[x1(n)] = Yep(k) = 0.5[Y(k)+Y*(N-k)] X2(k) = DFT[jx2(n)] = Yop(k) = 0.5[Y(k)-Y*(N-k)] 2N点得DFT[x(n)] = X(k)可由X1(k)和X2(k)得到
k??X(k)?X1(k)?W2NX2(k),k?0,1,?,N?1 ?k??X(k)?X1(k)?W2NX2(k),k?N,N?1,?,2N?1这样，通过一次N点FFT计算就完成了计算2N点DFT。当然由Y(k)
求x1(k)和X2(k)需要相对小的额外计算量。 （2） 分析2N点的IFFT变换，如下
与(1)相同，设X1(n),x2(n),X1(k),X2(k); n,k = 0,1,…, N-1 则应满足关系式
k??X(k)?X1(k)?W2NX2(k),k?0,1,?,N?1 ?k??X(k?N)?X1(k)?W2NX2(k)由上式可解出
X1(k)?0.5[X(k)?X(k?N)]X2(k)?0.5[X(k)?X(k?N)]W?k2N
由以上分析可得出计算过程如下:
1由X(k)计算出X1(k)和X2(k),即 ○
X1(k)?0.5[X(k)?X(k?N)]X2(k)?0.5[X(k)?X(k?N)]W?k2N
2由X1(k)和X2(k)构成N点频域序列Y(k) ○
Y(k) = X1(k) +jX2(k) = Yep(k) + Yop(k)
其中Yep(k) = X1(k)，Yop(k) = jX2(k),进行N点IFFT得到
y(n)?IFFT[Y(k)]?Re[y(n)]?jIm[y(n)],n?0,1,?,N?1
2
由DFT的共轭对称性知
Re[y(n)]?0.5[y(n)?y*(n)]?IDFT[Yep(k)]?x1(n)Im[y(n)]?0.5[y(n)?y*(n)]?IDFT[Yop(k)]?jx2(n)3由x1(n)和x2(n)合成x(n) ○
?nx1(),n?偶??2x(n)??
n?1?x2(),n?奇??2
3.请给出16点时域抽选输入倒序、输出顺序基2-FFT完整计算流图，注意WNP及其p值得确定。
解：
3