按時(shí)間抽取的FFT算法講義(PPT 28頁(yè)).ppt

1、FFT算法分類:,時(shí)間抽選法 DIT: Decimation-In-Time 頻率抽選法 DIF: Decimation-In-Frequency,7-2 按時(shí)間抽取的FFT算法,7-2 按時(shí)間抽取的FFT算法,一、按時(shí)間抽取的算法原理 二、按時(shí)間抽取的算法特點(diǎn) 三、按時(shí)間抽取FFT算法的其他形式,2,2020/8/10,一、按時(shí)間抽取的算法原理,設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。 若不滿足，則補(bǔ)零 N為2的整數(shù)冪的FFT算法稱基-2FFT算法。 將序列x(n)按n的奇偶分成兩組：,3,2020/8/10,4,則x(n)的DFT:,2020/8/10,5,再利用周期性求X(k)的后半部分,

2、2020/8/10,6,一個(gè)“蝶形運(yùn)算”包含1次乘法，2次加法,2020/8/10,7,2020/8/10,8,分解后的運(yùn)算量：,運(yùn)算量減少了近一半,2020/8/10,N / 2仍為偶數(shù)，進(jìn)一步分解：N / 2 N / 4,9,2020/8/10,10,同理：,其中：,這樣逐級(jí)分解，直到2點(diǎn)DFT,基2時(shí)間抽取FFT算法流圖,11,N=2,xk=x0, x1,2020/8/10,4點(diǎn)基2時(shí)間抽取FFT算法流圖,12,X10,X11,X20,X21,-1,-1,-1,-1,X 0,X 1,X 2,X 3,2020/8/10,13,2020/8/10,4點(diǎn)基2時(shí)間抽取FFT算法流圖,8點(diǎn)基2時(shí)間

3、抽取FFT算法流圖,14,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,2020/8/10,15,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,8點(diǎn)基2時(shí)間抽取FFT算法流圖,2020/8/10,基2時(shí)間抽取FFT算法,16,第一級(jí),第二級(jí),第三級(jí),2020/8/10,二、按時(shí)間抽取的算法特點(diǎn),17,1.計(jì)算速度 當(dāng)N = 2L時(shí)，共有L級(jí)蝶形，每級(jí)N / 2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)

4、乘法2次復(fù)數(shù)加法。,復(fù)數(shù)乘法：,復(fù)數(shù)加法：,比較DFT,2020/8/10,18,2020/8/10,算法的計(jì)算復(fù)雜度,19,2020/8/10,例 .如果一臺(tái)通用計(jì)算機(jī)的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來(lái)計(jì)算512點(diǎn)的 ，問(wèn)直接計(jì)算需要多少時(shí)間，用 運(yùn)算需要多少時(shí)間。,復(fù)乘所需時(shí)間,復(fù)加所需時(shí)間,所以直接利用DFT 計(jì)算所需時(shí)間：,2020/8/10,20,復(fù)乘所需時(shí)間,復(fù)加所需時(shí)間,所以用 FFT 計(jì)算所需時(shí)間,(2) 利用 計(jì)算： 復(fù)乘次數(shù)為 ，復(fù)加次數(shù)為 。,2020/8/10,21,2.倒序排列,22,23,倒序,k,0,k,1,k,2,2020/8/10,3.同址運(yùn)算 在同一級(jí)蝶形運(yùn)算中，兩信號(hào)只參與一次運(yùn)算。 4.蝶距規(guī)律,24,三、按時(shí)間抽