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

第一章

4.1 填空题

快速傅里叶变换（FFT）

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

，则y(n)为 点的序列，如果n?127)，记y(n)?x(n)?h(n)（线性卷积）

采用基2FFT算法以快速卷积的方式实现线性卷积，则FFT的点数至少为 点。 解：64+128-1＝191点; 256

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

解：①直接运算：需复数乘法N次，复数加法N（N直接运算所用计算时间T1为

2次。 ?1）T1?N2?100?N（N?1）?20?125808640?s?125.80864s

② 基2FFT运算：需复数乘法

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

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

2(3)快速傅里叶变换是基于对离散傅里叶变换 和利用旋转因子e来减少计算量，其特点是 _______、_________和__________。

解：长度逐次变短；周期性；蝶形计算、原位计算、码位倒置 （4）N点的FFT的运算量为复乘 、复加 。 解：mF4.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)

?j2?kN的

?NNL?log2N；aF?NL?Nlog2N 22的位置扰乱后信号为： 。

A． x(7) B. x(9) C. x(1) D. x(15) 解：B

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

5.直接计算N点DFT所需的复数乘法次数与( )成正比。 A.N B.N2 C.N3 D.Nlog2N 解：B

6.N点FFT所需的复数乘法次数为( )。 A.N C.N3 解：D

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

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

8.不考虑某些旋转因子的特殊性，一般一个基2 FFT算法的蝶形运算所需的复数乘法 及复数加法次数分别为( )。 A.1和2 C.2和1 解：A

9．计算N=2L（L为整数）点的按时间抽取基-2FFT需要( )级蝶形运算。 A．L 解：A

10.基-2 FFT算法的基本运算单元为( ) A.蝶形运算 C.相关运算 解：A

11.计算256点的按时间抽取基-2 FFT，在每一级有______个蝶形。( ) A.256 C.128

B.1024 D.64 B.卷积运算 D.延时运算

B.L/2

C.N

D.N/2

B.1和1 D.2和2

B.N2

B.N2 C.N3

D.Nlog2N

D.(N/2)log2N

解：C

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

13.求序列x(n)的1024点基2—FFT，需要_____次复数乘法。( ) A.1024 C.512×10 解：C

4.3 问答题

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

答：相同点：（1）进行原位运算（2）运算量相同，均为

B.1024×1024 D.1024×10

Nlog2N次复乘、Nlog2N次 2复加；不同点：（1）时域抽选法输入为倒位序，输出为自然顺序。频域抽选法正好与此相反，但时域抽选法也有输入为自然顺序、输出为倒位序的情况（2）蝶形运算不同 2.回答以下问题：

（1） 画出按时域抽取N?4点基2FFT的信号流图。

?(2,1,3,4)（n?0,1,2,3）的DFT。

（2） 利用流图计算4点序列x(n)（3） 试写出利用FFT计算IFFT的步骤。

解：（1）

x(0)x(2)x(1)x(3)Q0(0)Q0(1)?1Q(0)Q1(1)?11X(0)?j?1jX(1)X(2)X(3)

r01k0W20W2011W20W2l01k0W40W4011W40W423W40W42W40W43

4点按时间抽取FFT流图 加权系数 （2）

?Q0(0)?x(0)?x(2)?2?3?5 ??Q0(1)?x(0)?x(2)?2?1??1?Q1(0)?x(1)?x(3)?1?4?5 ??Q1(1)?x(1)?x(3)?1?4??3X(0)?Q0(0)?Q1(0)?5?5?10 X(1)?Q0(1)?W41Q1(1)??1?j?3

X(2)?Q0(0)?W42Q1(0)?5?5?0

X(3)?Q0(1)?W43Q1(1)??1?3j

即：

X(k)?(10,?1?3j,0,?1?3j),k?0,1,2,3

（3）具体步骤如下：

1）对

X(k)取共轭，得X*(k)；

? 2）对X(k)做N点FFT；

3）对2）中结果取共轭并除以N。

3.已知两个N点实序列

x(n)和y(n)得DFT分别为X(k)和Y(k)，现在需要求出序列x(n)和

y(n)，试用一次N点IFFT运算来实现。

解：依据题意

x(n)?X(k),y(n)?Y(k)

Z(k)?X(k)?jY(k)

取序列

对Z(k)作N点IFFT可得序列又根据DFT性质

z(n)。

IDFT[X(k)?jY(k)]?IDFT[X(k)?jIDFT[Y(k)]?x(n)?jy(n)

由原题可知，

x(n),y(n)都是实序列。再根据z(n)?x(n)?jy(n)，可得

x(n)?Re[z(n)]y(n)?Im[z(n)]

4.4 计算题

1. 对于长度为8点的实序列x(n)，试问如何利用长度为4点的FFT计算x(n)的8点DFT？写出其表达式，并画出简略流程图。 解：

X(k)??x(n)W8nkn?07

??x(2r)Wr?0332rk8??x(2r?1)W8(2r?1)kr?0k83

??g(r)Wr?0rk4?W?h(r)Wr?033rk4 ①

?G(k)?W8kH(k),k?0,1,2,3X(k?1)??g(r)Wr?03r(k?4)4?W3k?48?h(r)Wr?0rk4r(k?4)4

??g(r)Wr?03rk4?Wk8?h(r)Wr?0 ②

?G(k)?W8kH(k),k?0,1,2按照式①和式②可画出如下图所示的流程图。

x(0)x(2)G(0)x(4)x(6)x(1)x(3)x(5)4点DFTG(1)X(0)X(1)G(2)G(3)H(0)W80X(2)X(3)?1?14点H(2)W82DFT3H(3)W8H(1)W81x(7)2.

?1?1X(4)X(5)X(6)X(7)

X[k]是N点序列x(n)的DFT，N为偶数。两个

N2点序列定义为

x1[n]?1(x[2n]?x[2n?1]) 21N(x[2n]?x[2n?1]),0?n??1 22NX1[k]和X2[k]分别表示序列x1[n]和x2[n]的点DFT，试由X1[k]和X2[k]确定x[n]N

2x2[n]?N?12k?0N?1l?0ml2N2点DFT。

解：DFT

?x[2k]???x[2k]W??x[l]L?0N?1mkN2??x[l]W （l为偶数）

1?W1NmlWN?(X[m]?X[m?]) 222N?1l?0m（l?1）2（lN2lN2N DFT

?x[2k?1]???x[2k?1]WNmk??x[l]Wk?02lN2NN?12为奇数）

??x[l]l?0N?1(1?W2)ml?mWNWN?1N?m (X[m]?X[m?]WN22X1[m]?X2[m]?11NN?m?m(1?WN)X[m]?(1?WN)X[m?],0?m??1 442211NN?m?m(1?WN)X[m]?(1?WN)X[m?],0?m??1 4422解上述方程可得

mmX[m]?(1?WN)X1[m]?(1?WN)X2[m],0?m?N?1 2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库快速傅里叶变换(FFT)试题在线全文阅读。