快速傅里叶变换试题

1、填空题(1) 如果序列x(n)是一长度为64点的有限长序列(0 n 63)，序列h(n)是一长度为128点的有限长序列(0 n 127)，记y(n) x(n) h(n)(线性卷积)，则y(n)为点的序列，如果采用基2FFT算法以快速卷积的方式实现线性卷积，则FFT的点数至少为 _点。解：64+128-1 = 191 点;256(2) 如果一台通用机算计的速度为：平均每次复乘需100 S，每次复加需20 s，今用来计算N=1024点的DFTx( n)。问直接运算需(解：直接运算：需复数乘法)时间，用FFT运算需要()时间。N 2次，复数加法N ( N1)次。直接运算所用计算时间T1为T1N2 1

2、00N (N1) 20125808640 s 125.80864s基2FFT运算:需复数乘法N log 2 N次，复数加法2N log 2 N 次。用FFT计算1024点DTF所需计算时间T2为NT2log 2 N 100 N log2 N 20 716800 s 0.7168s。2jl(3) 快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子e N的_来减少计算量，其特点是 、和。解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置(4) N点的FFT的运算量为复乘、复加。NN解：mF L log 2 N ； aF NL N log 2 N22选择题1. 在基2DITFFT运算中通过不断

3、地将长序列的DFT分解成短序列的 DFT最后达到2点DFT来降低运算量。若有一个64点的序列进行基2DITFFT运算，需要分解 次，方能完成运算。D. 8解：B2在基2 DIT FFT运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16,倒序前信号点序号为8，则倒序后该信号点的序号为 。A. 8 B. 16 C. 1 D. 4解：C3. 在时域抽取FFT运算中，要对输入信号x(n)的排列顺序进行“扰乱”。 在16点FFT中，原来x(9)的位置扰乱后信号为： 。A. x（7） B. x（9） C. x（1） D. x（15）解：B4. 用按时间抽取FFT计算N点DFT所需的复数乘法次数与

4、（） 成正比解:D5.直接计算N点DFT所需的复数乘法次数与（）成正比。解:B点FFT所需的复数乘法次数为（）。D.（N/2）log 2N 解：D7.下列关于FFT的说法中错误的是（）。是一种新的变换是DFT的快速算法基本上可以分成时间抽取法和频率抽取法两类D.基2 FFT要求序列的点数为2L（其中L为整数）解：A8.不考虑某些旋转因子的特殊性,一般一个基2 FFT算法的蝶形运算所需的复数乘法及复数加法次数分别为（）解：A9 .计算N=Z（ L为整数）点的按时间抽取基-2FFT需要（）级蝶形运算。A. L解：A10. 基-2 FFT算法的基本运算单元为（）A.蝶形运算B.卷积运算C.相关运算D

5、.延时运算解：A11. 计算256点的按时间抽取基-2 FFT，在每一级有 个蝶形。（）解：C12. 如图所示的运算流图符号是2FFT算法的蝶形运算流图符号。（）A.按频率抽取B.按时间抽取、B项都是、B项都不是解：B13. 求序列x（n）的1024点基2 FFT,需要次复数乘法。（）X 1024X 10X 10解：C问答题1.简述频域抽选法和时域抽选法的异同。N答：相同点：（1）进行原位运算（2）运算量相同，均为log 2 N次复乘、N |og2 N次2复加；不同点：（1）时域抽选法输入为倒位序，输岀为自然顺序。频域抽选法正好与此相反，但时域抽选法也有输入为自然顺序、输岀为倒位序的情况（2）

