数字信号处理学习拓展
题2-43图 FFT蝶形运算流图
2－44 设序列x(n)的长度为200，对其用时域基2FFT来计算DFT，请写出第三级蝶形
中不同的旋转因子。
8M解: 由于序列x(n)的长度为200，所以取N?256?2?2,得M?8。
又因为L?3，P?J?2M?L?J?28?3?32J,J?0,1,…,2L-1-1=0，1，2，3
0326496第3级蝶形运算中不同的旋转因子为：W256 ， W256 ，W256 ，W256
2－45 如果通用计算机的速度为平均每次复数乘需要5?s，每次复数加需要1?s，用来计算
N?1024点DFT，问直接计算需要多少时间。用FFT计算呢？照这样计算，用FFT
进行快速卷积对信号进行处理时，估算可实现实时处理的信号最高频率。 解： 当N?1024?2时，直接计算DFT的复数乘法运算次数为N?1024次
直接计算1024点DFT需要时间TD为
1022TD?5?10?6?10242?1047552?10?6?6.290432s
用FFT计算1024点DFT所需计算时间为
TF?5?10?6?Nlog2N?Nlog2N?10?6 21024?5?10?6??10?1024?10?10?6
2 ?35.84ms
快速卷积时，要计算一次N点FFT（考虑到H(k)?DFT?h(n)?已计算好存入内存），一次N点IFFT和N次频域复数乘法。所以，计算1024点快速卷积的计算时间约为
2－26
数字信号处理学习拓展
Tc?2TF?1024
?71680?s?5?1024?s
?s ?76800所以，每秒钟处理的采样点数（即采样速率）fs?由采样定理知，可实时处理的信号最高频率为 fmax?1024?13333.3次/秒。
76800?10?6fs13333.3??6666.7Hz 22应当说明，实际实现时，fmax 还要小一些。这是由于实际采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分要计算两次。重叠部分长度与h(n)长度有关，而且还有存取数据指令周期等。
2－46 序列x(n)长240点，h(n)长10点。当采用直接计算法和快速卷积法（用基2FFT）
求它们的线性卷积y(n)?x(n)?h(n)时，各需要多少次乘法？ 解： （1）已知N1?240,N2?10,直接线性卷积复乘的次数为
N1?N2?240?10?2400（次）
（2）因为N1?N2?1?240?10?1?249,取N?256。快速卷积中复乘的次数： 1）x(n)????X(k),h(n)????H(k)，需2? 2）Y(k)?X(k)H(k)，需N次复乘； 3）y(n)?IFFT?Y(k)?，需 总的复乘的次数为：
FFTFFTNlog2N次复乘； 2Nlog2N次复乘； 23?Nlog2N?N?3?128?8?256?3328(次) 22－47 设有限长序列x(n)的DFT为X(k)，我们可使用FFT来完成该运算.现假设已知
X(k)，k?0,1,?,N?1,如何利用FFT求原序列x(n)?IDFT[X(k)]。
解：
1x(n)?N?X(k)Wk?0N?1?kn，n?0,1,?,N?1
2－27
数字信号处理学习拓展
1N?1*?x(n)?[?X(k)Wkn]，n?0,1,?,N?1
Nk?0 因此，利用FFT求x(n)的步骤为： (1) (2) (3)
对X(k)求共轭 对X(k)*进行FFT变换 对变换后的序列取共轭，并乘以
*1即得到x(n)。 N2－48 已知X(k)和Y(k)是两个N点实序列x(n)和y(n)的DFT，若要从X(k)和Y(k)
求x(n)和y(n)，为提高运算效率，试设计用一次N点IFFT来完成。 解：
x(n),y(n)为实序列。
?X(k),Y(k)为共轭对称序列，jY(k)为共轭反对称序列。
将X(k)，jY(k)作为序列F(k)的共轭对称分量和共轭反对称分量
F(k)?X(k)?jY(k)?Fep(k)?Fop(k)
计算一次N点IFFT得到
f(n)?IFFT?F(k)??Re?f(n)??jIm?f(n)?
由DFT的共轭对称性
11x(n)?Re[f(n)]?[f(n)?f*(n)]，y(n)?Im[f(n)]?[f(n)?f*(n)]
22j2－49 设x(n)是长度为2N的有限长实序列，X(k)为x(n)的2N点DFT。
（1） 试设计用一次N点DFT完成计算X(k)的高效算法。
（2） 若已知X(k)，试设计用一次N点IDFT实现求x(n)的2N点IDFT运算。 解： 本题的解题思路就是DIF-FFT思想
（1） 在时域分别抽取偶数点和奇数点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
2－28
数字信号处理学习拓展
根据DIT-FFT思想，只要求得x1(n)和x2(n)的N点DFT，再经过简单的一级碟形运算就可以得到x(n)的2N点DFT。又
x1(n),x2(n)为实，所以根据DFT的共轭对
称性，可用一次N点DFT求得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)?1??Y(k)?Y(N?k)? ??21?jX2(k)?DFT?jx2(n)??Yop(k)??Y(k)?Y(N?k)?? 2?2N点DFT[x(n)]?X(k)可由X1(k)、X2(k)得到
k??X(k)?X1(k)?W2NX2(k) k?0,1,?k??X(k?N)?X1(k)?W2NX2(k),N?1
这样通过一次N点DFT计算完成2N点DFT
?x1(n)?x(2n),?x(n)?x(2n?1),?2（2） 设?
X(k)?DFTx(n),?1??1?X(k)?DFT?x(n)?,2?2
k?0,1,,N?1, n?0,1,,N?1
k??X(k)?X1(k)?W2NX2(k),则? k??X(k?N)?X1(k)?W2NX2(k)
k?0,,N?1
?X1(k)?X2(k)?1?X(k)?X(k?N)? 21?X(k)?X(k?N)?W2?Nk 2?过程如下
①由X(k)计算出X1(k)，X2(k)
②由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点IDFT得到
2－29
数字信号处理学习拓展
y(n)?IDFT?Y(k)??Re?y(n)??jIm?y(n)? 由DFT的共轭对称性
n?0,1,,N?1
1??y(n)?y(n)??IDFT?Yep(k)??x1(n) ????21y(n)?y?(n)? jIm?y(n)????Yop(k)???jx2(n) ???IDFT?2 Re?y(n)??③由x1(n)和x2(n)定义得x(n)。
2－50 一个3000点的序列输入一个线性时不变系统，该系统的单位脉冲响应长度为60。为
了利用快速傅里叶变换算法的计算效率，该系统用128点的离散傅里叶变换和离散傅里叶反变换实现。如果采用重叠相加法，为了完成滤波器运算，需要多少DFT？ 解： 采用重叠相加法，将x(n)分成若干个长度为M的不重叠的序列xi(n)。若h(n)的长
度为L，则xi(n)?h(n)的长度为L?M?1，所以DFT变换的长度N?L?M?1。由题设，N?128，L?60，x(n)必须分成长度为M的序列：
M?N?L?1?69
x(n)的长度为3600点，所以共有44个序列（其中最后一个序列仅有33个非零值）。
为了计算卷积共需要： 1． 2． 3．
一个DFT用于计算H(k)。 44个DFT用于?i(k)的计算。
44个用于?i(k)??i(k)H(k) IDFT变换的计算。
一共需要45个DFT变换和44个IDFT变换。 2-51 已知信号x(t)=e-t10[cos(10t)+cos(12t)]u(t)，用DFT分析信号的频谱。
解：利用MATLAB分析信号的频谱画出频谱图如题2-51图所示：
N1=128;N2=512;
ws=100;w1=10;w2=12; fs=ws/(2*pi);
n1=0:N1-1;n2=0:N2-1;
xn1=exp(-n1/10).*(cos(w1/ws*n1)+cos(w2/ws*n1));8点有效x(n)数据 %在128点有效数据不补零情况下的分辨率演示 xk11=fft(xn1,N1);
mxk11=abs(xk11(1:N1/2)); figure(1);
2－30