7-2按时间抽取的FFT算法

FFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency§7-2按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22019/9/4一、按时间抽取的算法原理设序列点数N=2L，L为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：312221xrxrxrxr0,1,...,/21rN2019/9/44•则x(n)的DFT:111000NNNnknknkNNNnnnXkxnWxnWxnWn为偶数n为奇数/21/2121200221NNrkrkNNrrxrWxrW/21/21221200NNrkrkkNNNrrxrWWxrW/21/211/22/200NNrkkrkNNNrrxrWWxrW12kNXkWXk,0,1,.../21rkN2019/9/45•再利用周期性求X(k)的后半部分121122,/222XkXkNNNXkXkXkXk是以为周期的/22NkNkkNNNN又2019/9/461212()()()()()()2kNkNXkXkWXkNXkXkWXk0,1,...,/21kN•一个“蝶形运算”包含1次乘法，2次加法2019/9/472019/9/4复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计8分解后的运算量：•运算量减少了近一半22/2/2/2NNN2/21/2NNNN2019/9/4N/2仍为偶数，进一步分解：N/2N/491314(2)()(21)()xlxlxlxl0,1,...,/41lN13/2413/24()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,...,14Nk2019/9/4102/2kkNNWW统一系数：10同理：25/2625/26()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,...,14Nk其中：552()[()][(2)]XkDFTxlDFTxl662()[()][(21)]XkDFTxlDFTxl0,1,...,/41lN这样逐级分解，直到2点DFT基2时间抽取FFT算法流图11N=2x[k]={x[0],x[1]}]1[]0[]0[02xWxX]1[]0[]1[12xWxX]0[x]1[x]0[X-102W]1[X]1[]0[02xWx2019/9/44点基2时间抽取FFT算法流图12x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT111104W14W02W02WX[0]X[1]X[2]X[3]1,0],[][][241mmXWmXmXm1,0],[][]2[241mmXWmXmXm2019/9/413x[0]x[2]x[1]x[3]1111X[0]X[2]X[1]X[3]X1[0]X2[0]X1[1]X2[1]04W14W04W04W2019/9/44点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图144点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]111108W18W28W38W3,2,1,0],[][]4[281mmXWmXmXm3,2,1,0],[][][281mmXWmXmXm2019/9/4154点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]111108W18W28W38W2点DFT2点DFTx[0]x[4]x[2]x[6]114WX11[0]X11[1]X12[0]X12[1]04W2点DFT2点DFT11X21[0]X21[1]X22[0]X22[1]x[1]x[5]x[3]x[7]14W04W1111x[0]x[4]x[2]x[6]28W08W08W08WX11[0]X11[1]X12[0]X12[1]1111x[1]x[5]x[3]x[7]28W08W08W08WX21[0]X21[1]X22[0]X22[1]8点基2时间抽取FFT算法流图2019/9/4基2时间抽取FFT算法16x[0]x[4]x[2]x[6]X[0]X[2]X[1]X[3]111108W08W08Wx[1]x[5]x[3]x[7]X[0]X[2]X[1]X[3]111108W08W08W18W08W38W28W28W28W1111第一级第二级第三级2019/9/4二、按时间抽取的算法特点171.计算速度当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。2log22FNNmLN复数乘法：2logFaNLNN复数加法：222()2()loglog2FFmDFTNNNmFFTNN比较DFT2019/9/4182019/9/4算法的计算复杂度19复乘次数NN2NN2log22019/9/4例.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。5s0.5sDFTxnFFT解：(1)直接利用计算：复乘次数为，复加次数为。DFT2N1NN复乘所需时间626215105105121.31072TNs复加所需时间6260.51010.51051251210.130816TNNs所以直接利用DFT计算所需时间：121.441536TTTs2019/9/420复乘所需时间61262510log2512510log5120.011522NTNs622620.510log0.510512log5120.002304TNNs复加所需时间所以用FFT计算所需时间120.013824TTTs(2)利用计算：复乘次数为，复加次数为。FFT2log2NN2logNN2019/9/421222.倒序排列n0n1n200011011001101倒位序自然序0000000010041001010220101106301100114100101551010113611011177111222102()nnnn0122()nnnn2102()()xnnnnn23倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]010101012019/9/4243.同址运算在同一级蝶形运算中，两信号只参与一次运算。4.蝶距规律24～0NW142NNW02NW12NNW～三、按时间抽取FFT算法的其它形式252019/9/4262019/9/4272019/9/4282019/9/4