基2FFT算法分析的介绍

1、快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT). 1965年，Cooley和Tukey提出了计算离散傅里叶变换( DFT)的快 速算法，将DFT的运算量减少了几个数量级。 从此，对快速傅里叶变换(FFT) 算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2 DIF。 FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅里叶变换(FFT)是计算离散傅里叶变换(D

2、FT )的快速算法。DFT的定义式为N -JknX(k)二' x(n)Wn RN(k)心在所有复指数值 wNkn的值全部已算好的情况下，要计算一个X(k)需要N次复数乘法和N 1次复数加法。算出全部 N点X (k)共需N 2次复数乘法 和N(N -1)次复数加法。即计算量是与 N2成正比的。FFT的基本思想：将大点数的DFT分解为若干个小点数 DFT的组合，从而减少运算量。Wn因子具有以下两个特性，可使DFT运算量尽量分解为小点数的DFT运算：(1)周期性：wNiN)n =wNkn 二wNn N)k对称性：wNkM2)_ _w.利用这两个性质，可以使 DFT运算中有些项合并，以减少乘法

3、次数。例子: 求当N = 4时，X(2)的值3X(2)二嘉 x(n)W：n =x(0)W4° x(1)W42 x(2)W： x(3)W：n z0= x(0) x(2)W40 x(1) x(3)W42 (周期性) =x(0) x(2)-x(1) x(3)W：(对称性)通过合并，使乘法次数由4次减少到1次，运算量减少。FFT的算法形式有很多种，但基本上可以分为两大类：按时间抽取(DIT )和按频率抽取(DIF )。4.1按时间抽取(DIT )的FTT为了将大点数的 DFT分解为小点数的 DFT运算，要求序列的长度 N为 复合数，最常用的是 N =2M的情况(M为正整数)。该情况下的变换称

4、为 基2FFT。下面讨论基2情况的算法。先将序列x(n)按奇偶项分解为两组x(2r) =Xi(r) &2r +1) =x2(r)r =0,1/ ,- -12将DFT运算也相应分为两组N-1X(k)二 DFTx(n)二、x(n)Wn =0N 4N 4=Z x(n)W,n+ E x(n)W,nn =0n =0n为偶数n为奇数N /2 4N /2 4=、xJWrT' x(2r 1)wN2r 1)kr =0r =0N /2 JN /2J2rkk2rk=、Xi()WnWn 、X2()Wnr z0r z0N /2 JN/2八 Xi(r)wN：2 W, v X2(r)wNk/2(因为 W(r

5、k 二W)r z0r =0= Xi(k) W,X2(k)其中 X1(k)、X2(k)分别是 x1(n)、x2(n)的 N/2 点的 dftN /2 JN/2VrkrkXi(k)八 Xi()Wn/2 二x(2)Wn/2,0 乞 k1r Tr A2N /2 JN /2drkrkX2(k) = ' X2()Wn/2x(2r 1)Wn/2,0 乞 k1r =0r =02至此，一个N点DFT被分解为两个 N/2点的DFT。上面是否将全部 N点的X(k)求解出来了？N分析：Xi(k)和X2(k)只有N/2个点(k=0,1，1)，则由2kX(k) =XMk)，WNX2(k)只能求出X(k)的前N/2

