《快速傅里叶变换FFT试题》由会员分享，可在线阅读，更多相关《快速傅里叶变换FFT试题（9页珍藏版）》请在金锄头文库上搜索。
1、第一章快速傅里叶变换(FFT)4.1 填空题(1)如果序列x(n)是一长度为64点的有限长序列( n 63),序列h(n)是一长度为128点的 有限长序列( n 127)，记y(n)二x(n) *h(n)(线性卷积)，则y(n)为点的序列，如果采 用基2FFT算法以快速卷积的方式实现线性卷积，则FFT的点数至少为点。解：64+128-1 = 191 点；256(2)如果一台通用机算计的速度为：平均每次复乘需10 M ,每次复加需2 M ,今用来计算N=124 点的DFTx(n)。问直接运算需()时间，用FFT运算需要()时间。解：直接运算：需复数乘法N2次，复数加法N (N - 1)次。直接运
2、算所用计算时间T1为T = N2 x 10 + N (N 1) x 2 = 12580864卩 s = 125.80864s1N基2FFT运算：需复数乘法ylog2 N次，复数加法Nlog2 N次。用FFT计算1024点DTF所需计算时间T2为NT = log N x 10 + N log N x 2 = 716805 s = 0.7168s2 2 2 2 。”.j k(3)快速傅里叶变换是基于对离散傅里叶变换和利用旋转因子eN的来减少计算量，其特点是 、和。解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置、复加.(4) N点的FFT的运算量为复乘.NN解: mF =一 L = log
3、N ； aF = NL = Nlog N2 2? 24.2 选择题1 在基2DITFFT运算中通过不断地将长序列的DFT分解成短序列的DFT，最后达到2点DFT来 降低运算量。若有一个64点的序列进行基2DITFFT运算，需要分解次，方能完成运算。A.32B.6C.16D. 8解： B2在基2 DITFFT运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16，倒序前信号 点序号为8,则倒序后该信号点的序号为。A. 8B. 16C. 1D. 4解： C3在时域抽取FFT运算中，要对输入信号x(n)的排列顺序进行“扰乱”。在16点FFT中，原来x(9)的位置扰乱后信号为：。A x（7）B.
4、 x（9） C. x（1） D. x（15）解： B4用按时间抽取FFT计算N点DFT所需的复数乘法次数与（）成正比。A.NB.N2C.N3D.Nlog2N解： D5直接计算N点DFT所需的复数乘法次数与（）成正比。A.NB.N2C.N3D.Nlog2N解： B6.N点FFT所需的复数乘法次数为（）。A.NB.N2C.N3D.(N/2)log2N解： D7下列关于FFT的说法中错误的是（）。A. FFT是一种新的变换B. FFT是DFT的快速算法C. FFT基本上可以分成时间抽取法和频率抽取法两类D. 基2 FFT要求序列的点数为2L（其中L为整数）解： A8不考虑某些旋转因子的特殊性，一般一
5、个基2 FFT算法的蝶形运算所需的复数乘法 及复数加法次数分别为（）。A.1 和 2B.1 和 1C.2 和 1D.2 和 2解： A9计算N=2l （L为整数）点的按时间抽取基-2FFT需要（）级蝶形运算。A. LB.L/2C.ND.N/2解： A10.基-2 FFT算法的基本运算单元为（）A.蝶形运算B.卷积运算C.相关运算D.延时运算解： A11.计算256点的按时间抽取基-2 FFT,在每一级有个蝶形。（）A.256B.1024解：C12.如图所示的运算流图符号是基2FFT 算法的蝶形运算流图符号。()A. 按频率抽取B. 按时间抽取C. A、B 项都是D. A、B 项都不是 解： B
6、13.求序列x(n)的1024点基2FFT，需要次复数乘法。()A.1024B.1024X1024C.512X10D.1024X10解： C4.3 问答题1. 简述频域抽选法和时域抽选法的异同。N答：相同点：(1)进行原位运算(2)运算量相同，均为ylg2 N次复乘、N log2 N次复加；不同点：(1)时域抽选法输入为倒位序，输出为自然顺序。频域抽选法正好与此相反，但时域抽选 法也有输入为自然顺序、输出为倒位序的情况(2)蝶形运算不同2. 回答以下问题：(1) 画出按时域抽取N = 4点基2FFT的信号流图。(2) 利用流图计算 4 点序列 x(n)二(2,1,3,4)( n 二 ,1,2,
7、3)的 DFT。(3) 试写出利用FFT计算IFFT的步骤。解：(1)4点按时间抽取FFT流图冲0 1X)0 10 W 0 W 00W 0 W 02 2441 W0 W11wj0 w 12 2442W 0 W 2443W 0 W 344加权系数Q (0) = x(0) + x(2) = 2 + 3 = 50Q =x(0) - x(2) = 2 -1 = -10Q (0) = x(1) + x(3) = 1 + 4 = 51Q (1) = x(1) - x(3) = 1 - 4 = -31X (0)二 Q (0) + Q (0)二 5 + 5 二 1001X (1)二 Q 0(1)+ W41 Q
8、1(1) 一1 + j - 3X (2)二 Q (0) + W 2 Q (0)二 5 - 5 二 0041X二 Q0(1)+ W43Q1(1)i3jX (k) = (10,-1 + 3 j,0,-1 - 3 j), k = 0,l,2,33)具体步骤如下：1)对X(k)取共轭，得X *(k)；2)对 X * (k)做 N 点 FFT； 3)对 2)中结果取共轭并除以 N。3.已知两个N点实序列x(n)和y(n)得DFT分别为X (k)和Y(k)，现在需要求出序列x(n)和y(n)，试用一次N点IFFT运算来实现。解：依据题意x(n) o X(k),y(n) O Y(k)取序列对 Z (k)Z
9、(k) = X (k) + jY (k)作N点IFFT可得序列z(n)又根据 DFT 性质IDFT X (k) + jY (k)二 IDFTX (k) + jIDFTY (k)二 x(n) + jy (n) 由原题可知，x(n), y(n)都是实序列。再根据z(n) = x(n) + jy(n)，可得 x(n) = Re z (n)y (n) = Im z (n)4.4 计算题1.对于长度为8点的实序列x(n)，试问如何利用长度为4点的FFT计算x(n)的8点DFT?写出其表达式,并画出简略流程图。解：X (k)=工 x(n)W nkn=0=工 x(2r )W 2 rk + 工 x(2r +
10、1)W (2 r+1)k 88 r=0r=0=Y g (r)W rk + Wk 工 h(r)W rk484r=0r=0=G(k)+WkH(k),k = 0,1,2,38X(k+1)=Y3 g(r)W r(k+4) + W k+4 Y3 h(r)W r(k+4)484r =0r =0= Yg(r)W rk -W kYh(r)W rk484r=0r =0=G(k)-WkH(k),k = 0,1,28按照式和式可画出如下图所示的流程图。X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N2. X k是N点序列x(n)的DFT, N为偶数。两个2点序列定义为x n =(x2n + x2n
11、 +1)121Nx n = (x2n - x2n +1),0 n 一 一 12 2 2NX1 k和X k分别表示序列x1 n和x n的点DFT,试由Xk和X k确定xn N JL乙JL乙/JL乙点 DFT。解：DFT x2k= Sx2kWmk =SxlW 2(l 为偶数)NNk=02l=02INN -11 + W 21N=S xlN-Wml = (Xm + Xm + )2 N 22L=0DFT &2k +1=为xk + 1W k = SxlW； ( i 为奇数)k=02l=0inN-1仃一W 2 )1N=S xlN WmlW-m = (X m - X m + W-m2 N N 22 Nl=01
12、1NNX m =(1 + W -m) X m +(1 W -m) X m + ,0 m 11 4 N 4 N 2 2X m = 1 (1 - W-m)Xm +1 (1 + W-m)Xm + N,0 m N -124 N4 N22解上述方程可得Xm二(1 + Wm)X m + (1 - Wm)X m,0 m N -1N 1N 22Xm 十一=(1 Wm)X m + (1 + Wm)X m,0 m 12 N 1 N 2 23.已知长度为2N的实序列x(n)的DFT X (k)的各个数值(k = 0,1,.,2N - 1)，现在需要由X (k)计算x(n)，为了提高效率，请设计用一次N点IFFT来完
13、成。解：如果将x(n)按奇偶分为两组，即令n = 0,1,2, N 1u (n)二 x(2n)v(n)二 x(2n +1)那么就有k =0,1,2,.,N1X(k) = U(k) + Wk V(k)2NX(k + N) = U(k) Wk V(k)2N其中U(k)、V(k)分别是实序列u(n)、v(n)的N点DFT，U(k)、V(k)可以由上式解出U (k) =1 x (k) + X (k + N)1 2k = 0,1,2,N 1V (k) = - W -kX (k) X (k + N )JI2 2 NJ由于X(k)(k = 0，1，.，2N -1)是已知的，因此可以将X(k)前后分半按上式那样组合起来，于是就得到了 U (k)和V (k)。令y (n) = u (n) + jv(n)根据U(k)、V(k)，做一次N点IFFT运算，就可以同时得到u(n)和v(n) (n =N 1)它们分别是x(n)的偶数点和奇数点序列，于是序列x(n) (n = 0,1,-,2 N 1)也就求出了。4-7采用FFT算法，可用快速卷积完成线性卷积。现预计算线性卷积x(n) * h(n)，试写采用快速卷积的计算步骤(注意说明点数)。答:如果x(n)，h(n)的长度分别为N1,N2,那么用长度N N1 + N2 +1的圆周卷积可计算线性卷 积。
