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

第一章

快速傅里叶变换()

4.1 填空题

(1)如果序列x(n)是一长度为64点的有限长序列(0?n?63),序列h(n)是一长度为128点的有限长序列(0?n?127),记

,则y(n)为 点的序列,如果采用y(n)?x(n)?h(n)(线性卷积)

基2FFT算法以快速卷积的方式实现线性卷积,则FFT的点数至少为 点。

解:64+128-1=191点; 256

(2)如果一台通用机算计的速度为:平均每次复乘需100?s,每次复加需20?s,今用来计算1024点的[x(n)]。问直接运算需( )时间,用运算需要( )时间。

解:①直接运算:需复数乘法N2次,复数加法N(N?1)次。 直接运算所用计算时间T1为

T1?N2?100?N(N?1)?20?125808640?s?125.80864s

② 基2运算:需复数乘法

Nlog2N次,复数加法Nlog2N次。 2用计算1024点所需计算时间T2为

NT2?log2N?100?Nlog2N?20?716800?s?0.7168s。

2(3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子e?j2?kN的

来减少计算量,其特点是 、和。

解:长度逐次变短;周期性;蝶形计算、原位计算、码位倒置

(4)N点的的运算量为复乘 、复加 。

解:mF?NNL?log2N;aF?NL?Nlog2N22

4.2 选择题

1.在基2—运算中通过不断地将长序列的分解成短序列的,最后达到2点来降低运算量。若有一个64点的序列进行基2—运算,需要分解 次,方能完成运算。

/ 9

A.32 B.6 C.16 D. 8 解:B

2.在基2 —运算时,需要对输入序列进行倒序,若进行计算的序列点数16,倒序前信号点序号为8,则倒序后该信号点的序号为 。

A. 8 B. 16 C. 1 D. 4 解:C

3.在时域抽取运算中,要对输入信号x(n)的排列顺序进行“扰乱”。在16点中,原来x(9)的位置扰乱后信号为: 。 A. x(7) B. x(9) C. x(1) D. x(15) 解:B

4.用按时间抽取计算N点所需的复数乘法次数与( )成正比。

23

2N 解:D

5.直接计算N点所需的复数乘法次数与( )成正比。

23

2N 解:B

6点所需的复数乘法次数为( )。

2

3

D.(2)2N

解:D

7.下列关于的说法中错误的是( )。 是一种新的变换 是的快速算法

基本上可以分成时间抽取法和频率抽取法两类 D.基2 要求序列的点数为2L(其中L为整数) 解:A

8.不考虑某些旋转因子的特殊性,一般一个基2 算法的蝶形运算所需的复数乘法

及复数加法次数分别为( )。

A.1和2 B.1和1

/ 9

C.2和1 D.2和2 解:A

L

9.计算2(L为整数)点的按时间抽取基-2需要( )级蝶形运算。

A.L 2 2 解:A

10.基-2 算法的基本运算单元为( ) A.蝶形运算 B.卷积运算 C.相关运算 D.延时运算 解:A

11.计算256点的按时间抽取基-2 ,在每一级有个蝶形。( ) A.256 B.1024 C.128 D.64 解:C

12.如图所示的运算流图符号是基 2算法的蝶形运算流图符号。( ) A.按频率抽取 B.按时间抽取 、B项都是 、B项都不是 解:B

13.求序列x(n)的1024点基2—,需要次复数乘法。( ) A.1024 B.1024×1024 C.512×10 D.1024×10

解:C

4.3 问答题

1.简述频域抽选法和时域抽选法的异同。

答:相同点:(1)进行原位运算(2)运算量相同,均为log2N次复乘、Nlog2N次

复加;不同点:(1)时域抽选法输入为倒位序,输出为自然顺序。

/ 9

N2

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4