按时间抽取的FFT算法

按时间抽取的FFT算法FFT算法分类:时间抽选法

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

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

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

2025/3/25192025/3/25算法的计算复杂度20复乘次数NN22025/3/25例.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。解：(1)直接利用计算：复乘次数为，复加次数为。复乘所需时间复加所需时间所以直接利用DFT计算所需时间：2025/3/2521复乘所需时间复加所需时间所以用FFT

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

3.同