- 1、本文档共24页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[工学]详解FFT快速傅里叶变换FFT
第四章 快速傅里叶变换
有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年,Cooley 和 Tukey 提出了计算离散傅里叶变换(DFT)的快 速算法,将 DFT 的运算量减少了几个数量级。从此,对快速傅里叶变换(FFT) 算法的研究便不断深入,数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法,基本算法是基2DIT 和基2DIF。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。
快速傅里叶变换(FFT)是计算离散傅里叶变换(DFT)的快速算法。
DFT 的定义式为
N ?1
X (k ) = ∑ x(n)WN
RN (k )
n =0
在所有复指数值 W kn 的值全部已算好的情况下,要计算一个 X (k ) 需要 N
次复数乘法和 N-1 次复数加法。算出全部 N 点 X (k ) 共需 N 2 次复数乘法 和 N ( N ? 1) 次复数加法。即计算量是与 N 2 成正比的。
FFT 的基本思想:将大点数的 DFT 分解为若干个小点数 DFT 的组合, 从而减少运算量。
WN 因子具有以下两个特性,可使 DFT 运算量尽量分解为小点数的 DFT
运算:
(1) 周期性:
( k + N ) n
N
= W kn
= W ( n + N ) k
(2) 对称性:W ( k + N / 2 ) = ?W k
N N
利用这两个性质,可以使 DFT 运算中有些项合并,以减少乘法次数。例子:
求当 N=4 时,X(2)的值
3
∑ 4 4 4 4 4
X (2) =
n =0
x(n)W 2 n = x(0)W 0 + x(1)W 2 + x(2)W 4 + x(3)W 6
= [ x(0) + x(2)]W 0 + [ x(1) + x(3)]W 2
(周期性)
4
=[ x(0) + x(2)]-[ x(1) + x(3)]W 0
4
(对称性)
通过合并,使乘法次数由 4 次减少到 1 次,运算量减少。
FFT 的算法形式有很多种,但基本上可以分为两大类:按时间抽取
(DIT)和按频率抽取(DIF)。
4.1 按时间抽取(DIT)的 FTT
为了将大点数的 DFT 分解为小点数的 DFT 运算,要求序列的长度 N 为 复合数,最常用的是 N = 2 M 的情况(M 为正整数)。该情况下的变换称为 基 2FFT。下面讨论基 2 情况的算法。
先将序列 x(n)按奇偶项分解为两组
?x(2r ) = x1 (r )
?
?x(2r + 1) = x2 (r )
将 DFT 运算也相应分为两组
N
r = 0,1,L, 2 ? 1
N ?1
X (k ) = DFT [ x(n)] = ∑ x(n)W kn
n =0
N ?1
= ∑ x(n)W kn+
N ?1
∑ x(n)W kn
n=0
n为偶数
n =0
n 为奇数
N / 2?1
∑ (2 )
2 rk +
N / 2?1
∑ (2
+ 1)
( 2 r +1) k
= x
r =0
r WN
x r WN
r =0
N / 2?1
∑
2 rk +
N / 2?1
k ∑
2 rk
=
r =0
x1 (r )WN
WN
r =0
x2 (r )WN
N / 2?1
= ∑ x1 (r )W
r =0
N / 2 + WN
N / 2?1
∑ x2 (r )W
r =0
rk
N / 2
(因为W
2 rk
N
rk
N / 2
= X 1 (k ) + WN X 2 (k )
其中 X 1 (k ) 、 X 2 (k ) 分别是 x1 (n)、x2 (n) 的 N/2 点的 DFT
N / 2?1
N / 2?1
rk rk
X 1 (k ) = ∑ x1 (r )WN / 2 = ∑ x(2r )WN / 2 ,0 ≤ k ≤ ? 1
r =0
r =0 2
N / 2 ?1
N / 2 ?1
rk
rk N
X 2 (k ) = ∑ x 2 (r )W N / 2 = ∑ x(2r + 1)W N / 2 ,0 ≤ k ≤ ?1
r =0
r =0 2
至此,一个 N 点 DFT 被分解为两个 N/2 点的 DFT。
上面是否将全部 N 点的 X (k ) 求解出来了?
分析: X 1 (k ) 和
N
X 2 (k ) 只有
文档评论(0)