《详解FFT快速傅里叶变换FFT》由会员分享，可在线阅读，更多相关《详解FFT快速傅里叶变换FFT（26页珍藏版）》请在金锄头文库上搜索。
1、第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换 (DFT) 将其频域也离散化成有限长 序列 . 但其计算量太大 , 很难实时地处理问题 ,因此引出了快速傅里叶变换 (FFT). 1965 年， Cooley 和 Tukey 提出了计算离散傅里叶变换( DFT )的快 速算法，将 DFT 的运算量减少了几个数量级。 从此，对快速傅里叶变换 ( FFT) 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基2 DIT和基2 DIF。 FFT在离散傅里叶反变换、线性卷积 和线性相关等方
2、面也有重要应用。快速傅里叶变换(FFT )是计算离散傅里叶变换(DFT )的快速算法。DFT 的定义式为N- 1knX (k )=刀 x(n)Wj rn (k)n=0kn在所有复指数值 WNkn 的值全部已算好的情况下，要计算一个X (k ) 需要 N2 次复数乘法和 N1 次复数加法。算出全部N 点 X (k ) 共需 N 2 次复数乘法2和 N ( N - 1) 次复数加法。即计算量是与 N 2 成正比的。FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。WN 因子具有以下两个特性， 可使 DFT 运算量尽量分解为小点数的 DFT运算：=W kn
3、 =W (n+N )k( 1)周期性： W (k+N )n N NN(k+N / 2)k(2)对称性： W (k+N / 2) = - W kNN利用这两个性质， 可以使 DFT 运算中有些项合并， 以减少乘法次数。 例子： 求当N = 4时，X(2)的值/ 丿44444X (2) =x(n)W 2n = x(O)W 0 + x(1W 2 + x(2)W 4 + x(3)W 6n=00 2= x(0) +x(2) W0 +x(1) + x(3)W2(周期性)44=x(0) + x(2)-x(1) + x(3)W：(对称性)通过合并，使乘法次数由4次减少到1次，运算量减少。FFT的算法形式有很多
4、种，但基本上可以分为两大类：按时间抽取(DIT )和按频率抽取(DIF)。4.1按时间抽取(DIT )的FTT为了将大点数的 DFT分解为小点数的 DFT运算，要求序列的长度N为复合数，最常用的是N = 2 M的情况(M为正整数)。该情况下的变换称为基2FFT。下面讨论基2情况的算法。先将序列x(n)按奇偶项分解为两组?x(2r ) = Xi (r )?N?x(2r +1) = X2 (r )r = 0,1L，；- 1将DFT运算也相应分为两组N - 1X (k ) = DFT x(n) = / x(n)WN knn=0N- 1N- 1+1)(2r+1)kr=0r Wn(2xr=0rWn2rk
5、N / 2-12rk=/ x(n)Wkn/ x(n)W kn+n=0n=0n为偶数n为奇数N / 2- 12rkN / 2- 1x1 (r)WNWNx2 (r)WNr=0r=0N / 2- 1=X x1k N / 2- 1 Nrk/ 2 +WNX x2Nk/ 2 (因为 WNrk =wNk/ 2)(r)W(r)Wr=0r=0= X 1 (k ) +WNkX 2 (k )其中 Xi (k)、X 2 (k)分别是 Xi (n)、X2 (n)的 N/2 点的 dftN / 2-1N / 2- 1rkrkXi (k ) = E Xi (r)WN / 2 = E x(2r)WN / 2 ,0 k - 1
6、r=0r=0N / 2-1N / 2- 1rkrkX 2 (k)二 E X2 (r)WN / 2 = E x(2r +1)Wn / 2 ,0 froGOGGGDO (01(B)(51(7) xfTJrsrsrxfRxf2D点FT2 n占 FT2 n占 FT2 R富證k-B:1J 1J- u 1J0 4 2 6J u口 e卩*X X X Xr 亠 r - ” , ”n ”n” XXXXXXXX这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数 还是奇数来抽取的，故称为“时间抽取法”。分析上面的流图， N = 2 M，一共要进行 M次分解，构成了从 x(n)到X(k)的M级运算过程。每
7、一级运算都是由N/2个蝶形运算构成，因此每级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共需复数乘法次数:mF = N ? = N log NW 222复数加法次数:aF= N ?M=N log2 N根据上面的流图，分析FFT算法的两个特点，它们对FFT的软硬件构成产生很大的影响。(1) 原位运算 也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储 在原来的存储器中， 直到最后输出，中间无需其它的存 储器。根据运算流图 分析原位运算是如何进行的。 原位运算的结构可以节 省存储单元，降低设备成本。(2) 变址 分析运算流图中的输入输出序列的顺序，输出按顺序，输入是
8、“码位倒置”的顺序。见图。01234567X(0) X(4) X(2)X(6)X(1) X(5)X(3)X(7)码位倒置的变址处理自然顺序进制表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110011371111117码位倒置顺序在实际运算中，直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行 FFT 的原位运算。变质 的功能如图所示。用软件实现是通用采用雷德(Rader)算法，算出I的倒序J以后立即将输入数据
9、X(l)和X(J)对换。尽管变址运算所占运算量的比例很小，但对某些高要求的应用(尤其在实时信号处理中)，也可设法用适当的电路结构直接实现变址。 例如单片数字信号处理器 TMS320C25 就有专用 于 FFT 的二进制码变址模式。4. 2按频率抽取(DIF )的FTT除时间抽取法外，另外一种普遍使用的 FFT 结构是频率抽取法。频率抽取法将输入序列不是按奇、偶分组，而是将N点 DFT写成前后两部分：N - 1X (k ) = DFT x(n)=刀 x(n)W n=0N -1( N / 2)- 1n=0刀 x(n)W kn + E x(n)W knn=N / 2N / 2- 1nkN / 2- 1(n+N / 2)k+ / 2)x n WNn=0x n
