快速傅里叶变换FFT41填空题如果序列是一长度为64点

第一章 快速傅里叶变换（FFT） 4.1 填空题 （1）如果序列 是一长度为64点的有限长序列 ，序列 是一长度为128点的有限长序列 ，记 （线性卷积），则 为    点的序列，如果采用基 算法以快速卷积的方式实现线性卷积，则 的点数至少为    点。 解：64+128-1＝191点; 256 (2)如果一台通用机算计的速度为：平均每次复乘需100 ，每次复加需20 ，今用来计算N=1024点的DFT 。问直接运算需（  ）时间，用FFT运算需要（  ）时间。 解：①直接运算：需复数乘法 次，复数加法 次。 直接运算所用计算时间 为 ② 基2FFT运算：需复数乘法 次，复数加法 次。 用FFT计算1024点DTF所需计算时间 为 。 (3)快速傅里叶变换是基于对离散傅里叶变换          和利用旋转因子 的    来减少计算量，其特点是 _______、_________和__________。 解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置 （4）N点的FFT的运算量为复乘          、复加          。 解： ； 4.2 选择题 1．在基2DIT—FFT运算中通过不断地将长序列的DFT分解成短序列的DFT，最后达到2点DFT来降低运算量。若有一个64点的序列进行基2DIT—FFT运算，需要分解      次，方能完成运算。 A.32          B.6        C.16        D. 8 解：B 2．在基2 DIT—FFT运算时，需要对输入序列进行倒序，若进行计算的序列点数N=16，倒序前信号点序号为8，则倒序后该信号点的序号为    。 A. 8          B. 16          C. 1          D. 4 解：C 3．在时域抽取FFT运算中，要对输入信号x(n)的排列顺序进行“扰乱”。在16点FFT中，原来x(9)的位置扰乱后信号为：    。 A． x(7)        B.  x(9)      C.  x(1)        D.  x(15) 解：B 4.用按时间抽取FFT计算N点DFT所需的复数乘法次数与(    )成正比。 A.N          B.N2        C.N3          D.Nlog2N 解：D 5.直接计算N点DFT所需的复数乘法次数与(        )成正比。 A.N         B.N2          C.N3         D.Nlog2N 解：B 6.N点FFT所需的复数乘法次数为(        )。 A.N                                    B.N2 C.N3                                D.(N/2)log2N 解：D 7.下列关于FFT的说法中错误的是(     )。 A.FFT是一种新的变换 B.FFT是DFT的快速算法 C.FFT基本上可以分成时间抽取法和频率抽取法两类 D.基2 FFT要求序列的点数为2L(其中L为整数) 解：A 8.不考虑某些旋转因子的特殊性，一般一个基2 FFT算法的蝶形运算所需的复数乘法 及复数加法次数分别为(      )。 A.1和2                            B.1和1                C.2和1                            D.2和2 解：A 9．计算N=2L（L为整数）点的按时间抽取基-2FFT需要(      )级蝶形运算。 A．L                B.L/2                C.N                D.N/2 解：A 10.基-2 FFT算法的基本运算单元为(    ) A.蝶形运算    B.卷积运算 C.相关运算    D.延时运算 解：A 11.计算256点的按时间抽取基-2 FFT，在每一级有______个蝶形。(      ) A.256    B.1024    C.128    D.64 解：C 12.如图所示的运算流图符号是_______基 2FFT算法的蝶形运算流图符号。(    ) A.按频率抽取    B.按时间抽取 C.A、B项都是    D.A、B项都不是 解：B 13.求序列x(n)的1024点基2—FFT，需要_____次复数乘法。(      ) A.1024    B.1024×1024    C.512×10    D.1024×10 解：C 4.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计算流图见教材。