按时间抽取的基2FFT算法分析

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

3

x(n)W

2n4

x(0)W04

x(1)W

24

x(2)W

44

x(3)W64n0[x(0)＝[x(0)

x(2)]W0[x(1)x(3)]W谢谢阅读4x(2)]－[x(1)x(3)]W04

2 (周期性)4(对称性)通过合并，使乘法次数由4次减少到1次，运算量减少。谢谢阅读FFT的算法形式有很多种，但基本上可以分为两大类：按时间抽取谢谢阅读（DIT）和按频率抽取（DIF）。4.1按时间抽取（DIT）的FTT为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为精品文档放心下载复合数，最常用的是N2M的情况（M为正整数）。该情况下的变换称为感谢阅读基2FFT。下面讨论基2情况的算法。先将序列x(n)按奇偶项分解为两组x(2r)x(r)r0,1,,N11x(2r1)x(r)22.将DFT运算也相应分为两组N1X(k)DFT[x(n)]x(n)Wkn谢谢阅读N0N1x(n)Wkn＋N1x(n)Wkn谢谢阅读NNn0n0n为偶数n为奇数N/21N/21＝x(2r)W2rkx(2r1)W(2r1)kNNr0r0N/21N/21＝x(r)W2rkWkx(r)W2rk1NN2Nr0r0N/21WkN/21（因为W2rkWrk）＝x(r)Wrkx(r)Wrk1N/2N2N/2NN/2r0r0X(k)WkX(k)1N2其中X(k)、X(k)分别是x(n)、x(n)的N/2点的DFT1212X(k)＝x(r)Wrkx(2r)Wrk,0kN1N/21N/2111N/2N/22r0r0N/21N/21,0kN1X(k)＝x(r)Wrkx(2r1)Wrk22N/2N/22r0r0至此，一个N点DFT被分解为两个N/2点的DFT。谢谢阅读上面是否将全部N点的X(k)求解出来了？分析：X(k)和X(k)只有N/2个点（k0,1,,N1），则由122X(k)X(k)WkX(k)只能求出X(k)的前N/2个点的DFT，要求出感谢阅读1 N 2全部N点的X(k)，需要找出X(k)、X(k)和X(kN/2)的关系，其感谢阅读1 2.k0,1,,N21。由式子X(k)X(k)WkX(k)可得N21谢谢阅读X(kN/2)X(kN/2)WkN/2X(kN/2)化简得感谢阅读1 N 2X(kN/2)＝X(k)WkX(k谢谢阅读1 N 2这样N点DFT可全部由下式确定出来：X(k)X(k)WkX(k)1N2X(kN/2)X(k)WkX(k)1N2

)，k0,1, ,N21k0,1,,N1（＊）2上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运感谢阅读算。aaWkbNbaWkbWk-1NN图 蝶形运算符号通过这样的分解以后，每一个N／2点的DFT只需要(N)2N2次复数感谢阅读2 4乘法，两个N/2点的DFT需要2(N)2N2次复乘，再加上将两个N／2谢谢阅读2 2点DFT合并成为N点DFT时有N／2次与W因子相乘，一共需要谢谢阅读N2NN2222次复乘。可见，通过这样的分解，运算量节省了近一半。因为N2M，N/2仍然是偶数，因此可以对两个N/2点的DFT再感谢阅读分别作进一步的分解，将两个N/2点的DFT分解成两个N/4点的DFT。感谢阅读.例如对x(r)，可以在按其偶数部分及奇数部分进行分解：精品文档放心下载1x(2l)x(l)l0,1,,N131x(2l1)x(l)414则的运算可相应分为两组：N/41N/41X(k)＝x(2l)W2lkx(2l1)W(2l1)k11N/21N/2l0l0N/41WkN/41＝x(l)Wlkx(l)Wlk3N/4N/24N/4l0l0X(k)WkX(k)k0,1,,N13N/244将系数统一为以Ｎ为周期，即WkW2k，可得N/2NX(k)X(k)W2kX(k)Nk0,1,,13N41X(kN/4)X(k)W2kX(k)413N4同样，对X(k)也可进行类似的分解。一直分解下去，最后是２点的精品文档放心下载2DFT，２点DFT的运算也可用碟形符号来表示。这样，对于一个N238精品文档放心下载的DFT运算，其按时间抽取的分解过程及完整流图如下图所示。谢谢阅读.这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数精品文档放心下载还是奇数来抽取的，故称为“时间抽取法”。分析上面的流图，N 2M，一共要进行M次分解，构成了从x(n)到感谢阅读X(k)的M级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一谢谢阅读级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共精品文档放心下载.需要复数乘法次数：mFNMNlog2N复数加法次数：aNMNlogNF2根据上面的流图，分析ＦＦＴ算法的两个特点，它们对ＦＦＴ的软硬件感谢阅读构成产生很大的影响。（１）原位运算也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储谢谢阅读在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图谢谢阅读分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备谢谢阅读成本。（２）变址分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”精品文档放心下载的顺序。见图。自然顺序二进制表示码位倒置码位倒置顺序00000000100110042010010230111106.41000011510110156110011371111117码位倒置顺序01234567X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)码位倒置的变址处理在实际运算中，直接将输入数据x(n)按码位倒置的顺序排好输入很不感谢阅读方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序感谢阅读的存储换成码位倒置顺序的存储，这样就可以进行FFT的原位运算。变质谢谢阅读的功能如图所示。用软件实现是通用采用雷德（Rader）算法，算出I的倒感谢阅读序Ｊ以后立即将输入数据X(I)和X(J)对换。尽管变址运算所占运算量的比例精品文档放心下载很小，但对某些高要求的应用（尤其在实时信号处理中），也可设法用适当感谢阅读的电路结构直接实现变址。例如单片数字信号处理器TMS320C25就有专谢谢阅读用于FFT的二进制码变址模式。4.２按频率抽取（DIF）的FTT除时间抽取法外，另外一种普遍使用的FFT结构是频率抽取法。频率谢谢阅读.抽取法将输入序列不是按奇、偶分组，而是将Ｎ点DFT写成前后两部分：谢谢阅读N1X(k)DFT[x(n)]x(n)Wkn谢谢阅读N0(N/2)x1(n)Wkn＋N1x(n)Wkn感谢阅读NNn0nN/2N/21N/21＝x(n)Wnkx(nN/2)W(nN/2)kNNn0n0N/21＝[x(n)W(N/2)kx(nN/2)]WnkNNn0因为WN/21,W(N/2)k(1)k，k为偶数时(1)k1，k为奇数时NN(1)k1，由此可将X(k)分解为偶数组和奇数组：N/21X(k)＝ [x(n)(1)kx(nN/2)]Wnk感谢阅读N0N/21X(2r)＝ [x(n)x(nN/2)]W2nr感谢阅读N0N/2[1x(n)x(nN/2)]Wnr谢谢阅读N/20N/21X(2r1)＝ [x(n)x(nN/2)]W(2r1)n感谢阅读N0N/2[1x(n)x(nN/2)]WnWnr感谢阅读NN/2n0x(n)x(n)x(nN/2)n0,1,,N/21令1x(n)[x(n)x(nN/2)]Wn2N这两个序列都是N/2点的序列，对应的是两个N/2点的DFT运算：感谢阅读.X(2r

N/21)＝ x(n)]W1

