按时间抽取的FFT算法

FFT算法分类:时间抽选法

DIT:Decimation-In-Time频率抽选法

DIF:Decimation-In-Frequency§7-2按时间抽取的FFT算法§7-2

按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式22023/9/2一、按时间抽取的算法原理设序列点数N=2L，L为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：32023/9/24则x(n)的DFT:2023/9/25再利用周期性求X(k)的后半部分2023/9/26一个“蝶形运算”包含1次乘法，2次加法2023/9/272023/9/2复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计8分解后的运算量：运算量减少了近一半2023/9/2N/2仍为偶数，进一步分解：N/2N/492023/9/210同理：其中：这样逐级分解，直到2点DFT基2时间抽取FFT算法流图11N=2x[k]={x[0],x[1]}2023/9/24点基2时间抽取FFT算法流图12x[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]2023/9/2132023/9/24点基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-12023/9/2154点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-18点基2时间抽取FFT算法流图2023/9/2基2时间抽取FFT算法16第一级第二级第三级2023/9/2二、按时间抽取的算法特点171.计算速度当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DFT

2023/9/2182023/9/2算法的计算复杂度19复乘次数NN22023/9/2例.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。解：(1)直接利用计算：复乘次数为，复加次数为。

复乘所需时间复加所需时间所以直接利用DFT计算所需时间：2023/9/220复乘所需时间复加所需时间所以用FFT

计算所需时间(2)利用计算：复乘次数为，复加次数为。2023/9/2212.倒序排列n0n1n200011011001101倒位序自然序00000000100410010102201011063011001141001015510101136110111771112223倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]010101012023/9/2

3