第22卷第2期 2006年6月
上海电力学院学报
Vol.22,No.2June 2006
Journal of Shanghai University of Electric Power
文章编号:1006-4729(2006)02-0192-03
快速傅里叶变换的原理与方法
曹伟丽
(上海理工大学理学院,上海 )
摘 要:对样本点为N=2的离散傅里叶变换,,得到一组等价的迭代方程,,.与直接计算相比,大大减少了运算次数,,不需再设置其他存储单元.关键词:;对偶结点对;运算次数中图分类号:文献标识码:A
γ
PrincipleandMethodologyof
theFastFourierTransform
CAOWeiˉli
(InstituteofScience,UniversityofShanghaiforScienceandTechnology,Shanghai 200093,China)
Abstract: AccordingtoCooleyˉTukeydecimationintime,asetofequivalentiterationequationscanbeobtainedinregardtothediscreteFouriertransormofthesamplepointN=2.Elaborateanalysisoncharacteristicsofthedualnodepairsintheequationthereoutsimplifiesitscalculationalformula.Incomparisonwithdirectoperation,thismethodgreatlyreducesitsdegreeofoperation.Besides,nomoresettingsareneededonstoragecellsexceptthoseoccupiedbyNtimesinitialdatainthecalculationprocess.
Keywords: fastFouriertransform;discreteFouriertransform;dualnodepair;degreeofoperation
γ
傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛的应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换.
1 快速傅里叶变换算法
离散傅里叶正变换为 X(n)=∑x0(k)e
k=0N-1
次复数乘法及N-1次复数加法,要完成这组变
2
换共需N次复数乘法及N(N-1)次复数加法.但以下介绍的快速傅里叶变换的算法,可大大减少运算次数,提高工作效率.
γ
当N=2时,n和k可用二进制数表示为γ-1γ-2
n=2nnγ-1+2γ-2+…+n0=nγ-1nγ-2…n0・
k=2
γ-1
kγ-1+2
N
γ-2
kγ-2+…+k0=kγ-1kγ-2…k0・
又记W=[1]
N
n=0,1…,N-1(1)
,则式(1)可改写为
X(nγ-1nγ-2…n0・)=
P∑∑…∑x0(kγ-1kγ-2…k0・)W
kγ-1=0
111
由式(1)可知,对每一个n,计算X(n)须作N
收稿日期:2006-04-17
k0=0k1=0
(2
)
曹伟丽:快速傅里叶变换的原理与方法193
l
式中:P=nk=(2
(2W=W
WW
γ-1nk20γ-1
p
γ-1
nγ-1+2
γ-2
γ-2
nγ-2+…+n0)×
γ-1
kγ-1+2kγ-2+…+k0)
γ-1nγ-2nγ-1k(2γ-1+2γ-2+…+2n1+n0)2γ-1γ-1nγγ(2γ-1+2-2nγ-2+…+n0)2-2kγ-2γ-1nk0(2γ-1+…+n0)γ2
有k=i,与k=j=i+N/2.因此,用上一组的两个
数据计算所得的两个新数据仍可储存在原来位置,计算过程中只需要N个存储器.将xl(i)与xl
(i+N/2)称为第L个数组中的对偶结点对.计算
l
…
(3)
p
每个对偶结点对只需一次乘法,事实上由式(6)可得
xl(i)=xl-1(i)+xl-1i+xl(i+
因为W
W
W
=W
N
=[e
N
]
N
=1,所以
W=
γ-2k(2n1+n0)2γ-2
…W
γ-1n(2γ-1+…+n0)k0
式(2)可改写为
X(nγ-1nγ-2…n0・)∑∑…∑x0(kγ-1kγ-2…k0・)
k0=0k1=0
2
l
W
P1
111
W
γ-1nk20γ-1
W
γ-2k(2n1+n0)2γ-2
…W
kγ-1=0γ-1n(2γ-1+…+n0)k0
2
l
)=xl-1(i)l-1i-2γ-1
l
(8)
W
P2
2
l
(4)
:P12
γ-2γ-l
0;P2=2
γ-l
+2
γ-2
令
x1(n0kγ-2…k0・)=∑x0(kγ-1kγ-2…k)
kγ-1=0
n-2+1
P
0(7)中nl-1取0,1时对
P2=P1+2W有如下关系:
W
P2
=P1+N/2,于是对偶
W
γ-1nk20γ-1
x2(n0n1kγ-3…k0)∑0kγ-2…k0・)
k-2=0
=W
P1+2
=[N
]
P12
=-W1,因此式
P
P
(6)可表为
(5)
xl(i)=xl-1(i)+xl-1(i+xl(i+
γ-2k(2n1+n0)2γ-2
…
2
l
)W
xγ(n0n1…nγ-1・)=∑xγ-1(n0n1…nγ-2k0・)
k0=0
1
2
l
)=xl-1(i)+xl-1(i(9)
)W
P
2
l
γ-1γ-2
W
X(nγ-1nγ-2…n0・)=xγ(n0n1…nγ-1・)
γ-1n(2γ-2n+2
+…+n0)k0
P的求法:在xl(i)中,i写成二进制数n0n1…
则式(5)即为式(4)的分解形式.将初始数据x0(k)=x0(kγ-1kγ-2…k0・)代入式(5)的第一个等式,可得第一组计算数据,一般将第L-1组计算数据代入式(5)的第L个等式,计算后可得第L组计算数据(L=1,2,…,γ),计算公式也可表示为
x1(n0n1…nl-1kγ-1kγ-1=0
(2l-1n
l-1
…k0・,右移γ-l位,就成为00…0n0n1
…nl-1・,颠倒位序得:P=nl-1nl-2…n1n00…0・(l=1,2,…,γ).式(5)中,前面的γ个等式,每个
nl-1kγ-l-1
…k0・)=
等式均对应一组数据进行计算,每组数据都有N/2对结点,根据式(9),每对结点只需作1次乘法和2次加法,因此,每组数据只需N/2次乘法和N次加法,因而完成γ组数据的计算共需Nγ/2次乘法和Nγ次加法.
∑xl-1(n0n1…nl-2kγ-lkγ-l-1…k0・)
γ-2nγ-ln)k
l-1+2l-2+…+20γ-l
2 快速算法的计算机程序流程图
图1是快速傅里叶变换算法的计算机程序流
程图.
图中的i=IBR(k)为位序颠倒程序,设k=
n0n1…nl・,则i=n1nl-1…n0・.
W=
p
xl-1(n0n1…nl-20kγ-xl-1(n0n1…nl-21kγ-γ-1
l-1l-1
…k0・)+…k0・)W
(6)
γ-1
(7)式中 P=2nl-1+2nl-2+…+2n0
根据式(6),第L个数组中每个xl(k)=xl
(n0n1…nl-1kγ-l-1…k0・)的计算只依赖于上一数组的两个数据xl-1(i)=xl-1(n0n1…nl-20kγ-l-1…k0・)与xl-1(j)=xl-1(n0n1…nl-21kγ-l-1…k0
γ-2
3 计算实例
下面给出用离散傅里叶变换近似计算连续傅里叶变换的一个例子,并比较传统算法与快速算
法的运算次数.
-t
e,t>0
设f(t),求f(t)的傅里叶变换
0,t
)[f(t)].
・),这两个数据的标号相差2=N/2,即j=i
l
+n/2,而且这两个数据只用于计算第L个数组中标号为k=n0n1…nl-1k的数据(等号γ-l-1…k0・
右端为二进制数).当nl-1分别取0和1时,分别
γ-1
l
194上 海 电 力 学 院 学 报 2006年
图1 快速傅里叶变换算法的计算机程序流程图
解:取样本数为N=2=32,以时间间隔T=
0.25对f(t)抽样,则周期为NT=8,在间断点t=0处,样本点取中值0.5.
N-1-ktN
计算=T∑e,n=0,1,…,N-1.
k=0N5
将每对数据对应的复数均乘以T=0.25,即
-t
为连续傅里叶变换)[e]=F(ω)在ω=n/
(NT)处的值的近似值.
4 结 论
直接计算离散傅里叶变换共需作N次复数乘法及N(N-1)次复数加法,而用快速傅里叶变换,只需Nγ/2次乘法和N
γ次加法.直接算法和
+1
γ,加法次数之快速算法的乘法次数之比为2/
γ
比为(2-1)/γ.当γ增大时,比值明显增大,快
2
若用传统算法,共须作32×32=1024次复
数乘法,而用快速傅里叶变换的算法,只需作16×5=80次乘法.将32个样本点对应的原始数据输入快速傅里叶变换的程序,可得到输出的频率函数的32个样本值,由于离散傅里叶变换的频率函数以N=32为周期,又因为其实部与虚部分别为偶函数与奇函数,所以只需取前面的N/2=16个值.其实部与虚部见表1.
表1 快速傅里叶变换算法的频率函数
序号
12345678
γ
速算法效果更为明显.因此,与直接计算相比,用
快速傅里叶变换算法可大大减少运算次数,提高工作效率.参考文献:
实部
4.022.491.170.630.390.270.190.15
虚部
-0.00-1.93-1.78-1.39-1.09-0.87-0.71-0.59
序号
[**************]
实部
0.120.100.090.080.070.070.060.06
虚部
-0.48-0.40-0.33-0.26-0.20-0.15-0.10-0.05
[1] E.O.布赖姆.快速傅里叶变换[M].柳 群译.上海:上海
科学技术出版社,1979.
[2] H.J.努斯鲍默.快速傅里叶变换和卷积算法[M].胡光锐
译.上海:上海科学技术文献出版社,1984.
[3] 程佩青.数字信号处理教程.第2版[M].北京:清华大学出
版社,2001.
[4] 张易知.虚拟仪器的设计与实现[M].西安:西安电子科技
大学出版社,2002.
[5] 蒋正萍.数字信号处理[M].北京:电子工业出版社,2004.
第22卷第2期 2006年6月
上海电力学院学报
Vol.22,No.2June 2006
Journal of Shanghai University of Electric Power
文章编号:1006-4729(2006)02-0192-03
快速傅里叶变换的原理与方法
曹伟丽
(上海理工大学理学院,上海 )
摘 要:对样本点为N=2的离散傅里叶变换,,得到一组等价的迭代方程,,.与直接计算相比,大大减少了运算次数,,不需再设置其他存储单元.关键词:;对偶结点对;运算次数中图分类号:文献标识码:A
γ
PrincipleandMethodologyof
theFastFourierTransform
CAOWeiˉli
(InstituteofScience,UniversityofShanghaiforScienceandTechnology,Shanghai 200093,China)
Abstract: AccordingtoCooleyˉTukeydecimationintime,asetofequivalentiterationequationscanbeobtainedinregardtothediscreteFouriertransormofthesamplepointN=2.Elaborateanalysisoncharacteristicsofthedualnodepairsintheequationthereoutsimplifiesitscalculationalformula.Incomparisonwithdirectoperation,thismethodgreatlyreducesitsdegreeofoperation.Besides,nomoresettingsareneededonstoragecellsexceptthoseoccupiedbyNtimesinitialdatainthecalculationprocess.
Keywords: fastFouriertransform;discreteFouriertransform;dualnodepair;degreeofoperation
γ
傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛的应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换.
1 快速傅里叶变换算法
离散傅里叶正变换为 X(n)=∑x0(k)e
k=0N-1
次复数乘法及N-1次复数加法,要完成这组变
2
换共需N次复数乘法及N(N-1)次复数加法.但以下介绍的快速傅里叶变换的算法,可大大减少运算次数,提高工作效率.
γ
当N=2时,n和k可用二进制数表示为γ-1γ-2
n=2nnγ-1+2γ-2+…+n0=nγ-1nγ-2…n0・
k=2
γ-1
kγ-1+2
N
γ-2
kγ-2+…+k0=kγ-1kγ-2…k0・
又记W=[1]
N
n=0,1…,N-1(1)
,则式(1)可改写为
X(nγ-1nγ-2…n0・)=
P∑∑…∑x0(kγ-1kγ-2…k0・)W
kγ-1=0
111
由式(1)可知,对每一个n,计算X(n)须作N
收稿日期:2006-04-17
k0=0k1=0
(2
)
曹伟丽:快速傅里叶变换的原理与方法193
l
式中:P=nk=(2
(2W=W
WW
γ-1nk20γ-1
p
γ-1
nγ-1+2
γ-2
γ-2
nγ-2+…+n0)×
γ-1
kγ-1+2kγ-2+…+k0)
γ-1nγ-2nγ-1k(2γ-1+2γ-2+…+2n1+n0)2γ-1γ-1nγγ(2γ-1+2-2nγ-2+…+n0)2-2kγ-2γ-1nk0(2γ-1+…+n0)γ2
有k=i,与k=j=i+N/2.因此,用上一组的两个
数据计算所得的两个新数据仍可储存在原来位置,计算过程中只需要N个存储器.将xl(i)与xl
(i+N/2)称为第L个数组中的对偶结点对.计算
l
…
(3)
p
每个对偶结点对只需一次乘法,事实上由式(6)可得
xl(i)=xl-1(i)+xl-1i+xl(i+
因为W
W
W
=W
N
=[e
N
]
N
=1,所以
W=
γ-2k(2n1+n0)2γ-2
…W
γ-1n(2γ-1+…+n0)k0
式(2)可改写为
X(nγ-1nγ-2…n0・)∑∑…∑x0(kγ-1kγ-2…k0・)
k0=0k1=0
2
l
W
P1
111
W
γ-1nk20γ-1
W
γ-2k(2n1+n0)2γ-2
…W
kγ-1=0γ-1n(2γ-1+…+n0)k0
2
l
)=xl-1(i)l-1i-2γ-1
l
(8)
W
P2
2
l
(4)
:P12
γ-2γ-l
0;P2=2
γ-l
+2
γ-2
令
x1(n0kγ-2…k0・)=∑x0(kγ-1kγ-2…k)
kγ-1=0
n-2+1
P
0(7)中nl-1取0,1时对
P2=P1+2W有如下关系:
W
P2
=P1+N/2,于是对偶
W
γ-1nk20γ-1
x2(n0n1kγ-3…k0)∑0kγ-2…k0・)
k-2=0
=W
P1+2
=[N
]
P12
=-W1,因此式
P
P
(6)可表为
(5)
xl(i)=xl-1(i)+xl-1(i+xl(i+
γ-2k(2n1+n0)2γ-2
…
2
l
)W
xγ(n0n1…nγ-1・)=∑xγ-1(n0n1…nγ-2k0・)
k0=0
1
2
l
)=xl-1(i)+xl-1(i(9)
)W
P
2
l
γ-1γ-2
W
X(nγ-1nγ-2…n0・)=xγ(n0n1…nγ-1・)
γ-1n(2γ-2n+2
+…+n0)k0
P的求法:在xl(i)中,i写成二进制数n0n1…
则式(5)即为式(4)的分解形式.将初始数据x0(k)=x0(kγ-1kγ-2…k0・)代入式(5)的第一个等式,可得第一组计算数据,一般将第L-1组计算数据代入式(5)的第L个等式,计算后可得第L组计算数据(L=1,2,…,γ),计算公式也可表示为
x1(n0n1…nl-1kγ-1kγ-1=0
(2l-1n
l-1
…k0・,右移γ-l位,就成为00…0n0n1
…nl-1・,颠倒位序得:P=nl-1nl-2…n1n00…0・(l=1,2,…,γ).式(5)中,前面的γ个等式,每个
nl-1kγ-l-1
…k0・)=
等式均对应一组数据进行计算,每组数据都有N/2对结点,根据式(9),每对结点只需作1次乘法和2次加法,因此,每组数据只需N/2次乘法和N次加法,因而完成γ组数据的计算共需Nγ/2次乘法和Nγ次加法.
∑xl-1(n0n1…nl-2kγ-lkγ-l-1…k0・)
γ-2nγ-ln)k
l-1+2l-2+…+20γ-l
2 快速算法的计算机程序流程图
图1是快速傅里叶变换算法的计算机程序流
程图.
图中的i=IBR(k)为位序颠倒程序,设k=
n0n1…nl・,则i=n1nl-1…n0・.
W=
p
xl-1(n0n1…nl-20kγ-xl-1(n0n1…nl-21kγ-γ-1
l-1l-1
…k0・)+…k0・)W
(6)
γ-1
(7)式中 P=2nl-1+2nl-2+…+2n0
根据式(6),第L个数组中每个xl(k)=xl
(n0n1…nl-1kγ-l-1…k0・)的计算只依赖于上一数组的两个数据xl-1(i)=xl-1(n0n1…nl-20kγ-l-1…k0・)与xl-1(j)=xl-1(n0n1…nl-21kγ-l-1…k0
γ-2
3 计算实例
下面给出用离散傅里叶变换近似计算连续傅里叶变换的一个例子,并比较传统算法与快速算
法的运算次数.
-t
e,t>0
设f(t),求f(t)的傅里叶变换
0,t
)[f(t)].
・),这两个数据的标号相差2=N/2,即j=i
l
+n/2,而且这两个数据只用于计算第L个数组中标号为k=n0n1…nl-1k的数据(等号γ-l-1…k0・
右端为二进制数).当nl-1分别取0和1时,分别
γ-1
l
194上 海 电 力 学 院 学 报 2006年
图1 快速傅里叶变换算法的计算机程序流程图
解:取样本数为N=2=32,以时间间隔T=
0.25对f(t)抽样,则周期为NT=8,在间断点t=0处,样本点取中值0.5.
N-1-ktN
计算=T∑e,n=0,1,…,N-1.
k=0N5
将每对数据对应的复数均乘以T=0.25,即
-t
为连续傅里叶变换)[e]=F(ω)在ω=n/
(NT)处的值的近似值.
4 结 论
直接计算离散傅里叶变换共需作N次复数乘法及N(N-1)次复数加法,而用快速傅里叶变换,只需Nγ/2次乘法和N
γ次加法.直接算法和
+1
γ,加法次数之快速算法的乘法次数之比为2/
γ
比为(2-1)/γ.当γ增大时,比值明显增大,快
2
若用传统算法,共须作32×32=1024次复
数乘法,而用快速傅里叶变换的算法,只需作16×5=80次乘法.将32个样本点对应的原始数据输入快速傅里叶变换的程序,可得到输出的频率函数的32个样本值,由于离散傅里叶变换的频率函数以N=32为周期,又因为其实部与虚部分别为偶函数与奇函数,所以只需取前面的N/2=16个值.其实部与虚部见表1.
表1 快速傅里叶变换算法的频率函数
序号
12345678
γ
速算法效果更为明显.因此,与直接计算相比,用
快速傅里叶变换算法可大大减少运算次数,提高工作效率.参考文献:
实部
4.022.491.170.630.390.270.190.15
虚部
-0.00-1.93-1.78-1.39-1.09-0.87-0.71-0.59
序号
[**************]
实部
0.120.100.090.080.070.070.060.06
虚部
-0.48-0.40-0.33-0.26-0.20-0.15-0.10-0.05
[1] E.O.布赖姆.快速傅里叶变换[M].柳 群译.上海:上海
科学技术出版社,1979.
[2] H.J.努斯鲍默.快速傅里叶变换和卷积算法[M].胡光锐
译.上海:上海科学技术文献出版社,1984.
[3] 程佩青.数字信号处理教程.第2版[M].北京:清华大学出
版社,2001.
[4] 张易知.虚拟仪器的设计与实现[M].西安:西安电子科技
大学出版社,2002.
[5] 蒋正萍.数字信号处理[M].北京:电子工业出版社,2004.