第一章 快速傅里叶变换（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点DF
T来降低运算量。若有一个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）运算量相同，均为次复乘、次