快速傅里叶变换(FFT)试题(6页).doc

-第一章第二章第三章 快速傅里叶变换(FFT)试题-第 6 页第四章 快速傅里叶变换（FFT）4.1 填空题 （1）如果序列是一长度为64点的有限长序列，序列是一长度为128点的有限长序列，记（线性卷积），则为 点的序列，如果采用基算法以快速卷积的方式实现线性卷积，则的点数至少为 点。解：64+128-1191点; 256(2)如果一台通用机算计的速度为：平均每次复乘需100，每次复加需20，今用来计算N=1024点的DFT。问直接运算需（ ）时间，用FFT运算需要（ ）时间。解：直接运算：需复数乘法次，复数加法次。直接运算所用计算时间为 基2FFT运算：需复数乘法次，复数加法次。用FFT计算1024点DTF所需计算时间为(3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子的 来减少计算量，其特点是 _、_和_。解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置（4）N点的FFT的运算量为复乘 、复加 。解：；4.2 选择题1在基2DITFFT运算中通过不断地将长序列的DFT分解成短序列的DFT，最后达到2点DFT来降低运算量。若有一个64点的序列进行基2DITFFT运算，需要分解 次，方能完成运算。 A.32 B.6 C.16 D. 8解：B2在基2 DITFFT运算时，需要对输入序列进行倒序，若进行计算的序列点数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所需的复数乘法次数与( )成正比。A.N B.N2 C.N3 D.Nlog2N解：D5.直接计算N点DFT所需的复数乘法次数与(        )成正比。A.N         B.N2 C.N3         D.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.不考虑某些旋转因子的特殊性，一般一个基2 FFT算法的蝶形运算所需的复数乘法及复数加法次数分别为( )。A.1和2B.1和1C.2和1D.2和2解：A9计算N=2L（L为整数）点的按时间抽取基-2FFT需要( )级蝶形运算。ALB.L/2C.ND.N/2解：A10.基-2 FFT算法的基本运算单元为( )A.蝶形运算B.卷积运算C.相关运算D.延时运算解：A11.计算256点的按时间抽取基-2 FFT，在每一级有_个蝶形。( )A.256B.1024C.128D.64解：C12.如图所示的运算流图符号是_基2FFT算法的蝶形运算流图符号。( )A.按频率抽取B.按时间抽取C.A、B项都是D.A、B项都不是解：B13.求序列x(n)的1024点基2FFT，需要_次复数乘法。( )A.1024B.1024×1024C.512×10D.1024×10解：C4.3 问答题1.简述频域抽选法和时域抽选法的异同。 答：相同点：（1）进行原位运算（2）运算量相同，均为次复乘、次复加；不同点：（1）时域抽选法输入为倒位序，输出为自然顺序。频域抽选法正好与此相反，但时域抽选法也有输入为自然顺序、输出为倒位序的情况（2）蝶形运算不同2.回答以下问题：（1） 画出按时域抽取点基的信号流图。（2） 利用流图计算4点序列（）的。（3） 试写出利用计算的步骤。解：（1） 4点按时间抽取FFT流图 加权系数 （2） 即： （3）具体步骤如下：1）对取共轭，得； 2）对做N点FFT； 3）对2）中结果取共轭并除以N。 3.已知两个N点实序列和得DFT分别为和，现在需要求出序列和，试用一次N点IFFT运算来实现。解：依据题意 取序列 对作N点IFFT可得序列。又根据DFT性质 由原题可知，都是实序列。再根据，可得 4.4 计算题1. 对于长度为8点的实序列，试问如何利用长度为4点的FFT计算的8点DFT？写出其表达式，并画出简略流程图。解：按照式和式可画出如下图所示的流程图。2.是N点序列的DFT，N为偶数。两个点序列定义为和分别表示序列和的点DFT，试由和确定点DFT。解：DFT （为偶数） DFT（为奇数）解上述方程可得3.已知长度为2N的实序列的DFT的各个数值，现在需要由计算，为了提高效率，请设计用一次N点IFFT来完成。解：如果将按奇偶分为两组，即令那么就有 其中、分别是实序列、的N点DFT，、可以由上式解出由于是已知的，因此可以将前后分半按上式那样组合起来，于是就得到了和。令根据、，做一次N点IFFT运算，就可以同时得到和它们分别是的偶数点和奇数点序列，于是序列也就求出了。4-7 采用FFT算法，可用快速卷积完成线性卷积。现预计算线性卷积，试写采用快速卷积的计算步骤（注意说明点数）。答：如果，的长度分别为,那么用长度的圆周卷积可计算线性卷积。用FFT运算来求值（快速卷积）的步骤如下：（1） 对序列，补零至长为N，使，并且(M为整数)，即（2） 用FFT计算，的离散傅立叶变换 （N点） （N点）（3） 计算（4） 用IFFT计算的离散傅立叶变换得： （N点）4-8试推导时域抽取基-2 FFT算法，并画出8点的FFT计算流图。解：其中 和分别是和的点的DFT，周期为。所以： ，又因为： 所以 ，8点的FFT计算流图见教材。