按时间抽取的FFT算法

FFT算法分类:时间抽选法

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

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

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

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

复乘所需时间复加所需时间所以直接利用DFT计算所需时间：2026/5/2920复乘所需时间复加所需时间所以用FFT

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

3.同址运算