6、个点的DFT，要求出全部N点的X(k)，需要找出X,k)、X2(k)和X(k N/2)的关系，其 中 k =0,1, -1。由式子 X(k) =Xjk) W,X2(k)可得X(k N /2X1(k N/2) wNk N/2X2(k N/2)化简得kNX(k N/2) = XMk)-WzX2(k) , k=0,1，12这样N点DFT可全部由下式确定出来：X(k) =X1(k)+W,X2(k)N 彳kk=0,1,-1(*).X(k + N/2) = X1(k) WnX2(Q2上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运61算。通过这样的分解以后，每一个2N 2 N 2N/2点

7、的DFT只需要(一)2次复数乘24法，两个 N/2点的DFT需要2N 2 N22( )2次复乘，再加上将两个N/2点2 2DFT合并成为 N点DFT时有N / 2次与 W因子相乘，一共需要N2N N 次复乘。可见，通过这样的分解，运算量节省了近一半。2 2因为N =2M , N/2仍然是偶数，因此可以对两个 N/2点的DFT再分别作进一步的分解，将两个 N/2点的DFT分解成两个N/4点的DFT。Xi（2I）f（I） 曲（21 +1）*1）l =0,1, ,N -14例如对x,(r)，可以在按其偶数部分及奇数部分进行分解:462则的运算可相应分为两组:N /4 4X1（k） = ' X

8、1（2l）wN"/k2l =0N /4 4' Xi（2I1）wN221）kl ZZ0N /44八 X3（l）WN/4 WNk/2l z0N /4 4' X4（l）WN/4l =0= X3（k） W,/2X4（k）Nk=0,1，1将系数统一为以N为周期，即W爲2 =Wf2，可得k =0,1,N -14Xi（k） =X3（k） +Wn X4（k）Xi（k N/4）=X3（k） -WfN!kX4（k）同样，对X2（k）也可进行类似的分解。一直分解下去，最后是2点的3DFT, 2点DFT的运算也可用碟形符号来表示。这样，对于一个N = 2 =8的DFT运算，其按时间抽取的分解

9、过程及完整流图如下图所示。J * * *1-忆伍 n p317 x(x(x(xlx(x(xXX X X X X X X XDFT占E8S'11 )P1I3)Ml151161PI x(x(xrx(x(x><(x(J u u n 0 2 4 6 fl ft flX X X Xu n n u 13 5 7 fl -fl- flX X X X2占DFT2占DFT?点DFT2点DFToooo-cooox(X X X X X X(0)阿61问(31171 xllMxlxl 1x(X00 000000* *-1P 卩II20M 归 el(7 X(X(X(X(X(X(XX(OO-OQOOO

10、O这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。分析上面的流图，N =2M，共要进行 M次分解，构成了从 x(n)到X(k)的M级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要 N/2次复乘和N次复加，则按时间抽取的 M级运算后总共需 要复数乘法次数： mF二山 M =Nlog2NF 2 2 y2复数加法次数：aF二N M二Nlog2N根据上面的流图，分析FFT算法的两个特点，它们对FFT的软硬件构成产生很大的影响。(1) 原位运算也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储 在原来的存储器中，

11、 直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。(2) 变址分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置” 的顺序。见图。自然顺序二进制表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110011371111117码位倒置顺序0X(0)码位倒置的变址处理X(7)在实际运算中，直接将输入数据 x(n)按码位倒置的顺序排好输入很不 方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就

12、可以进行FFT的原位运算。变质的功能如图所示。用软件实现是通用采用雷德(Rader)算法，算出I的倒序J以后立即将输入数据X(I)和X(J)对换。尽管变址运算所占运算量的比例很小，但对某些高要求的应用(尤其在实时信号处理中)，也可设法用适当的电路结构直接实现变址。例如单片数字信号处理器 TMS320C25就有专用 于FFT的二进制码变址模式。4. 2按频率抽取(DIF )的FTT除时间抽取法外，另外一种普遍使用的FFT结构是频率抽取法。频率抽取法将输入序列不是按奇、偶分组，而是将N点DFT写成前后两部分：N J knX(k)二 DFTx(n)二 '、x(n)WNn=0(N /2) 1N

13、 A=x(n)W+ V x(n)W；nn=0n -N/2N /2 JN/2=' x(n)Wk、x(n N/2)wNn N/2)kn =0n =0N /2 J八x(n) wNN/2沐x(n N/2)Wkn =Q因为 W&/21,wNN/2)k =(-1)k , k 为偶数时(-1)k =1 , k 为奇数时(_1)k二1由此可将X(k)分解为偶数组和奇数组:N /2 4X(k)= a x(n) (-1)kx(n N/2)W0n=QN/2 二X(2r)= ' x(n) x(n N /2)WfJnr n =0N /2 4二 x x(n) x(n N/2)W,；2n =0N /

14、2 4X(2r 1> y x(n) -x(n N /2)WN21)n n=0N /2 4-為x(n) -x(n N/2)WrJwJ/2n z0n =0,1, N/2 -1x1 (n) = x(n) + x( n + N / 2) X2(n)=x(n) -x(n N/2)Wr：这两个序列都是 N/2点的序列，对应的是两个N/2点的DFT运算:N/2 JX(2r)八 xi(n)崗寫n z0N /2 dX(2r 1)八 X2(n)W/2这样，同样是将一个 N点的DFT分解为两个N/2点的DFT 了。频率抽选法对应的碟形运算关系图如下：刈可xl)x(3bx(4)ox5)ox6)oDFT叫4占DF

15、Tx X0)*o X2)” Xx X6) m Xl)x X(3)R X5) >oX7)£ 1金2澤 gJr 妙fFF莎Ur12 3 4 f4 ft ( fl fl X X X X X*F*oOo O-o X0IX(2)XoX7)W3x(05 xlh x罔。 x30 刈忙 x(5)o x6)0 如这种分组的办法由于每次都是按输出X(k)在频域的顺序上是属于偶数还是奇数来分组的，称为频率抽取法。与前面按时间抽取的方法相比，相同点 问题：如何利用快速算法计算IDFT ？分析IDFT的公式：1 N 4x(n) =IDFT X(k)二一' X(k)Wfk,n =0,1, N -1

16、N k=o比较DFT的公式：N -4X(k)二 DFT x(n) =' x(n)wNk 二 0,1, N -1n=0得知可用两种方法来实现IDFT的快速算法：(1)只要把DFT运算中的每一个系数该为Wn我，并且最后再乘以常数，就可以用时间抽取法N或频率抽取的FFT算法来直接计算IDFT o这种方法需要对 FFT的程序和参 数稍加改动才能实现。 (2) 因为1 N A * nk * 1 *x(n) 、X (k)WN DFTX (k), n -0,1/ , N -1，也就 N k卫N是说，可先将 X(k)取共轭变换，即将 X(k)的虚部乘以1,就可直接调用FFT的程序，最后再对运算结果取一

