按時間抽取的FFT算法FFT算法分類:時間抽選法

DIT:Decimation-In-Time頻率抽選法

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

按時間抽取的FFT算法一、按時間抽取的算法原理二、按時間抽取的算法特點(diǎn)三、按時間抽取FFT算法的其他形式32025/3/25一、按時間抽取的算法原理設(shè)序列點(diǎn)數(shù)N=2L，L為整數(shù)。若不滿足，則補(bǔ)零N為2的整數(shù)冪的FFT算法稱基-2FFT算法。將序列x(n)按n的奇偶分成兩組：42025/3/255則x(n)的DFT:2025/3/256再利用周期性求X(k)的后半部分2025/3/257一個“蝶形運(yùn)算”包含1次乘法，2次加法2025/3/2582025/3/25復(fù)數(shù)乘法復(fù)數(shù)加法一個N/2點(diǎn)DFT(N/2)2N/2(N/2–1)兩個N/2點(diǎn)DFTN2/2N(N/2–1)一個蝶形12N/2個蝶形N/2N總計(jì)9分解后的運(yùn)算量：運(yùn)算量減少了近一半2025/3/25N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4102025/3/2511同理：其中：這樣逐級分解，直到2點(diǎn)DFT基2時間抽取FFT算法流圖12N=2x[k]={x[0],x[1]}2025/3/254點(diǎn)基2時間抽取FFT算法流圖13x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2點(diǎn)DFT2點(diǎn)DFT-1-1-1-1X

[0]X

[1]X

[2]X

[3]2025/3/25142025/3/254點(diǎn)基2時間抽取FFT算法流圖8點(diǎn)基2時間抽取FFT算法流圖154點(diǎn)DFT4點(diǎn)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點(diǎn)DFT4點(diǎn)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點(diǎn)基2時間抽取FFT算法流圖2025/3/25基2時間抽取FFT算法17第一級第二級第三級2025/3/25二、按時間抽取的算法特點(diǎn)181.計(jì)算速度當(dāng)N=2L時，共有L級蝶形，每級N/2個蝶形，每個蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT

2025/3/25192025/3/25算法的計(jì)算復(fù)雜度20復(fù)乘次數(shù)NN22025/3/25例.如果一臺通用計(jì)算機(jī)的速度為平均每次復(fù)乘，每次復(fù)加，用它來計(jì)算512點(diǎn)的，問直接計(jì)算需要多少時間，用運(yùn)算需要多少時間。解：(1)直接利用計(jì)算：復(fù)乘次數(shù)為，復(fù)加次數(shù)為。復(fù)乘所需時間復(fù)加所需時間所以直接利用DFT計(jì)算所需時間：2025/3/2521復(fù)乘所需時間復(fù)加所需時間所以用FFT

計(jì)算所需時間(2)利用計(jì)算：復(fù)乘次數(shù)為，復(fù)加次數(shù)為。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.同