FFT初探FFT的基本思想利用DFT系数的特性，合并DFT运算中的某些项，把长序列DFT变成短序列DFT，从而减少其运算量。DFT计算复杂度一窥N点有限长序列x(n)X(k)=∑x(n)Wn=0N?1?1knNAneasyexampleX[m]=X[0]=X[1]=N?1∑k+x[k]WkmN,++m=0,,?N?1102WN32WN=002WN02WN0+3WN13WN0+3WN2+3WN=10=?1?jX[2]=02WN02WN2+3WN33WN4+3WN6+3WN+62WN92WN=0X[3]=+复数加法N(N-1)+=?1+j复数乘法N2那我们有什么办法解决呢？利用WnkN的特性W的特性nkNnkWN=e?j2πnkN对称性nk?(n(WN)*=WNnk=WNN?n)k=WN(N?k)↓↓Nk?nknNWN?WNWN?WN?nk周期性可约性WWnkN=W(N+n)kN=Wn(N+k)Nnk/mN/mnkN?je=e?jπ=?1e↑0N/2(k+N/2)k特殊点：WN=1WN=?1WN=?WN2πmnkmN↓=WmnkmNWnkN=W?j2πN?N2FFT计算方法（按时间抽取）1、算法原理设序列点数N=2L，L为整数。若不满足，则补零将序列x(n)按n的奇偶分成两组：?x1(r)=x(2r)，r=0，2，N/2?11，...??x2(r)=x(2r+1)将N点DFT定义式分解为两个长度为N/2的DFTX(k)N?1kn=DFTx(n)=∑x(n)WNn=0N/2?1N/2?12rk=∑x(2r)WN+∑x(2rr=0r=0[](2r+1)k+1)WNn为偶n为奇N/2?1r=0rkx2(r)WN/2∑X2(k)=N/2?1r=0rkkx1(r)WN/2+WN∑X1(k)2rk（这一步利用：WNrk=WN/2）r,k=0,1,...N/2?1………（………（1）记：X(k)=kX1(k)+WNX2(k)再利用周期性求X(k)的后半部分再利用周期性求X(k)的后半部分X(k)∵Wr(N/2+k)N/2=WrkN/2N/2?1?N?N/2?1rrkX1?+k?=∑x1(r)WN(/N/2+k)=∑x1(r)WN/2=X1(k)2?2?r=0r=0?N?X2?+k?=X2(k)?2?又WNk+N2kk=WNN/2WN=?WNk?X(k)=X1(k)+WNX2(k)，k=0,1,2,...N/2?1??(2)?X(N+k)=X(N+k)+W(N/2+k)X(N+k)1N2?222?k=X1(k)?WNX2(k)，k=0,1,2,...N/2?1k?X(k)=X1(k)+WNX2(k)?k=0,1,...,N/2?1∴?NkX(k+)=X1(k)?WNX2(k)??2将上式表达的运算用一个专用“蝶形”信流图表示。X1(k)kX2(k)WNkX1(k)+WNX2(k)kX1(k)?WNX2(k)上支路为加法，下支路为减法；注：a.上支路为加法，下支路为减法；乘法运算的支路标箭头和系数。b.乘法运算的支路标箭头和系数。N=8=2x(0)x(2)x(4)X1(0)3X(0)N2点DFTX1(1)X1(2)X1(3)X(1)X(2)X(3)x(6)WN0x(1)x(3)x(5)x(7)X2(0)N2点DFT1WNX(4)X2(1)X2(2)WN2WN3X(5)X(6)X(7)X2(3)分解后的运算量：分解后的运算量：复数乘法一个N/2点DFT(N/2)2点一个两个N/2点DFTN2/2点两个一个蝶形N/2个蝶形个蝶形总计1N/2复数加法N/2(N/2?1)N(N/2?1)2NN2/2+N/2≈N2/2N(N/2?1)+N≈N2/2运算量减少了近一半FFT运算量与运算特点1．N=2L时，共有L=log2N级运算；每一级有N/2个蝶形结。2．每一级有N个数据中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3．计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N次复乘法；复加法L*N=Nlog2N次。与直接DFT定义式运算量相比(倍数)N2/(Nlog2N)。当N大时，此倍数很大。比较DFT比较DFT