快速傅里叶变换(FFT)
一、教学目的及要求
1. 了解FFT 与DFT 的关系；
2. 了解DFT ，FFT 存在的计算量的问题；
3. 熟悉FFT 的理论依据；掌握时间抽取基2-FFT(即DIT-FFT)算法的原理。
二、教学重点及难点
重点：直接计算N 点DFT 的计算量；减少运算量的基本途径；时间抽取基2-FFT 算法的基本思想(蝶式运算图)。
难点：利用DFT 的运算规律及其中某些算子的特殊性质（nk
N W 的周期性和对称性），找出减少乘法和加法运算次数的有效途径。
三、教学内容
1. 直接计算N 点DFT 的运算量
1,,1,0,)()(1
0-==∑-=-N k W n x k X N n kn N
复数乘法次数：N 2，复数加法次数：N (N -1)，N 很大近似为N 2
思考题：如果计算机的速度为平均每次复数乘需要5×10-6秒，每次复加需要1×10-6秒，用来计算N =1024点DFT ，直接计算需要多少时间？
s
N N N T 29.610231024101024105)
1(10105626626≈⨯⨯+⨯⨯=-⨯⨯+⨯⨯=----直接计算所需时间为：
2. 减少运算量的途径：
(1) 用旋转因子的性质减少运算量
k N
N k N N N N m nk m N nk N mnk mN nk N nk N
k n N N k n N N
nk N nk N nk N j nk N W W W W W W W W W W W W W e W -=-====++-*-)2(20
//))(-2,11)4,)3)2)1，＝特殊点：＝可约性：周期性：＝＝）对称性：（性质
（π
(2) 减少序列的长度，即把长度为N 的序列分解为长度为N /2的序列
(3) 利用DFT 的对称性及周期性(N )
3. 基2-DIT-FFT 算法原理(N =2M )
(1) 算法的推导过程
1
,,1,0 ),()12(1
,,1,0 ),()2(DFT )(2221-==+-==N
N
r r x r x n r r x r x n n n x 为奇数时：为偶数时：，
的奇偶分为两组作按将
则x (n )的DFT 可以表示为：
12
,,1,0)()()()()()()12()2()()()()(212
/12
021202/1120)12(212021
120)12(12
0210
-=+=+=+=++=+=
=∑∑∑∑∑∑∑∑∑-=-=-=+-=-=+-===-=N k k X W k X W r x W W r x W r x W r x W r x W
r x W n x W n x W n x k X k N r N N r k N N r kr N N r r k N
N r r k N N r r k N N r r k N n kn N n kn N N n kn N 奇数偶数(1) (1)式即为序列x (n )分解为两个长度为N /2的奇、偶序列，其前N /2个点的DFT ，对于其后N /2个点的DFT ，可利用DFT 的周期性求得。
由DFT 的隐含周期性，可得：
)()2(11k X N k X =+和)()2
(22k X N k X =+ 从而有：
1
2/,,1,0)()()2()2()2(2122/1-=-=+++=++N k k X W k X N k X W N k X N k X k N N k N (2) (2)式即为序列x (n )分解为两个长度为N /2的奇、偶序列后其后N /2个点的DFT 。
(2) 蝶式运算图
式(1)和式(2)可用如下的蝶式图表示：
(3) N =8时，序列第一次分解的蝶式运算图
(4) 为减少运算量，进一步把长度为N /2的两个序列进一步分解为长度为N /4的序列，则有：
14,,1,0)()()4(14,
,1,0)()()(42/3142/31-=-=+-=+=N k k X W k X N k X N k k X W k X k X k N k N (3) 14,,1,0)()()4(14,
,1,0)()()(62/5262/52-=-=+-=+=N k k X W k X N k X N k k X W k X k X k N k N (4) (5) N=8时，序列完整分解的蝶式运算图
(6)对于长度为N (N =2M )的序列，经过M -1次分解，分解为2M -1个长度为2的序列，其运算量如下：共有M 级分解，每一级有2M-1个蝶式运算，每一个蝶式运算包括一次复数乘法运算两次加法运算，所以经过基2-FFT 后，其运算量为：
复数乘法次数：M *2M-1=N /2*log 2N 复数加法次数：N *log 2N
与直接运算DFT 的运算量相比，大大降低了运算量。
(7) 蝶式运算的特点：
➢ FFT 输入序列的顺序看似杂乱无章，其实是正常顺序的倒序(怎样实现？按序
列长度的二进制位从低位到高位按照0、1抽取)。
➢ 旋转因子的特点：
➢ 蝶形类型随迭代次数成倍增加，每迭代一次，蝶形类型增加一倍，数据点间隔也
增加一倍。
3. 进一步利用FFT 减少运算量的措施：
(1) 怎样通过计算一次N 点FFT ，得到两个实序列的N 点FFT 。
(2) 怎样通过计算一次N 点FFT ，得到2N 点FFT 。
思考题：在时域内把序列分成前后两半的序列，在频域内是否对应奇偶抽取的结论(基2DIF －FFT)
小结：
(1) 减少DFT 运算量的途径
(2) 基2-DIT-FFT 基本思想
(3) 蝶形运算的特点
(4) 进一步减少FFT 运算量的途径。