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

电信06级数字信号处理课程期中论文1快速傅里叶变换的原理及其应用摘要快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。傅里叶变换的理论与方法在“数理方程”、“线性系统分析”、“信号处理、仿真”等很多学科领域都有着广泛应用,由于计算机只能处理有限长度的离散的序列,所以真正在计算机上运算的是一种离散傅里叶变换.虽然傅里叶运算在各方面计算中有着重要的作用，但是它的计算过于复杂，大量的计算对于系统的运算负担过于庞大，使得一些对于耗电量少，运算速度慢的系统对其敬而远之，然而，快速傅里叶变换的产生，使得傅里叶变换大为简化，在不牺牲耗电量的条件下提高了系统的运算速度，增强了系统的综合能力，提高了运算速度，因此快速傅里叶变换在生产和生活中都有着非常重要的作用，对于学习掌握都有着非常大的意义。关键词快速傅氏变换；快速算法；简化；广泛应用电信06级数字信号处理课程期中论文2目录摘要………………………………………………………………………………１ABSTRACT………………………………………………………………………２绪论………………………………………………………………………………４快速傅里叶变换原理……………………………………………………………５快速傅里叶的实际应用…………………………………………………………７１快速傅里叶变换在喇曼光谱信号噪声平滑中的应用…………………７引言………………………………………………………………………７实验原理及结果…………………………………………………………８结论………………………………………………………………………９２采用异步实现的快速傅里叶变换处理器………………………………９引言……………………………………………………………………９实验原理及结果………………………………………………………１０结论……………………………………………………………………１０３快速傅里叶算法在哈特曼夏克传感器波前重构算法中的应用………１１引言……………………………………………………………………１１实验原理及结果………………………………………………………１１结论……………………………………………………………………１２参考文献…………………………………………………………………………１３电信06级数字信号处理课程期中论文3绪论傅立叶变换在生产生活中的重要性非常突出，它将原来难以处理的时域信号相对比较容易地转换成了易于分析的频域信号，可以利用一些工具对这些频域信号进行处理、加工，把信号转化为可以对其进行各种数学变化的数学公式，对其进行处理。最后还可以.利用傅立叶反变换将这些频域信号转换成时域信号，它是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。然尔，它在运算上过于复杂，过于宏大的运算过程，对于一些相对简单的低功耗处理器来说，难以自如应对，因此，快速傅里叶变换则显出了它的优越性。快速傅氏变换（FFT），是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。对于计算机处理信号方面上是一大进步。系统的速度不但取决于本身的电信06级数字信号处理课程期中论文4速度，而且还在相当大的程度上取决于算法，算法运算量的大小直接影响着对设备的控制质量。通过傅立叶变换（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电信06级数字信号处理课程期中论文6120120(22)rrrrKnnnW(3)因为22[]1rrNNWWe所以（2）可改成0011011112001200()()rrrrrkkkXnnnxkkk12112212120112020120(22)2(22)2(22)rrrrrrrrrrrrrrrrnnnknnnkKnnn（4）201201300020()()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取０，电信06级数字信号处理课程期中论文7１时对应的P值。因2/21112NPPPR，于是对偶结点的pW有如下关系：111222][PNPNNPPWeWW,因此式（６）可表示为1111()()[]2()()[]22pllllplllllNxixixiWNNxixixiWP的求法：在)(ixl中，i写成二进制数01110......kknnnlrl右移lr位，就成为110...0...0lnnn颠倒位序得),...,2,1(0...0...011rlnnnpl式（５）吕，前面的γ个等式，每个等式均对应一组数据进行计算，每组数据都有N/２对结点，根据式（９），每对结点只需作１次乘法和２次加法，因此，每组数据只需N/2次乘法和N次加法，因而完成γ组数据的计算共需Nγ/2次乘法和Nγ次加法。Ⅱ.快速傅里叶的实际应用:一．快速傅里叶变换在喇曼光谱信号噪声平滑中的应用１．引言电探测系统是光信号的转换、传输及处理的系统.系统的各个部分在工作时总会受到一些无用信号的干扰,给光谱峰的检测判别及进一步的数据处理带来了不利因素.对光谱电信06级数字信号处理课程期中论文8信号进行数字滤波,以获得更真实的光谱信息，显得格外重要.目前最为通用和有效的信号滤波处理方法是快速傅立叶变换方法.纯水是一种较弱的喇曼散射介质,需要专用的喇曼散射光谱仪器才能获得高信噪比的喇曼光谱.我们以增强型的CCD探头为探测器,结合普通的分光单色仪,在YAG激光器532nm激光线的激励下获得低信噪比的纯水的喇曼光谱.信噪比较差的喇曼光谱经过FFT变换后,,用FFT的逆变换将滤除噪声后的频谱信号转换成为光谱信号,最终获得信噪比较高的纯水的喇曼光谱.２．实验原理及结果傅里叶变换的基本表达式为)1...1,0(,)()(10NkWnxkxNnnkN（１）]2exp[NknWnkN（２）式（1）中的x（n）(n=0,2,…N-1)是列长为N的输入序列，即实验采集到的时域上的切片数据;x(k)(=0,1,…N-1)是列长为N的输出序列，即经过傅里叶变换后的频域上的数据。对数字化后的光谱信号而言,x(n)是一组离散的实数信号；而X(k)分为实部x(v)和虚部y(ν)2部分。x(ν)和y(ν)又可组成振幅谱A(ν)和相位谱P(ν)：)()()(22vyvxVA（３）)()(arctan)(vxvyvp（４）通过对式(3)和式(4)性能的考察,发现A(ν)和P(ν)中既含有目标信号的信息,也含有噪声的信息,如果二者所在的区域不同,则可以通过傅里叶变换分析出噪声信息,将之从捕获的信号中去除,从而达到噪声平滑的目的,获得高信噪比的目标信号.纯水普通喇曼散射的信号很弱,我们在532nm脉冲激光泵浦液滴的条件下获得其散射光谱.由于样品信号极其微弱,在将CCD的增益调至最大时,获得如图1所示的纯水的喇曼光谱.光谱的信噪比值用如下方式估算:设(n)x为含噪声图像(n)y为消除噪声后的图像,图像的均方根误差为电信06级数字信号处理课程期中论文921(n)-y(n))NNnx(5)信噪比定义为除噪声后的信号与均方根误差之比1[(]/NNYNSNR(6)计算出642.86～643.62nm光谱区的信噪比为SNR≈17.图１多通道光谱分析仪采集的含有噪声的纯水普通喇曼散射信号电信06级数字信号处理课程期中论文10图2傅里叶变换后的频谱图对图2幅度谱纵轴取对数得图噪声幅度门限值低于2×105,经门限滤波处理,在频谱图中将幅度谱低于该门限值的频率成分去除,获得的频谱用FFT的逆变换返回得到门限滤波曲线如图5所示.计算出642.86～643.62nm光谱区的信噪比为SNR≈484.与图1相比,光谱的信噪比有了极大的改善.3结论在光谱信号受到光子噪声调制的条件下,如果光谱信号的变化频率低于高频光子噪声的变化频率,则可以通过快速傅里叶变换,获得目标信号和噪声信号的频谱,进行低通滤波和门限滤波后,分别将具有高频和不同振幅的噪声信号去除,实现对弱光谱信号干扰噪声