资源描述：
《快速傅里叶变换的原理与方法_曹伟丽》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第22卷第2期上海电力学院学报Vo.l22,No.22006年6月JournalofShanghaiUniversityofElectricPowerJune2006文章编号:1006-4729(2006)02-0192-03快速傅里叶变换的原理与方法曹伟丽(上海理工大学理学院,上海200093)摘要:对样本点为N=2的离散傅里叶变换,按照库利图基按时间抽取的方法,得到一组等价的迭代方程,对方程中对偶结点对的性质作了详细分析,由此简化了方程中的计算公式.与直接计算相比,大大减少了运算次数,并且计算过程中除了N个初始数据所占的存储单
2、元外,不需再设置其他存储单元.关键词:快速傅里叶变换;离散傅里叶变换;对偶结点对;运算次数中图分类号:O241文献标识码:APrincipleandMethodologyoftheFastFourierTransformCAOWeili(InstituteofScience,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)Abstract:AccordingtoCooleyTukeydecimationintime,asetofequivalentiteration
3、equationscanbeobtainedinregardtothediscreteFouriertransormofthesamplepointN=2.Elaborateanalysisoncharacteristicsofthedualnodepairsintheequationthereoutsimplifiesitscalculationalformula.Incomparisonwithdirectoperation,thismethodgreatlyreducesitsdegreeofoperation.Besides,nomoresettin
4、gsareneededonstoragecellsexceptthoseoccupiedbyNtimesinitialdatainthecalculationprocess.Keywords:fastFouriertransform;discreteFouriertransform;dualnodepair;degreeofoperation傅里叶变换的理论与方法在数理方程、次复数乘法及N-1次复数加法,要完成这组变2线性系统分析、信号处理、仿真等很多学科换共需N次复数乘法及N(N-1)次复数加法.领域都有着广泛的应用,由于计算机只能处理有但
5、以下介绍的快速傅里叶变换的算法,可大大减限长度的离散的序列,所以真正在计算机上运算少运算次数,提高工作效率.的是一种离散傅里叶变换.当N=2时,n和k可用二进制数表示为-1-2n=2n-1+2n-2++n0=n-1n-2n01快速傅里叶变换算法-1-2k=2k-1+2k-2++k0=k-1k-2k0-j2离散傅里叶正变换为又记W=eN,则式(1)可改写为N-1-j2nkX(n-1n-2n0)=[1]X(n)=xNn=0,1,N-1(1)0(k)e111k=0Px0(k-1k-2k0)W
6、(2)由式(1)可知,对每一个n,计算X(n)须作Nk0=0k1=0k-1=0收稿日期:2006-04-17曹伟丽:快速傅里叶变换的原理与方法193-1-2l式中:P=nk=(2n-1+2n-2++n0)有k=i,与k=j=i+N/2.因此,用上一组的两个-1-2(2k-1+2k-2++k0)数据计算所得的两个新数据仍可储存在原来位Wp=W(2-1n-1+2-2n-2++2n1+n0)2-1k-1置,计算过程中只需要N个存储器.将xl(i)与xl(2-1n+2-2n++n)2
7、-2klW-1-20-2(i+N/2)称为第L个数组中的对偶结点对.计算Wk0(2-1n-1++n0)(3)每个对偶结点对只需一次乘法,事实上由式(6)2N-j2Np可得因为W=W=[eN]=1,所以W=2-1n0k-1(2n1+n0)2-2k-2(2-1n-1++n0)k0NPWWWx1l(i)=xl-1(i)+xl-1i+lW2式(2)可改写为(8)111NNP2xl(i+l)=xl-1(i)+xl-1i+lWX(n-1n-2n0)k=0k=0k=0x0(k-1k-2k0)2201-1-2
8、-l-l-22-1nk(2n+n
