快速傅立叶变换FFT.pdf

快速傅里叶变换
*FFT 并不是一种新的变换形式,
它只是DFT 的一种快速算法。并
且根据对序列分解与选取方法的
不同而产生了FFT 的多种算法。
计算DFT复数运算量
))计算一个计算一个XX (k)(k)值,运算量为值,运算量为
N−1
例则 n
例k=1k=1则 X(1) = ∑x(n)WN
n=0
要进行要进行NN次复数乘法次复数乘法,,(N(N--1)1)次复数加法次复数加法
所以,要完成整个所以,要完成整个DFTDFT运算,其计算量为:运算,其计算量为:
N*NN*N次复数相乘,次复数相乘,N*(NN*(N--1)1)次复数加法次复数加法
kn
利用WN 的固有对称性和周期性
改善DFT的运算效率
kn kn * −nk
WN 的对称性:(WN ) =WN
Wkn 的周期性:π kn (n+N)k n(N+k)
N WN =WN =WN
2
− j kN
因为: kN Nπ− j2πk k = 0,1,
N − 1
(WN ) = (e ) =e =1
2
− j Nn
Nn N − j2πn n = 0,1,
N − 1
(WN ) = (e ) = e =1
n(N−k) (N−n)k −nk N
k+
由此可得出: WN =WN =WN 2 k
2π(WN ) = −WN
− j N π
N/2 N 2
(WN ) =e =cos − jsinπ= −1
2π
− j nk
nk nk N
WN 的特性 WeN =
nk*()()− nk N−− n k n N k
对称性(WWWNNN ) = == W N
↓↓
Nk− nk nN− nk
WWNN⋅ WWNN⋅
nk() Nnk+ nNk ()+
周期性 WWNN= = W N
nk mnk nk nk/ m
可约性 WWNmN= WWNNm= /
↓ 2π N
2π−⋅j
− j mnk N 2 − jπ
e mN ee= =−1
↑
0/2(/2)NkNk+
特殊点: WWNN= 1=− 1 W N =− W N
¾时间抽取基-2FFT算法
Decimation-in-Time (DIT)
一、算法原理
„ 设输入序列长度为N=2M(M为正整数,将该序
列按时间顺序的奇偶分解为越来越短的子序
列,称为基2按时间抽取的FFT算法。也称为
Coolkey-Tukey算法。
„ 其中基数2----N=2M,M为整数。若不满足这个
条件,可以人为地加上若干零值(加零补长)
使其达到 N=2M。
二二、按时间抽选的基、按时间抽选的基--2FFT2FFT算法算法
1、算法推导
设序列点数设序列点数 NN == 22M,,MM 为整数。为整数。
若不满足,则补零若不满足,则补零
N为2的整数幂的FFT算法称基-2FFT算法。
将序列x(n)按n的奇偶分成两组:
xr()2 = xr1 ( ) rN=−0,1,..., / 2 1
()()
xr21+= xr2
则则xx((nn))的的DFT:DFT:
NNN−111−−
nk nk nk
X ()kxnWxnWxnW==+∑∑∑()NNN () ()
nnn=000==
n为偶数 n为奇数
NN/2− 1 /2− 1
2rk ()21rk+
=++∑∑xrW()221NN xr ( W )
rr=00=
NN/2− 1rk /2− 1 rk
22k
=+∑∑xrWWxrW12()()NN()() N
rr=00=
NN/2− 1 /2− 1
rk k rk
=+∑∑xrW1/22/2()NN W xrW N ()
rr=00=
k
=+X12(kWXk) N ( ) rk,0,1,.../21= N −
一个一个NN点的点的DFTDFT被分解为两个被分解为两个N/2N/2点点DFTDFT。。
XX1(k)(k),,XX2(k)(k)这两个这两个N/2N/2点的点的DFTDFT按照:按照:
k
X(k) = X 1 (k) +WN X 2 (k)
又合成 N点DFT中的前半部分 k = 0,1
N / 2 −1
 再应用再应用WW系数的周期性,求出用系数的周期性,求出用XX1(k)(k),,XX2(k)(k)
表达的后半部的表达的后半部的X(k+N/2)X(k+N/2)的值。的值。
再利用周期性求再利用周期性求XX((kk))的后半部分的后半部