按时间抽取的FFT算法.pptVIP

*FFT算法分类:时间抽选法 DIT:Decimation-In-Time频率抽选法 DIF:Decimation-In-Frequency§7-2按时间抽取的FFT算法按时间抽取的算法原理按时间抽取的算法特点按时间抽取FFT算法的其他形式7-2按时间抽取的FFT算法设序列点数N=2L，L为整数。01若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。02将序列x(n)按n的奇偶分成两组：03一、按时间抽取的算法原理则x(n)的DFT:再利用周期性求X(k)的后半部分一个“蝶形运算”包含1次乘法，2次加法复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计分解后的运算量：运算量减少了近一半N/2仍为偶数，进一步分解：N/2N/4同理：其中：这样逐级分解，直到2点DFT基2时间抽取FFT算法流图01N=202x[k]={x[0],x[1]}034点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT-1-1-1-1X[0]X[1]X[2]X[3]4点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图4点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-18点基2时间抽取FFT算法流图4点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第一级第二级第三级基2时间抽取FFT算法二、按时间抽取的算法特点1.计算速度当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DFT算法的计算复杂度复乘次数NN2复加所需时间例.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。解：(1)直接利用计算：复乘次数为，复加次数为。复乘所需时间所以直接利用DFT计算所需时间：(2)利用计算：复乘次数为，复加次数为。复加所需时间复乘所需时间所以用FFT计算所需时间*