按时间抽取的FFT算法

FFT算法分类:时间抽选法

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

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

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

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

复乘所需时间复加所需时间所以直接利用DFT计算所需时间：2025/2/2320复乘所需时间复加所需时间所以用FFT

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

3.同址运算

在同一级蝶形运算中，两信号只参与一次运算。

4.蝶距规律24～～三、按时间抽取FFT算法的其它形式252025/2/23262025/2/23272025/2/23282025/2/239、春去春又回，新桃换旧符。在那桃花盛开的地方，在这醉人芬芳的季节，愿你生活像春天一样阳光，心情像桃花一样美丽，日子像桃子一样甜蜜。2月-252月-25Sunday,February23,202510、人的志向通常和他们的能力成正比例。21:12:1621:12:1621:122/23/20259:12:16PM11、夫学须志也，才须学也，非学无以广才，非志无以成学。2月-2521:12:1621:12Feb-2523-Feb-2512、越是无能的人，越喜欢挑剔别人的错儿。21:12:1621:12:1621:12Sunday,February23,202513、志不立，天下无可成之事。2月-252月-2521:12:1621:12:16February23,202514、ThankyouverymuchfortakingmewithyouonthatsplendidoutingtoLondon.ItwasthefirsttimethatIhadseentheToweroranyoftheotherfamoussights.IfI'dgonealone,Icouldn'thaveseennearlyasmuch,becauseIwouldn'thaveknownmywayabout.。23二月20259:12:16下午21:12:162月-2515、会当凌绝顶，一览众山小。二月259:12下午2月-2521:12February23,202516