6、蝶形运算不同2. 回答以下问题:(1)画出按时域抽取 N 4点基2FFT的信号流图。(2)利用流图计算4点序列x（n）(2,1,3,4) ( n 0,1,2,3)DFT。(3)试写出利用FFT计算IFFT的步骤。解：（1）x(0) x(2) x(1) x(3)Q°(0)Q0(1)Q1(1N01014X(0)0w2°w2°w20 w20W40 W40X(0丿4 V11A/1f X (1丿W4 W4202f X(2)W4 W44X(3)3W4W加权系数点按时间抽取FFT流图Q°(0)Q°x(0) x(2)x(0) x(2)Q1(0) x x(3)Q

7、Q x(1) x(3)X(0) Q°(0) Q,0)510X(1)Q°(1) W41Q1 (1)X(2)Qc(0)W42Q1(0)5 50X(3) Q0(1) W43Q1 (1) 1 3j即：X(k) (10, 1 3j,0, 1 3j),k 0,1,2,3(3)具体步骤如下：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) X(k)

8、,y(n) Y(k)取序列Z(k) X(k) jY(k)对 Z(k) 作N点IFFT可得序列 z(n)。又根据DFT性质IDFT X(k) jY(k) IDFTX(k) jIDFT Y(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)计算题1.对于长度为8点的实序列x(n)，试问如何利用长度为4点的FFT计算x(n)的8点DFT？写出其表达式， 并画出简略流程图。7解： X(k)x ( n )W8nkn033x(2r)W82rkx(2r 1)W8(2r 1)kr 0 r 033g (

9、r )W4rk W8k h(r)W4rkr 0 r 0kG(k) W8kH (k),k 0,1,2,333X(k 1)g(r)W4r(k 4) W8k 4 h(r)W4r(k 4)r 0 r 033 g(r)W4rk W8kh(r )W4rkr0 r 0 G(k) W8kH(k),k 0,1,2按照式和式可画出如下图所示的流程图。22. XkX(0)X(1) XX(3)X(4)X(5)X(6)X1 xdn 2(x2 n x2n 1)1NX2n-(x2 n x2n 1),0 n - 1Xik和X2k分别表示序列xn和X2n的号点DFT试由X1k和X2k确定xn N解：dft x2kN 12mkx

10、2kWN2N 1mlx IWN2(I 为偶数)2INdft x2kN 1xlL 01 Wn2N21x2kk 0WNmI£(XmXm 号)m (l 1)mk1Wn2N 1xl Wn 22（l为奇数）点 DFT。N 1INX1m4(11WNm)Xm(14Wnm)Xm号,0 mN 12X2【m91WNm)Xm-(14Wnm)Xm号,0 m貝12解上述方程可得Xm(1 W：)X1m(1WNm)X2m,0 m山12(1Wn2)1-(XmN mX mWnx|2l 02ml mVn VnXm ；(1 MXIm d 心阿0 m3.已知长度为2N的实序列x(n)的DFTX(k)的各个数值(k0,1,.

11、,2N1),现在需要由X(k)计算x(n)，为了提高效率，请设计用一次N点IFFT来完成。解：如果将x(n)按奇偶分为两组，即令u( n)x(2n)v(n) x(2n 1)0,1,2, ,N那么就有X(k) U(k) W4kNV(k)X(k N) U(k) W2Nv(k)0,1,2,N 1其中U(k)、V(k)分别是实序列u(n)、v(n)的n点dft, U (k)、1U(k) X(k) X(k N)V(k) 1w2, X(k) X(k N)V(k)可以由上式解出k 0,1,2,N 1由于X(k)(k 0,1,.,2N1)是已知的，因此可以将 X(k)前后分半按上式那样组合起来，于是就得到了

12、U(k)和V(k)。令y(n) u(n) jv(n)根据U(k)、V(k)，做一次N点IFFT运算，就可以同时得到u(n)和 v(n) (n 0,1,., N 1)它们分别是x(n)的偶数点和奇数点序列，于是序列x(n) (n4-7采用FFT算法，可用快速卷积完成线性卷积。现预计算线性卷积0,1,.,2Nx(n)1)也就求出了。h(n)，试写采用快速卷积的计算步骤(注意说明点数)答：如果x(n)，h(n)的长度分别为N2,那么用长度N卷积。用fft运算来求x(n) h(n)值(快速卷积)的步骤如下:N1N21的圆周卷积可计算线性(1)对序列x(n)，h(n)补零至长为N,使nN1 N21，并且N 2m (M为整数)，即x(n)x(n)0n 0,1,.N1N1,N11,.N 1(3)h(n)h(n)0n0,1,., N21N2,N221,.,N1用FFT计算x(n)，h(n)的离散傅立叶变换x(n)FFTX(k)h( n)FFTH(k)计算 Y(k) X(k)H(k)(N点)(N点)(4)用IFFT计算Y(k)的离散傅立叶变换得:x(n) h(n)IFFT Y(k)(n 点)4-8试推导时域抽取基-2 FFT算法,并画出8点的FFT计算流图。解:n WN；kN 2 1N 2