资源描述：
《详解fft(快速傅里叶变换fft》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第四章快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT).1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基２DIT和基２DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅里叶变换（FFT）是计算离
2、散傅里叶变换（DFT）的快速算法。DFT的定义式为knN−1X(k)=∑x(n)WNRN(k)n=0N在所有复指数值Wkn的值全部已算好的情况下，要计算一个X(k)需要N次复数乘法和N－1次复数加法。算出全部N点X(k)共需N2次复数乘法和N(N−1)次复数加法。即计算量是与N2成正比的。FFT的基本思想：将大点数的DFT分解为若干个小点数DFT的组合，从而减少运算量。WN因子具有以下两个特性，可使DFT运算量尽量分解为小点数的DFT运算：W（1）周期性：(k+N)nNN=WknN=W(n+N)k（2）对称性：W(k+N/2)=−WkNN利用这两个性质，可以使DF
3、T运算中有些项合并，以减少乘法次数。例子：求当N＝4时，X(2)的值3∑44444X(2)=n=0x(n)W2n=x(0)W0+x(1)W2+x(2)W4+x(3)W6=[x(0)+x(2)]W0+[x(1)+x(3)]W2(周期性)44＝[x(0)+x(2)]－[x(1)+x(3)]W04(对称性)通过合并，使乘法次数由4次减少到1次，运算量减少。FFT的算法形式有很多种，但基本上可以分为两大类：按时间抽取（DIT）和按频率抽取（DIF）。4.1按时间抽取（DIT）的FTT为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是N=2M
4、的情况（M为正整数）。该情况下的变换称为基2FFT。下面讨论基2情况的算法。先将序列x(n)按奇偶项分解为两组⎧x(2r)=x1(r)⎨⎩x(2r+1)=x2(r)将DFT运算也相应分为两组Nr=0,1,L,2−1N−1NX(k)=DFT[x(n)]=∑x(n)Wknn=0N−1N=∑x(n)Wkn＋N−1N∑x(n)Wknn=0n为偶数n=0n为奇数N/2−1∑(2)2rk+N/2−1∑(2+1)(2r+1)k＝xr=0rWNxrWNr=0N/2−1∑2rk+N/2−1k∑2rk＝r=0x1(r)WNWNkr=0x2(r)WNrkN/2−1
5、＝∑x1(r)Wr=0N/2+WNN/2−1∑x2(r)Wr=0rkN/2（因为W2rkN）rk=WN/2k=X1(k)+WNX2(k)其中X1(k)、X2(k)分别是x1(n)、x2(n)的N/2点的DFTN/2−1N/2−1NrkrkX1(k)＝∑x1(r)WN/2=∑x(2r)WN/2,0≤k≤−1r=0r=02N/2−1N/2−1rkrkNX2(k)＝∑x2(r)WN/2=∑x(2r+1)WN/2,0≤k≤−1r=0r=02至此，一个N点DFT被分解为两个N/2点的DFT。上面是否将全部N点的X(k)求解出来了？分析：X1(k)和NX2(k
6、)只有N/2个点（k=0,1,L,2−1），则由1N2X(k)=X(k)+WkX(k)只能求出X(k)的前N/2个点的DFT，要求出全部N点的X(k)，需要找出X1(k)、X2(k)和X(k+N/2)的关系，其N中k=0,1,L,2−1。由式子X(k)=X1N(k)+WkX2(k)可得1NX(k+N/2)=X(k+N/2)+Wk+N/2kX2(k+N/2)化简得NX(k+N/2)＝=X1(k)−WNX2(k)，k=0,1,L,2−1这样N点DFT可全部由下式确定出来：1N2⎧⎪X(k)=X(k)+WkX(k)1N2⎩⎪⎨X(k+N/2)=X(k)−WkX(k)k
7、=0,1,L,N−12（＊）上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运算。Naa+WkbWNkba−Wkb-1N图蝶形运算符号2通过这样的分解以后，每一个N／2点的DFT只需要(N)2=N次复数乘242法，两个N/2点的DFT需要2(N)2=N次复乘，再加上将两个N／2点22DFT合并成为N点DFT时有N／2次与W因子相乘，一共需要2N+N22N2≈次复乘。可见，通过这样的分解，运算量节省了近一半。2因为N=2M，N/2仍然是偶数，因此可以对两个N/2点的DFT再分别作进一步的分解，将两个N/
