§4DFT的快速算法——FFTDFT的快速算法的快速算法——FFT时域抽取基-2FFT算法DIT-FFT）时域抽取基-2FFT算法（DIT-FFT）算法（频域抽取基-2FFT算法DIF-FFT）算法（频域抽取基-2FFT算法（DIF-FFT）的快速算法（IFFT）逆DFT的快速算法（IFFT）N为合数的FFT算法（混合基）混合基）1DFT的快速算法（FFT）DFT的快速算法（FFT）综述的快速算法DFT的运算量DFT的运算量nkX(k)=DFT[x(n)]=∑x(n)WNn=0N?1(k=0,1?,N?1),复乘N2次复加N×N?1≈N2次数：，数：（）减少DFT运算量的方法减少DFT运算量的方法①将长度N变短。例如若将长度变为N/2，则运算量变成：将长度N变短。例如若将长度变为N/2，则运算量变成：复乘N2/4次复加≈N2/4次数：，数：Wnk的性质②利用Nn(n+rN)周期性：周期性：WN=WNn?n*共轭对称性：共轭对称性：WN=(WN)rnn可约性：可约性：WrN=WN版权所有违者必究第三章第2讲2DFT的快速算法（FFT）DFT的快速算法（FFT）综述的快速算法FFT的算法分类FFT的算法分类FFT算法首先由Cooly-Tuky提出了基2FFT算法FFT算法首先由Cooly-Tuky提出了基－2FFT算法，它对算法，它对DFT的发展起到了极大推进作用。随后又出现了混合基DFT的发展起到了极大推进作用。随后又出现了混合基算法。算法。算法作介绍，内容包括：FFT的基本本节仅对基2FFT算法本节仅对基－2FFT算法作介绍，内容包括：FFT的基本思想、时域与频域抽取的基－2FFT算法及其程序实现算法及其程序实现。思想、时域与频域抽取的基－2FFT算法及其程序实现。基-2FFT算法（DIT-FFT）FFT算法DIT-FFT）算法（指要求长度N指要求长度N满足N=2MM为整数），若不满足可将（序列补零延长，使其满足长度要求。时域抽取与频域抽取时抽FFT法Decimation-In-Tim，称e简DIT-FFT）?按域取算（?频抽FFT算（法Decimation-In-Freqency，称-FFT）简DIF?按域取版权所有违者必究第三章第2讲3时域抽取基－2FFT算法DIT-FFT）算法（时域抽取基－2FFT算法（DIT-FFT）算法的推导时域抽取算法是按时域抽取算法是按n的奇偶把时间序列x(n)分解为两个长为N/2点的序列，即：N/2点的序列，即：x1(r)=x(2r)x2(r)=x(2r+1)N?1n=0knNr=0,1,...,N/2?12krN则(k)=∑x(n)W=X=2∵WNkr=e?1N/2r=0N/2?1r=0∑x(2r)Wr=01++N/2?1r=0∑x(2r+1)W22krNk(2r+1)NN/2?1∑x(r)W?jN/2?1r=02krN∑x(r)WWkN?j2π2KrN=e2πkrN/2∴X(k)=krkx1(r)WN/2+WN∑=1N/2WkrN/2?r=0krx2(r)WN/2∑k=X1(k)+WNX2(k)k=0,1N/2?1,...,第三章第2讲4版权所有违者必究时域抽取基－2FFT算法DIT-FFT）算法（时域抽取基－2FFT算法（DIT-FFT）x上式中X1(k)和2(k)分别为x1(n)和2(n)的N/2点DFT，即：N/2点DFT，即：XX1(k)=N/2?1n=0∑x(n)W1knN/2Nk=0,1,...,?12X2(k)=N/2?1n=0knx2(n)WN/2∑Nk=0,1,...,?12这是X(k)(k=0,1,...N/2?1)前N/2点DFTN/2点版权所有违者必究第三章第2讲5时域抽取基－2FFT算法DIT-FFT）算法（时域抽取基－2FFT算法（DIT-FFT）对于X(k)(k=N/2,?N?1)后N/2点的DFTN/2点kk∵WN+N/2=?WNNk∴X(k+)=X1(k)?WNX2(k)2Nk=0,1,...,?12显然，可采用蝶式运算图显然，可采用蝶式运算图来表示上述前N/2和后N/2两式，蝶式运算图来表示上述前N/2和后N/2两式如下图所示：版权所有违者必究第三章第2讲6时域抽取基－2FFT算法DIT-FFT）算法（时域抽取基－2FFT算法（DIT-FFT）例如N=8时的DFT,可以分解为两个N/2=4点例如N=8时的DFT,可以分解为两个N/2=4点DFT,如下图：版权所有违者必究第三章第2讲7时