快速傅立叶变换(FFT)算法-DSP实验.docx

快速傅立叶变换(FFT)算法实验摘要：FFT（FastFourierTransformation）即为快速傅里叶变换是离散傅里叶变换的快速算法它是根据离散傅里叶变换的奇、偶、虚、实等特性对离散傅立叶变换的算法进行改进获得的。这种算法大大减少了变换中的运算量使得其在数字信号处理中有了广泛的运用。本实验主要要求掌握在CCS环境下用窗函数法设计FFT快速傅里叶的原理和方法；并且熟悉FFT快速傅里叶特性；以及通过本次试验了解各种窗函数对快速傅里叶特性的影响等。引言：快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法。起初DFT的计算在数字信号处理中就非常有用但由于计算量太大即使采用计算机也很难对问题进行实时处理所以并没有得到真正的运用。1965年J.W.库利和T.W.图基提出快速傅里叶变换采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少特别是被变换的抽样点数N越多FFT算法计算量的节省就越显著。从此对快速傅里叶变换（FFT）算法的研究便不断深入数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法基本算法是基2DIT和基2DIF。FFT的出现使信号分析从时域分析向频域分析成为可能极大地推动了信号分析在各领域的实际应用。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。实验原理：FFT并不是一种新的变换它是离散傅立叶变换（DFT）的一种快速算法。由于我们在计算DFT时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。每运算一个X（k）需要4N次复数乘法及2N+2（N-1）=2（2N-1）次实数加法。所以整个DFT运算总共需要4N^2次实数乘法和N*2(2N-1)=2N(2N-1)次实数加法。如此一来计算时乘法次数和加法次数都是和N^2成正比的当N很大时运算量是可观的因而需要改进对DFT的算法减少运算速度。根据傅立叶变换的对称性和周期性我们可以将DFT运算中有些项合并。我们先设序列长度为N=2^LL为整数。将N=2^L的序列x(n)(n=01……N-1)按N的奇偶分成两组也就是说我们将一个N点的DFT分解成两个N/2点的DFT他们又从新组合成一个如下式所表达的N点DFT：其中设x(n）为N项的复数序列由DFT变换任一X（m）的计算都需要N次复数乘法和N-1次复数加法而一次复数乘法等于四次实数乘法和两次实数加法一次复数加法等于两次实数加法即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法）那么求出N项复数序列的X（m）即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候需要N2=1048576次运算在FFT中利用WN的周期性和对称性把一个N项序列（设N=2kk为正整数）分为两个N/2项的子序列每个N/2点DFT变换需要（N/2）^2次运算再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后总的运算次数就变成N+2*(N/2）^2=N+N^2/2。继续上面的例子N=1024时总的运算次数就变成了525312次节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去直到分成两两一组的DFT运算单元那么N点的DFT变换就只需要Nlog2N次的运算N在1024点时运算量仅有10240次是先前的直接算法的1%点数越多运算量的节约就越大这就是FFT的优越性。8点DFT的FFT运算流图计算离散傅里叶变换的快速方法有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是的周期性；另一是的对称性这里符号*代表其共轭。这样便可以把离散傅里叶变换的计算分成若干步进行计算效率大为提高。时间抽取算法令信号序列的长度为N=2其中M是正整数可以将时域信号序列x(n)分解成两部分一是偶数部分x（2n）另一是奇数部分x（2n+1）其中。于是信号序列x(n）的离散傅里叶变换可以用两个N/2抽样点的离散傅里叶变换来表示和计算。一个抽样点数为N的信号序列x(n）的离散傅里叶变换可以由两个N/2抽样点序列的离散傅里叶变换求出。依此类推这种按时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅里叶变换计算最后合成为N点的离散傅里叶变换。①N=2点的离散傅里叶变换的计算全由蝶形运算组成需要M级运算每级包括N/2个蝶形运算总共有个蝶形运算。所以总的计算量为次复数乘法运算和Nlog2N次复数加法运算。②FFT算法按级迭代进行N抽样点的输入信号具有N个原始数据x0(n）经第一级运算后得出新的N个数据x1(n）再经过第二级迭代运算又得到另外N个数据x2(n）依此类推直至最后的结果