数字信号处理习题集(附答案) 下载本文

第四章 快速傅立叶变换

一、 计算DFT效率及其改善途径

填空题:

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

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

T1?N2?100?N(N?1)?20?125808640?s?125.80864s (2)基2FFT运算:需复数乘法

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

T2?Nlog2N?100?Nlog2N?20?716800?s?0.7168s 22.N点FFT的运算量大约是( )。 解:

Nlog2N次复乘和Nlog2N次复加 23.快速傅里叶变换是基于对离散傅里叶变换 ___________和利用旋

转因子e?j2?kN的________ 来减少计算量,其特点是

_______,_________和__________。

解:快速傅里叶变换是基于对离散傅里叶变换 长度逐次变短 和利用旋转因子e?j2?kN的 周期性 来减少计算量,其特点是 蝶形计算、 原

位计算 和 码位倒置。

简答题:

4.FFT主要利用了DFT定义中的正交完备基函数

nWN(n?0,1,?,N?1)的周

期性和对称性,通过将大点数的DFT运算转换为多个小数点的DFT运算,实现计算量的降低。请写出WN的周期性和对称性表达式。 答:①周期性:WN(n?N)k?WNnk?WN(k?N)n ②对称性:WNn?N2??WNn

5.基2FFT快速计算的原理是什么?它所需的复乘、复加次数各是多

少?

解:原理:利用WNkn的特性,将N点序列分解为较短的序列,计算短序列的DFT,最后再组合起来。 复乘次数:

二、 按时间抽取FFT算法

简答题:

1.简略推导按时间抽取基2-FFT算法的蝶形公式,并画出N=8时算法

NNN,复加次数:Nlog2 log22的流图,说明该算法的同址运算特点。 解:答案略。

作图题:

3.画出N?8基2 时间抽取的FFT流图,并利用该流图计算序列

x[k]??1,1,1,1,0,0,0,0?的DFT。

解:答案略。

4.对于长度为8点的实序列x(n),试问如何利用长度为4点的FFT计算

x(n)的8点DFT?写出其表达式,并画出简略流程图。

解:X(k)??x(n)W8nk

n?07??x(2r)Wr?0332rk8??x(2r?1)W8(2r?1)kr?0k83 ??g(r)W?Wrk4r?0?h(r)Wr?03rk4

?G(k)?W8kH(k),k?0,1,2,3①

X(k?1)??g(r)Wr?03r(k?4)4?Wk?48?h(r)Wr?03r(k?4)4

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

?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)?1?1X(4)X(5)X(6)X(7)

三、按频率抽取FFT算法

计算题:

N1.X[k]是N点序列x[n]的DFT,N为偶数。两个2点序列定义为

1x1[n]?(x[2n]?x[2n?1])2

x2[n]?1N(x[2n]?x[2n?1]),0?n??122

N X1[k]和X2[k]分别表示序列x1[n]和x2[n]的2点DFT,试由X1[k]和X2[k]确定x[n]的N点DFT。

解:

mk DFT?x[2k]???x[2k]WN??x[l]Wk?02l?0N?12N?1ml2N2 (l为偶数)

??x[l]L?0N?11?W1NmlWN?(X[m]?X[m?]) 222N?1l?0m(l?1)2N2lN2Nmk??x[l]W DFT?x[2k?1]???x[2k?1]WNk?02N?12(l为奇数)

??x[l](1?W)WNmlWN?m?1(X[m]?X[m?N]WN?m

N?1l?0lN2N222X1[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 2X[m?NNmm]?(1?WN)X1[m]?(1?WN)X2[m],0?m??1 22

简答题: 2.

简略推导按频率抽取基2-FFT算法的蝶形公式,并画出N?8时

算法的流图,说明该算法的同址运算特点。

【答案】其同址运算特点为输入按自然顺序存放,输出序列按码位颠倒顺序存放。

作图题: 3.

画出基2 时域抽取4点FFT的信号流图。

解:答案略。

四、 其它FFT算法

简答题: