1、4.1 填空题 （1）如果序列 是一长度为 64 点的有限长序列 ，序列)(nx )630(n是一长度为 128 点的有限长序列 ，记 （线性)(nh )1270(n(hxy卷积） ，则 为 点的序列，如果采用基 算法以快速卷积的方式实)(y FT现线性卷积，则 的点数至少为 点。FT解：64+128-1191 点; 256(2)如果一台通用机算计的速度为：平均每次复乘需 100 ，每次复加需 20s，今用来计算 N=1024 点的 DFT 。问直接运算需（ ）时间，用 FFTs)(nx运算需要（ ）时间。解：直接运算：需复数乘法 次，复数加法 次。2N）（ 1N直接运算所用计算时间 为1T
2、ssNT 8064.25158064021 ）（ 基 2FFT 运算：需复数乘法 次，复数加法 次。2log2log用 FFT 计算 1024 点 DTF 所需计算时间 为T。ssNNT 7168.071680l10log22 (3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子的 kNje来减少计算量，其特点是 _、_和_。解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置（4）N点的FFT的运算量为复乘 、复加 。解： ；NLmF2logNLaF2log4.2 选择题1在基 2DITFFT 运算中通过不断地将长序列的 DFT 分解成短序列的DFT，最后达到 2 点 DFT 来降低
3、运算量。若有一个 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 所需的复数乘法次数与(
4、)成正比。A.N B.N2 C.N3 D.Nlog2N解：D5.直接计算 N 点 DFT 所需的复数乘法次数与( )成正比。A.N B.N2 C.N3 D.Nlog2N 解：B6.N 点 FFT 所需的复数乘法次数为( )。A.N B.N2C.N3 D.(N/2)log2N解：D7.下列关于 FFT 的说法中错误的是 ( )。 A.FFT 是一种新的变换 B.FFT 是 DFT 的快速算法 C.FFT 基本上可以分成时间抽取法和频率抽取法两类 D.基 2 FFT 要求序列的点数为 2L(其中 L 为整数)解：A8.不考虑某些旋转因子的特殊性，一般一个基 2 FFT 算法的蝶形运算所需的复数乘法
5、及复数加法次数分别为( )。A.1 和 2 B.1 和 1C.2 和 1 D.2 和 2解：A9计算 N=2L（L 为整数）点的按时间抽取基-2FFT 需要( )级蝶形运算。AL B.L/2 C.N D.N/2解：A10.基-2 FFT 算法的基本运算单元为( )A.蝶形运算 B.卷积运算C.相关运算 D.延时运算解：A11.计算 256 点的按时间抽取基-2 FFT，在每一级有_个蝶形。( )A.256 B.1024C.128 D.64解：C12.如图所示的运算流图符号是_基2FFT 算法的蝶形运算流图符号。( )A.按频率抽取B.按时间抽取C.A、B 项都是D.A、B 项都不是解：B13.
6、求序列 x(n)的 1024 点基 2FFT，需要_次复数乘法。 ( )A.1024 B.10241024C.51210 D.102410解：C4.3 问答题1.简述频域抽选法和时域抽选法的异同。答：相同点：（1）进行原位运算（2）运算量相同，均为 次复乘、N2log次Nlog复加；不同点：（1）时域抽选法输入为倒位序，输出为自然顺序。频域抽选法正好与此相反，但时域抽选法也有输入为自然顺序、输出为倒位序的情况（2）蝶形运算不同2.回答以下问题：（1） 画出按时域抽取 点基 的信号流图。4NFT2（2） 利用流图计算 4 点序列 （ ）的)4,31()nx3,210n。DFT（3） 试写出利用
7、计算 的步骤。FTI解：（1）)0(x)1(x)2()3( )0(X)1()2(X)3()0(Q)1(0)(1Q)(1 1jj kr0112W020212 kl0114W0414230404W0424344 点按时间抽取 FFT 流图 加权系数（2） 12)(0)(50x1)()(501xQ)0(X3)()14jW052(20 j(3134即： ,21),)kjkX（3）具体步骤如下：1）对 取共轭，得 ；)(k(*2）对 做 N 点 FFT；3）对 2）中结果取共轭并除以 N。3.已知两个N点实序列 和 得DFT分别为 和 ，现在需要求)(nxy)(kXY出序列 和 ，试用一次N点IFFT
8、运算来实现。)(nxy解：依据题意 )(,YkX取序列 )(kjZ对 作 N 点 IFFT 可得序列 。)(kZnz又根据 DFT 性质 )()()()( njyxkYjIDFTkXITkjYXIDFT 由原题可知， 都是实序列。再根据 ，可得 ,ynx nz)(Im)(Renx4.4 计算题1. 对于长度为8点的实序列 ，试问如何利用长度为4点的FFT 计算 的8)(nx )(nx点DFT？写出其表达式，并画出简略流程图。解： 708)()(nnkWxkX3,210),()()2(8343040)12(88kHWkGrhrgxxkkrkrk0)4(4830)4(1( rkrrrX2,1),(
9、)(8304304kHWkGhgkrrkrr按照式和式可画出如下图所示的流程图。 )2(x46)1(x35)7()1(2G08)(WH1238)( )1(X23)4(5X6)7(100034点DFT4点DFT2. 是N点序列 的DFT，N为偶数。两个 点序列定义为kXnx2N)12(1nx0,22 x和 分别表示序列 和 的 点DFT，试由 和 确定1kX12xN1kX2nxN点DFT。解：DFT （ 为偶数）1021202NlmlNkmkWxxx)2(10 NXllNNL DFT （ 为奇数）10211202 NllmNkmkWxxx ）（mNmNllNl X 2()1(0 10,)(4)(
10、41 XWmXmN 2,)1()(2 mXmN解上述方程可得 120,)1()1( 21 NWmXmNmN,)()(2 21 XX3.已知长度为 2N 的实序列 的 DFT 的各个数值 ，nxk)12,.0(Nk现在需要由 计算 ，为了提高效率，请设计用一次 N 点 IFFT 来完成。)(kX)(解：如果将 按奇偶分为两组，即令nx 1,20)12() nxnvu那么就有 1,20)()()2NkVWkUNkXkN其中 、 分别是实序列 、 的 N 点 DFT， 、 可)Vnuv)(kUV以由上式解出 1,20)()21)( kkXkkN 由于 是已知的，因此可以将 前后分半按上式那,.0X
11、)(X样组合起来，于是就得到了 和 。令)(UVnjvuny根据 、 ，做一次N点IFFT运算，就可以同时得到 和)(kUV )(nuv1,.0(n它们分别是 的偶数点和奇数点序列，于是序列 也就)(nx )(nx)12,.0N求出了。4-7 采用 FFT 算法，可用快速卷积完成线性卷积。现预计算线性卷积 ，(nhx试写采用快速卷积的计算步骤（注意说明点数） 。答：如果 ， 的长度分别为 , ,那么用长度 的圆周)(nxh1N2 121卷积可计算线性卷积。用 FFT 运算来求 值（快速卷积）的步骤如下：)(nhx（1） 对序列 ， 补零至长为 N，使 ，并且)(xn21(M 为MN2整数)，即
12、 1,.,0)(1nx,.,)(2Nhn（2） 用 FFT 计算 ， 的离散傅立叶变换)(x（N 点）)(kXFT （N 点）Hnh（3） 计算 )()(kXkY（4） 用 IFFT 计算 的离散傅立叶变换得：（ N 点）)(kYIFTx4-8 试推导时域抽取基-2 FFT 算法，并画出 8 点的 FFT 计算流图。解： 10NnknXkxW21212100NrkrkNr xW21212 200Nrk rkNr rx21212200rk rkNr rxkNGWH其中 2120NrkNrrkrGkxWH和 分别是 和 的 点的 DFT，周期为 。Gk2x122N所以： ，NkGNkH又因为： 22jkkkNNWeW 2 kNXGW所以 ，22kNkGH 0,12k8 点的 FFT 计算流图见教材。
