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

快速傅立叶变换(FFT)算法实验 摘要：FFT（Fast Fourier Transformation），即为快速傅里叶变换，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。这种算法大大减少了变换中的运算量，使得其在数字信号处理中有了广泛的运用。本实验主要要求掌握在CCS环境下用窗函数法设计FFT快速傅里叶的原理和方法；并且熟悉FFT快速傅里叶特性；以及通过本次试验了解各种窗函数对快速傅里叶特性的影响等。 引言： 快速傅里叶变换FFT是离散傅里叶变换DFT的一种快速算法。起初DFT的计算在数字信号处理中就非常有用，但由于计算量太大，即使采用计算机也很难对问题进行实时处理，所以并没有得到真正的运用。1965年J.W.库利和T.W.图基提出快速傅里叶变换，采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。从此，对快速傅里叶变换（FFT）HYPERLINK /view/7420.htm \t _blank 算法的研究便不断深入，HYPERLINK /view/162096.htm \t _blank 数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT 的出现，使信号分析从时域分析向频域分析成为可能，极大地推动了信号分析在各领域的实际应用。FFT在离散傅里叶反变换、线性HYPERLINK /view/865418.htm \t _blank 卷积和HYPERLINK /view/1082682.htm \t _blank 线性相关等方面也有重要应用。 实验原理： 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^L，L为整数。将N=2^L的序列x(n)(n=0,1,……，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=2k,k为正整数），分为两个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抽样点序列的离散傅里叶变换求出。依此类推