详解FFT（快速傅里叶变换）
4星 · 超过85%的资源 需积分: 33 8 浏览量
2008-12-10
16:13:47
上传
评论 3
收藏 185KB PDF 举报 
第四章 快速傅里叶变换
有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长
序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换
(FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT）的快
速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）
算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发
展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算
法，基本算法是基２DIT 和基２DIF。FFT 在离散傅里叶反变换、线性卷积
和线性相关等方面也有重要应用。
快速傅里叶变换（FFT）是计算离散傅里叶变换（DFT）的快速算法。
DFT的定义式为
)(kX
=
)()(
1
0
kRWnx
N
N
n
kn
N
∑
−
=
在所有复指数值 的值全部已算好的情况下，要计算一个 需要 N
次复数乘法和 N－1 次复数加法。算出全部 N 点 共需 次复数乘法
和 次复数加法。即计算量是与 成正比的。
kn
N
W )(kX
)(kX
2
N
)1( −NN
2
N
FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合，
从而减少运算量。
N
W 因子具有以下两个特性，可使 DFT运算量尽量分解为小点数的 DFT
运算：
（1） 周期性：
kNn
N
kn
N
nNk
N
WWW
)()( ++
==
（2） 对称性：
k
N
Nk
N
WW −=
+ )2/(
利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子：
求当 N＝4 时，X(2)的值
剩余12页未读，继续阅读
资源评论
wangmarlin2013-04-10内容还可以，要仔细阅读
updown2012-09-18还可以，都是理论层面的介绍，要是能配上算法实现的代码就好了。
lisajelly2012-10-19算法介绍的很浅显易懂，很不错的资料，但是混合基算法介绍的太少了。
