详解FFT(快速傅里叶变换FFT.docx

第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换 (FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换(DFT)的快 速算法，将DFT的运算量减少了几个数量级从此，对快速傅里叶变换(FFT) 算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发 展而迅速发展根据对序列分解与选取方法的不同而产生了 FFT的多种算 法，基本算法是基2DIT和基2DIFFFT在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用快速傅里叶变换(FFT )是计算离散傅里叶变换(DFT )的快速算法DFT的定义式为N-1X (k)=乏x(n)WknRN (k)n =0在所有复指数值Wkn的值全部已算好的情况下，要计算一个X ( k )需要N 次复数乘法和N - 1次复数加法算出全部N点X (k)共需N 2次复数乘法 和N(N - 1)次复数加法即计算量是与N 2成正比的FFT的基本思想：将大点数的DFT分解为若干个小点数DFT的组合, 从而减少运算量W因子具有以下两个特性可使DFT运算量尽量分解为小点数的DFT 运算： (1)周期性：W")= Wkn = W (n+村)k(k+ N )nN“ (k+ n )n n n(2)对称性：W (k+ N /2)=-WkN N利用这两个性质，可以使DFT运算中有些项合并，以减少乘法次数。

例子:求当N = 4时，X(2)的值w4 4 4 4 4X (2)= X(n)W 2n = X(0)W0 + x(1)W2 + x (2)W4 + x(3)W6n=0=[x(0) + x⑵]W0 + [x⑴+x⑶]W2 倜期性)44=[x(0) + x(2)] - [x⑴+x⑶]W0 (对称性)4通过合并，使乘法次数由4次减少到1次，运算量减少FFT的算法形式有很多种，但基本上可以分为两大类：按时间抽取(DIT )和按频率抽取(DIF )4.1按时间抽取(DIT )的FTT为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为 复合数，最常用的是N=2 m的情况(M为正整数)该情况下的变换称为 基2FFT下面讨论基2情况的算法先将序列x(n)按奇偶项分解为两组Q (2r)= x. (r)lx (2r +1) = x (r) 将DFT运算也相应分为两组X (k)= DFT [ x (n)]二W-1 x (n)Wknn =0N-1=W x (n )版切N-1W x (n)V|N knn = 0n为奇数+ 1) (2 r +1)kn =0n为偶数(2x r W x r WNNr =0r=0N，W 12rk + N 寸1k ^― 2rkx (r)Wr=0W^ x 2 (r )Wr=0N y 1=Z x1(r )W+ WkNN y 1Z x2(r )Wrk (因为 W 2 rk = WrkN / 2 N N / 2r=0r=0=X i(k) + WkX 2(k)其中 X (k)、X (k)分别是 x (n)、x 2(n)的 N/2 点的 DFTN /2- 1X 1(k) = z x 1r=0rk(r )WN / 2N / 2- 1rk=Z x(2r)Wn/ 2,0

上面是否将全部N点的X (k)求解出来了？分析：X (k)和1 X2(k)只有 N/2 个点(k =0,1,L ,22N - 1 )，则由X(k) = X (k) + WkX (k)只能求出X(k)的前N/2个点的DFT，要求出1 N 2全部N点的X (k)，需要找出X 1(k)、X2(k)和X (k + N / 2)的关系，其N中k =0,1L，一- 1由式子 X(k) = X21X(k + N / 2) = X (k + N / 2) + Wk+n/ 21N(k)+WkX (k)可得N2X2(k + N / 2)化简得kX (k + N / 2)==X 1(k) - WnX 2( k) 这样N点DFT可全部由下式确定出来：,k = 0,1LIX(k) = X (k) + WkX (k)1 N 2[x (k + N / 2) = X 1(k) - MN，X (k)上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运 算k = 0,1LN-1 (*)2ba--1WkNa + WkbWkbN图蝶形运算符号通过这样的分解以后，每一个N/2点的DFT只需要（史）2 =七 次复数乘2 4法，两个N/2点的DFT需要2(N )2 =生次复乘，再加上将两个N/2点22DFT合并成为N点DFT时有N / 2次与W因子相乘，一共需要N2 N N2 + —2 2 = 次复乘。

可见，通过这样的分解，运算量节省了近一半2因为N = 2m , N/2仍然是偶数，因此可以对两个N/2点的DFT再 分别作进一步的分解，将两个N/2点的DFT分解成两个N/4点的DFT1x1 (2l )= x 3 (l)Nl = 0,1L，— - 14例如对x1(,),可以在按其偶数部分及奇数部分进行分解:X (2l +1) = x (l) 则的运算可相应分为两组: 的DFT运算，其按时间抽取的分解过程及完整流图如下图所示N^-1X1(k) = Z X 1(2l )Wl=0UkN / 2NM (21 +1)k+ Z X. (2l + N / 21)w l=0N^- 13xik/ 4kN/ 2wN!^ 14xl=0()Nk/4l w1=0k=X 3( k) + WN/2 X 4k = 0，1L， — 14将系数统一为以N为周期，即Wk = w2k，可得N/ 2 N(k)X (k) = X (k) + W2kX 4(k)2kXI (k + N / 4) = X3(k) - w^ X4 (k)k = 0,1L N_ 1,同样’对X 2(k)也可进行类似的分解一直分解下去，最后是2点的DFT , 2点DFT的运算也可用碟形符号来表示。

这样，对于一个N = 23 = 8的7]°X(1) 次】 冲】 □ X(4] oX(5]0X(6]冲】这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数 还是奇数来抽取的，故称为"时间抽取法"分析上面的流图，N=2m，一共要进行M次分解，构成了从x(n)到X(k)的M级运算过程每一级运算都是由N/2个蝶形运算构成，因此每一 级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共需 要-M2复数乘法次数：气 二N .二N log N复数加法次数：i=N • M=N [o% N根据上面的流图，分析FFT算法的两个特点，它们对FFT的软硬件 构成产生很大的影响1) 原位运算也称为同址运算，当数据输入到存储器中以后，每一级运 算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存 储器根据运算流图分析原位运算是如何进行的原位运算的结构可以节 省存储单元，降低设备成本2) 变址分析运算流图中的输入输出序列的顺序，输出按顺序，输入是 "码位倒置"的顺序X(0)X(4)X(2) X(6) X(1)X(5) X(3) X(7)码位倒置的变址处理自然顺序一进制表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110011371111117码位倒置顺序0123 4567在实际运算中，直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行FFT的原位运算。

变质 的功能如图所示用软件实现是通用采用雷德(Rader)算法，算出I的倒 序J以后立即将输入数据X(I)和X(J)对换尽管变址运算所占运算量的比例 很小，但对某些高要求的应用(尤其在实时信号处理中)，也可设法用适当 的电路结构直接实现变址例如单片数字信号处理器TMS320C25就有专用 于FFT的二进制码变址模式4.2按频率抽取(DIF )的FTT除时间抽取法外，另外一种普遍使用的FFT结构是频率抽取法频率 抽取法将输入序列不是按奇、偶分组，而是将N点DFT写成前后两部分：X (k)= DFT [ x (n)]二^-12 X ( n)Wknn =0(N /^1 N-p= 2 X(n)Wkn + 2 X(n)Wknn=0Nn=N/ 2nk + N/ (n+N /2)k+ / 2)NWNn =0n=0nk= N2'[x (n) + W(n/2)kX (n +N / 2)WnNn =0因为 Wn / 2 =-1,W (N / 2)k =(-1)k , k 为偶数时(T)k = 1 , k 为奇数时NN(T)k = -1 ,由此可将X(k)分解为偶数组和奇数组:NX (k)= n =0 [x (n) + (- 1)kX(n + N / 2)WnkX(2r)= n=0 [x(n)+x(n + N/N/2- [x(72)+ X(72 + / 2) jy nrn=0NX (2r +1)= n=0 [x (n) - x(n + N / 2)W (2r+1)nN N/ 2= [x(n) - x(n + N / 2)]WnWnrn=0n = 0,1L , N / 2 - 1(n) = x (n) + x (n + N / 2) 1X (n) = [x(n) - x(n + N / 2)]Wn2这两个序列都是N/2点的序列，对应的是两个N/2点的DFT运算:N/ 2- 11 N / 2X (2r)= n= x (n)Wnr^L2-12 N / 2X(2r +1)= x (n)Wrnn=0这样，同样是将一个N点的DFT分解为两个N/2点的DFT 了。

频率抽选法 对应的碟形运算关系图如下：N 对于N=8时频率抽取法的FFT流图如下:oooooooo(01⑴(2)(3]同(51回(71xx(x(x(x(x(x(x(\X\\zz0xzXXXZoA/。