第四章 快速傅立叶变换
一、 计算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算法
简答题：