快速傅里叶变换原理及其应用(快速入门)

电信06级数字信号处理课程期中论文1快速傅里叶变换的原理及其应用摘要快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换.虽然傅里叶运算在各方面计算中有着重要的作用，但是它的计算过于复杂，大量的计算对于系统的运算负担过于庞大，使得一些对于耗电量少，运算速度慢的系统对其敬而远之，然而，快速傅里叶变换的产生，使得傅里叶变换大为简化，在不牺牲耗电量的条件下提高了系统的运算速度，增强了系统的综合能力，提高了运算速度，因此快速傅里叶变换在生产和生活中都有着非常重要的作用，对于学习掌握都有着非常大的意义。关键词快速傅氏变换；快速算法；简化；广泛应用电信06级数字信号处理课程期中论文2AbstractFastFourierTransform(FFT),isadiscretefastFouriertransformalgorithm,whichisbasedontheDiscreteFourierTransformofoddandeven,false,false,andothercharacteristicsoftheDiscreteFourierTransformalgorithmsimprovementsobtained.ItsFouriertransformtheoryhasnotfoundanew,butinthecomputersystemortheapplicationofdigitalsystemsDiscreteFourierTransformcanbesaidtobeabigstepinto.Fouriertransformtheoryandmethodsinthemathematicalequationandlinearsystemsanalysisandsignalprocessing,simulation,andmanyotherareashaveawiderangeofapplications,asthecomputercanonlyhandlealimitedlengthofthesequenceofdiscrete,sotrueOnthecomputer'soperationisadiscreteFouriertransform.FourierAlthoughallaspectsofcomputinginthecalculationhasanimportantrole,butitscalculationwastoocomplicated,alotofcomputingsystemforcalculatingtheburdenistoolargeforsomeLesspowerconsumption,theslowspeedofoperationofitssystematarm'slength,however,havethefastFouriertransform,Fouriertransformgreatlysimplifyingthemaking,notinpowerattheexpenseoftheconditionstoincreasethespeedofcomputingsystems,andenhancethesystemThecomprehensiveabilitytoimprovethespeedofoperation,theFastFourierTransformintheproductionandlifehaveaveryimportantroleinlearningtomasterallhavegreatsignificance.KeywordsFastFourierTransform;fastalgorithm;simplified;widelyused电信06级数字信号处理课程期中论文3目录摘要………………………………………………………………………………１ABSTRACT………………………………………………………………………２绪论………………………………………………………………………………４快速傅里叶变换原理……………………………………………………………５快速傅里叶的实际应用…………………………………………………………７１快速傅里叶变换在喇曼光谱信号噪声平滑中的应用…………………７引言………………………………………………………………………７实验原理及结果…………………………………………………………８结论………………………………………………………………………９２采用异步实现的快速傅里叶变换处理器………………………………９引言……………………………………………………………………９实验原理及结果………………………………………………………１０结论……………………………………………………………………１０３快速傅里叶算法在哈特曼夏克传感器波前重构算法中的应用………１１引言……………………………………………………………………１１实验原理及结果………………………………………………………１１结论……………………………………………………………………１２参考文献…………………………………………………………………………１３电信06级数字信号处理课程期中论文4绪论傅立叶变换在生产生活中的重要性非常突出，它将原来难以处理的时域信号相对比较容易地转换成了易于分析的频域信号，可以利用一些工具对这些频域信号进行处理、加工，把信号转化为可以对其进行各种数学变化的数学公式，对其进行处理。最后还可以.利用傅立叶反变换将这些频域信号转换成时域信号，它是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。然尔，它在运算上过于复杂，过于宏大的运算过程，对于一些相对简单的低功耗处理器来说，难以自如应对，因此，快速傅里叶变换则显出了它的优越性。快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。对于计算机处理信号方面上是一大进步。系统的速度不但取决于本身的速度，而且还在相当大的程度上取决于算法，算法运算量的大小直接影响着对设备的控制质量。通过傅立叶变换（DFT），运用测试软件进行检测，可以看出快速傅里叶变换大大的提高了运算速度，它为各系统的设计提供了简单算法，有着十分重要的意义。电信06级数字信号处理课程期中论文5Ⅰ.快速傅里叶变换原理数字信号的傅里叶变换,通常采用离散傅里叶变换(DFT)方法。DFT存在的不足是计算量太大,很难进行实时处理。计算一个N点的DFT,一般需要2N次复数乘法和N(N-1)次复数加法运算.因此,当N较大或要求对信号进行实时处理时,往往难以实现所需的运算速度。1965年,J.W.Cooly和J.W.Tukey发现了DFT的一种快速算法,经其他学者进一步改进,很快形成了一套高效运算方法,这就是现在通用的快速傅里叶变换,简称FFT(TheFastFourierTransform)。快速傅里叶变换的实质是利用式(1)中的权函数nkNW的对称性和周期性,把N点DFT进行一系列分解和组合,使整个DFT的计算过程变成一系列叠代运算过程,使DFT的运算量大大简化,为DFT及数字信号的实时处理和应用创造了良好的条件。快速傅里叶变换算法如下：由(1)式可知，对每一个n，计算X(ｎ)须作N次复数乘法及N-1次复数加法，要完成这组变换共需次乘法及N(N-1)次复数加法。但以下介绍的快速傅里叶变换的算法，可大大减少运算次数，提高工作效率。当2rN时，n和k可用二进制数表示：1212012022rrrrrrnnnnnnn1212012022rrrrrrkkkkkkk又记NWe,则（1）式可改写为0011011112001200()()rprrrrkkkXnnnxkkkW（2）式中：1212120120(22)(22)rrrrrrrrPnkkkknnn12112212011202(22)2(22)2rrrrrrrrrrrrnnnknnnkP120120(22)rrrrKnnnW(3)因为22[]1rrNNWWe所以（2）可改成0011011112001200()()rrrrrkkkXnnnxkkk12112212120112020120(22)2(22)2(22)rrrrrrrrrrrrrrrrnnnknnnkKnnn（4）电信06级数字信号处理课程期中论文6201201300020()()rrrkxnnkkxnkk102(2)22rnnrkW(5)120011()()rrrrXnnnxnnn则式（５）即为式（４）的分解形式。将初始数据代入式（５）的第一个等式，可得每一组计算数据，一般将痗L-1组计算数据代入式（５）的第L个等式，计算后可得第L组计算数据（L＝１，２，…，γ），计算公式也可表示为10110200120()()rrrrkxnkkxkkk121200(22)rrrrnnnkW=10121201012120(0)(0)PlrrrlrrrxnnnkkkxnnnkkkW（6）式中121120222rrrllPnnn（7）根据式（６），第L个数组中每个120120()()llrrrrxkxnnnkkk的计算只依赖于上一个数组的两个数据这两个数据的标号相差12/2YlN，即/2ljin，而且这两个数据只用于计算第L个数组中标号的数据（等号右端为二进制数）。当1ln分别取０和１时，分别有,/2lkikjin。因此，用上一组的两个数据计算所得的两个新数据仍可储存在原来位置，计算过程中只需要N个存储器。将()lxi与(/2)llxin称为第L个数组中的对偶结点对。计算每个对偶结点对只需一次乘法，事实上由式（６）可得11()()[]2plllNxixiiW211()()[]22plllllNNxixixiW式中：lrlrnP2...22210n；02222...22nnPlrlrlr别为式（７）中1ln取０，１时对应的P值。因2/21112NPPPR，于是对偶结点的pW有如下关系：111222][PNPNNPPWeWW,因此式（６）可表示为1111()()[]2()()[]22pllllplllllNxixixiWNNxixixiWP的求法：在)(ixl中，i写成二进制数01110......kknnnlrl右移lr位，就成为110...0...0lnnn颠倒位序得),...,2,1(0...0...011rlnnnpl式（５）吕，前面的γ个等式，每个电信06级数字信号处理课程期中论文7等式均对应一组数据进行计算，每组数据都有N/２对结点，根据式（９），每对结点只需作１次乘法和２次加法，因此，每组数据只需N/2次乘法和N次加法，因而完成γ组数据的计算共需Nγ/2次乘法和Nγ次加法。Ⅱ.快速傅里叶的实际应用:一．快速傅里叶变换在喇曼光谱信号噪声平滑中的应用１．引言电探测系统是光信号的转换、传输及处理的系统.系统的各个部分在工作时总会受到一些无用信号的干扰,给光谱峰的检