nrN/20X(2r

N/211)＝ x(n)W2

rnN/20这样，同样是将一个N点的DFT分解为两个N/2点的DFT了。频率抽选精品文档放心下载法对应的碟形运算关系图如下：aabb(ab)WnN-1WnN对于N=8时频率抽取法的FFT流图如下：.这种分组的办法由于每次都是按输出X(k)在频域的顺序上是属于偶数还是谢谢阅读奇数来分组的，称为频率抽取法。与前面按时间抽取的方法相比，相同点感谢阅读问题：如何利用快速算法计算IDFT？分析IDFT的公式：x(n)IDFT[X(k)]1N1X(k)Wnk,n0,1, ,N1谢谢阅读N Nk0比较DFT的公式：(k)DFT[x(n)]N1x(n)Wnk,k0,1,,N1谢谢阅读N0得知可用两种方法来实现IDFT的快速算法：（１）只要把DFT运算中的每精品文档放心下载一个系数Wnk该为Wnk，并且最后再乘以常数1，就可以用时间抽取法精品文档放心下载N N N.或频率抽取的FFT算法来直接计算IDFT。这种方法需要对FFT的程序和参精品文档放心下载数 稍 加 改 动 才 能 实 现 。（ ２ ） 因 为谢谢阅读x(n)1N1X*(k)Wnk]*1{DFT[X*(k)]},n0,1,,N1，也就[NNN0是说，可先将X(k)取共轭变换，即将X(k)的虚部乘以－１，就可直接调用精品文档放心下载FFT的程序，最后再对运算结果取一次共轭变换并乘以常数1/N即可得到精品文档放心下载x(n)的值。这种方法中，FFT运算和IFFT运算都可以共用一个子程序块，精品文档放心下载在使用通用计算机或用硬件实现时比较方便。4.1.3混合基FFT算法以上讨论的是基2的FFT算法，即N2M的情况，这种情况实际上使用得最多，这种FFT运算，程序简单，效率很高，用起来很方便。另精品文档放心下载外，在实际应用时，有限长序列的长度N到底是多少在很大程度时是由人谢谢阅读为因素确定的，因此，大多数场合人们可以将N选定为N2M，从而可精品文档放心下载以直接调用以２为基数的FFT运算程序。如果长度N不能认为确定，而N的数值又不是以2为基数的整数次精品文档放心下载方，一般可有以下两种处理方法：（１） 将x(n)用补零的方法延长，使N增长到最邻近的一个精品文档放心下载2M数值。例如，N=30，可以在序列x(n)中补进x(30)＝精品文档放心下载.x(31)＝０两个零值点，使N=32。如果计算FFT的目的是为了谢谢阅读了解整个频谱，而不是特定频率点，则此法可行。因为有限长谢谢阅读序列补零以后并不影响其频谱X(ejw)，只是频谱的采样点数增谢谢阅读加而已。（２）如果要求特定频率点的频谱，则N不能改变。如果N为复合谢谢阅读数，则可以用以任意数为基数的FFT算法来计算。快速傅里叶变换的谢谢阅读基本思想就是要将DFT的运算尽量分小。例如，N=6时，可以按照精品文档放心下载N=3×２分解，将６点DFT分解为３组２点DFT。感谢阅读举例：N=9时的快速算法。4.2 快速傅里叶变换的应用凡是可以利用傅里叶变换来进行分析、综合、变换的地方，都可以利精品文档放心下载FFT算法及运用数字计算技术加以实现。FFT在数字通信、语音信号处理、图像处理、匹配滤波以及功率谱估计、仿真、系统分析等各个领域都得到了广泛的应用。但不管FFT在哪里应用，一般都以卷积积分或相关积分的具体处理为依据，或者以用FFT作为连续傅里叶变换的近似为基础。感谢阅读4.2.1利用FFT求线性卷积—快速卷积在实际中常常遇到要求两个序列的线性卷积。如一个信号序列x(n)通过谢谢阅读.FIR滤波器时，其输出y(n)应是x(n)与h(n)的卷积：精品文档放心下载y(n)x(n)h(n)

x(m)h(nm)m有限长序列x(n)与h(n)的卷积的结果y(n)也是一个有限长序列。假设x(n)感谢阅读与h(n)的长度分别为N1和N2，则y(n)的长度为N=N1+N2-1。若通过精品文档放心下载补零使x(n)与h(n)都加长到N点，就可以用圆周卷积来计算线性卷积。这谢谢阅读样得到用FFT运算来求y(n)值（快速卷积）的步骤如下：精品文档放心下载（１）对序列x(n)与h(n)补零至长为N，使N≥N1+N2-1，并且谢谢阅读N2M(M为整数)，即x(n),n0,1,,N11x(n)0,nN1,N11,,N1h(n),n0,1,,N21h(n)0,nN2,N21,,N1（２）用FFT计算x(n)与h(n)的离散傅里叶变换x(n)(FFT)X(k)（N点）h(n)(FFT)H(k)（N点）（３）计算Y(k)=X(k)H(k)（４）用IFFT计算Y(k)的离散傅里叶反变换得：y(n)=IFFT[Y(k)]（N点）.4.2.2利用FFT求相关—快速相关互相关及自相关的运算已广泛的应用于信号分析与统计分析，应用于连谢谢阅读续时间系统也用于离散事件系统。用FFT计算相关函数称为快速相关，它与快速卷积完全类似，不同的精品文档放心下载是一个应用离散相关定理，另一个应用离散卷积定理。同样都要注意到离散谢谢阅读傅里叶变换固有的周期性，也同样用补零的方法来绕过这个障碍。精品文档放心下载设两个离散时间信号x(n)与y(n)为已知，离散互相关函数记作R(n)，谢谢阅读xy定义为R(n)x(m)y(nm)xy如果x(n)与y(n)的序列长度分别为N1和N2，则用FFT求相关的计算步骤感谢阅读如下：（１）对序列x(n)与y(n)补零至长为N，使N≥N1+N2-1，并且精品文档放心下载2M(M为整数)，即x(n),n0,1, ,N11x(n)0, nN1,N11, ,N1y(n),n0,1, ,N21y(n)0, nN2,N21, ,N1感谢阅读（２）用FFT计算x(n)与y(n)的离散傅里叶变换精品文档放心下载x(n)(FFT)X(k) （N点）谢谢阅读.y(n)(FFT)Y(k) （N点）精品文档放心下载（３）将X(k)的虚部Im[X(k)]改变符号，求得其共轭