快速傅里叶变换(FFT)试题

第一章快速傅里叶变换（FFT）4.1填空题（1）如果序列)(nx是一长度为64点的有限长序列)630(n，序列)(nh是一长度为128点的有限长序列)1270(n，记)()()(nhnxny（线性卷积），则)(ny为点的序列，如果采用基FFT2算法以快速卷积的方式实现线性卷积，则FFT的点数至少为点。解：64+128-1＝191点;256(2)如果一台通用机算计的速度为：平均每次复乘需100s，每次复加需20s，今用来计算N=1024点的DFT)]([nx。问直接运算需（）时间，用FFT运算需要（）时间。解：①直接运算：需复数乘法2N次，复数加法）（1NN次。直接运算所用计算时间1T为ssNNNT80864.12512580864020110021）（②基2FFT运算：需复数乘法NN2log2次，复数加法NN2log次。用FFT计算1024点DTF所需计算时间2T为ssNNNNT7168.071680020log100log2222。(3)快速傅里叶变换是基于对离散傅里叶变换和利用旋转因子kNje2的来减少计算量，其特点是_______、_________和__________。解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置（4）N点的FFT的运算量为复乘、复加。解：NNLNmF2log22；NNNLaF2log4.2选择题1．在基2DIT—FFT运算中通过不断地将长序列的DFT分解成短序列的DFT，最后达到2点DFT来降低运算量。若有一个64点的序列进行基2DIT—FFT运算，需要分解次，方能完成运算。A.32B.6C.16D.8解：B2．在基2DIT—FFT运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16，倒序前信号点序号为8，则倒序后该信号点的序号为。A.8B.16C.1D.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所需的复数乘法次数与()成正比。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.基2FFT要求序列的点数为2L(其中L为整数)解：A8.不考虑某些旋转因子的特殊性，一般一个基2FFT算法的蝶形运算所需的复数乘法及复数加法次数分别为()。A.1和2B.1和1C.2和1D.2和2解：A9．计算N=2L（L为整数）点的按时间抽取基-2FFT需要()级蝶形运算。A．LB.L/2C.ND.N/2解：A10.基-2FFT算法的基本运算单元为()A.蝶形运算B.卷积运算C.相关运算D.延时运算解：A11.计算256点的按时间抽取基-2FFT，在每一级有______个蝶形。()A.256B.1024C.128D.64解：C12.如图所示的运算流图符号是_______基2FFT算法的蝶形运算流图符号。()A.按频率抽取B.按时间抽取C.A、B项都是D.A、B项都不是解：B13.求序列x(n)的1024点基2—FFT，需要_____次复数乘法。()A.1024B.1024×1024C.512×10D.1024×10解：C4.3问答题1.简述频域抽选法和时域抽选法的异同。答：相同点：（1）进行原位运算（2）运算量相同，均为NN2log2次复乘、NN2log次复加；不同点：（1）时域抽选法输入为倒位序，输出为自然顺序。频域抽选法正好与此相反，但时域抽选法也有输入为自然顺序、输出为倒位序的情况（2）蝶形运算不同2.回答以下问题：（1）画出按时域抽取4N点基FFT2的信号流图。（2）利用流图计算4点序列)4,3,1,2()(nx（3,2,1,0n）的DFT。（3）试写出利用FFT计算IFFT的步骤。解：（1）)0(x)1(x)2(x)3(x)0(X)1(X)2(X)3(X)0(0Q)1(0Q)0(1Q)1(1Q111jjkr001102W02W02W12Wkl001104W04W14W2304W04W04W24W34W4点按时间抽取FFT流图加权系数（2）112)2()0()1(532)2()0()0(00xxQxxQ341)3()1()1(541)3()1()0(11xxQxxQ1055)0()0()0(10QQX31)1()1()1(1140jQWQX055)0()0()2(1240QWQXjQWQX31)1()1()3(1340即：3,2,1,0),31,0,31,10()(kjjkX（3）具体步骤如下：1）对)(kX取共轭，得)(*kX；2）对)(kX做N点FFT；3）对2）中结果取共轭并除以N。3.已知两个N点实序列)(nx和)(ny得DFT分别为)(kX和)(kY，现在需要求出序列)(nx和)(ny，试用一次N点IFFT运算来实现。解：依据题意)()(),()(kYnykXnx取序列)()()(kjYkXkZ对)(kZ作N点IFFT可得序列)(nz。又根据DFT性质)()()]([)([)]()([njynxkYjIDFTkXIDFTkjYkXIDFT由原题可知，)(),(nynx都是实序列。再根据)()()(njynxnz，可得)](Im[)()](Re[)(nznynznx4.4计算题1.对于长度为8点的实序列)(nx，试问如何利用长度为4点的FFT计算)(nx的8点DFT？写出其表达式，并画出简略流程图。解：708)()(nnkWnxkX3,2,1,0),()()()()12()2(8304830430)12(83028kkHWkGWrhWWrgWrxWrxkrrkkrrkrkrrrk①30)4(44830)4(4)()()1(rkrkrkrWrhWWrgkX2,1,0),()()()(83048304kkHWkGWrhWWrgkrrkkrrk②按照式①和式②可画出如下图所示的流程图。)2(x)4(x)6(x)1(x)3(x)5(x)7(x)1(G)2(G08)0(WH18)1(WH28)2(WH38)3(WH)1(X)2(X)3(X)4(X)5(X)6(X)7(X111)0(G)0(X)0(x)3(G14点DFT4点DFT2.][kX是N点序列)(nx的DFT，N为偶数。两个2N点序列定义为])12[]2[(21][1nxnxnx120]),12[]2[(21][2Nnnxnxnx][1kX和][2kX分别表示序列][1nx和][2nx的2N点DFT，试由][1kX和][2kX确定][nxN点DFT。解：DFT10221202][]2[]2[NlmlNNkmkNWlxWkxkx（l为偶数）])2[][(2121][102NmXmXWWlxmlNNLlNNDFT102121202][]12[]12[NllmNNkmkNWlxWkxkx）（（l为奇数）mNmNmlNlNNNlWNmXmX]2[][(212)1(][210120],2[)1(41][)1(41][1NmNmXWmXWmXmNmN120],2[)1(41][)1(41][2NmNmXWmXWmXmNmN解上述方程可得120],[)1(][)1(][21NmmXWmXWmXmNmN120],[)1(][)1(]2[21NmmXWmXWNmXmNmN3.已知长度为2N的实序列)(nx的DFT)(kX的各个数值)12,...,1,0(Nk，现在需要由)(kX计算)(nx，为了提高效率，请设计用一次N点IFFT来完成。解：如果将)(nx按奇偶分为两组，即令1,,2,1,0)12()()2()(Nnnxnvnxnu那么就有1,,2,1,0)()()()()()(22NkkVWkUNkXkVWkUkXkNkN其中)(kU、)(kV分别是实序列)(nu、)(nv的N点DFT，)(kU、)(kV可以由上式解出1,,2,1,0)()(21)()()(21)(2NkNkXkXWkVNkXkXkUkN由于)12,...,1,0)((NkkX是已知的，因此可以将)(kX前后分半按上式那样组合起来，于是就得到了)(kU和)(kV。令)()()(njvnuny根据)(kU、)(kV，做一次N点IFFT运算，就可以同时得到)(nu和)(nv)1,...,1,0(Nn它们分别是)(nx的偶数点和奇数点序列，于是序列)(nx)12,...,1,0(Nn也就求出了。4-7采用FFT算法，可用快速卷积完成线性卷积。现预计算线性卷积)()(nhnx，试写采用快速卷积的计算步骤（注意说明点数）。答：如果)(nx，)(nh的长度分别为1N,2N,那么用长度121NNN的圆周卷积可计算线性卷积。用FFT运算来求)()(nhnx值（快速卷积）的步骤如下：（1）对序列)(nx，)(nh补零至长为N，使121NNN，并且MN2(M为整数)，即1,...1,01,...1,0)()(111NNNnNnnxnx1,...,1,01,...,1,0)()(222NNNnNnnhnh（2）用FFT计算)(nx，)(nh的离散傅立叶变换)()(kXnxFFT（N点）)()(kHnhFFT（N点）（3）计算)()()(kHkXkY（4）用IFFT计算)(kY的离散傅立叶变换得：)]([)()(kYIFFTnhnx（N点）4-8试推导时域抽取基-2FFT算法，并画出8点的FFT计算流图。解：10NnkNnXkxnW212121200221NNrkrkNNrrxrWxrW21212200221NNrkrkkNNNrrxrWWxrW21212200221NNrkkrkNNNrrxrWWxrWkNGkWHk其中21202120221NrkNrNrkNrGkxrWHkxrWGk和Hk分别是2xr和21xr的2N点的DFT，周期为2N。所以：2NGkGk，2NHkHk又因为：222NjkNkkNNNWeW2222NkkNNNNNXkGkWHkGkWHk所以222kNkNXkGkWHkNNNXkGkWHk，0,1,,12Nk8点的FFT计算流图见教材。