17、次共轭变换并乘以常数1/N即可得到x(n)的值。这种方法中，FFT运算和IFFT运算都可以共用一个子程序块， 在使用通用计算机或用硬件实现时比较方便。4.1.3混合基FFT算法以上讨论的是基2的FFT算法，即N =2M的情况，这种情况实际 上使用得最多，这种 FFT运算，程序简单，效率很高，用起来很方便。另 外，在实际应用时，有限长序列的长度N到底是多少在很大程度时是由人为因素确定的，因此，大多数场合人们可以将N选定为N =2M，从而可以直接调用以2为基数的FFT运算程序。如果长度N不能认为确定，而 N的数值又不是以2为基数的整数次方，一般可有以下两种处理方法：(1) 将x(n)用补零的方法延

18、长，使N增长到最邻近的一个N =2M数值。例如，N=30,可以在序列x(n)中补进x(30) = x(31)=0两个零值点， 使N=32。如果计算FFT的目的是为了了解整 个频谱，而不是特定频率点，则此法可行。因为有限长序列补 零以后并不影响其频谱X(ejw)，只是频谱的采样点数增加而已。(2) 如果要求特定频率点的频谱，则N不能改变。如果 N为复合数，则可以用以任意数为基数的FFT算法来计算。快速傅里叶变换的基本思想就是要将 DFT的运算尽量分小。例如， N=6时，可以按照N=3 X2分解，将6点 DFT分解为3组2点 DFT。举例：N=9时的快速算法。4.2快速傅里叶变换的应用凡是可以利用

19、傅里叶变换来进行分析、综合、变换的地方，都可以利用FFT算法及运用数字计算技术加以实现。FFT在数字通信、语音信号处理、图像处理、匹配滤波以及功率谱估计、仿真、系统分析等各个领域都得 到了广泛的应用。但不管FFT在哪里应用，一般都以卷积积分或相关积分的具体处理为依据，或者以用FFT作为连续傅里叶变换的近似为基础。4.2.1利用FFT求线性卷积一快速卷积在实际中常常遇到要求两个序列的线性卷积。如一个信号序列x(n)通过FIR滤波器时，其输出 y(n)应是x(n)与h(n)的卷积：cdy(n) =x(n) h(n) =x(m)h(n -m)m=-有限长序列x(n)与h(n)的卷积的结果y(n)也是

20、一个有限长序列。假设x(n)与h(n)的长度分别为 N1和N2，贝U y(n)的长度为N=N1+N2-1。若通过补零使x(n)与h(n)都加长到N点，就可以用圆周卷积来计算线性卷积。这样得到用FFT运算来求y(n)值(快速卷积)的步骤如下：(1) 对序列x(n)与 h( n)补零至长为 N ,使 N > N1+N2-1 ,并且N =2m (M为整数)，即x(n)二；x(n), n = 0,1,，N1 1O n = N1, N1 +1,，N 1 一、h(n), n= 0,1,，N21 h(n) = *0, n = N2,N2+1,，N 1(2) 用FFT计算x(n)与h(n)的离散傅里叶变

21、换x(n)二(FFT )二 X(k)(N 点)h(n)= (FFT )二 H(k)(N 点)(3) 计算 Y(k)=X(k)H(k)(4) 用IFFT计算Y(k)的离散傅里叶反变换得：y(n)=IFFTY(k) (N点)4.2.2 利用FFT求相关一快速相关互相关及自相关的运算已广泛的应用于信号分析与统计分析，应用于连续时间系统也用于离散事件系统。用FFT计算相关函数称为快速相关，它与快速卷积完全类似，不同的是一个应用离散相关定理，另一个应用离散卷积定理。同样都要注意到离散傅里叶变换固有的周期性，也同样用补零的方法来绕过这个障碍。设两个离散时间信号 x(n)与y(n)为已知，离散互相关函数记作

22、Rxy (n)，定义为QORxy (n)二 ' x(m)y(n m)m二：如果x(n)与y(n)的序列长度分别为 N1和N2，则用FFT求相关的计算步骤 如下：(1 )对序列x(n)与y( n)补零至长为N ,使N > N1+N2-1 ,并且 N =2m (M为整数)，即(、|X(n), n = 01,-,N1-1x(n) = *0, n = N1,N1+1,，N 1/、y( n), n =0,1，N2-1y(n)=丿0, n = N2,N2+1，N 1(2) 用FFT计算x(n)与y(n)的离散傅里叶变换x(n)二(FFT )二 X(k)(N 点)y(n)= (FFT)u Y(k)(N 点)(3) 将X(k)的虚部lmX(k)改变符号，求得其共轭X*(k)(4) 计算 Rxy