1、FFT算法分類:,時間抽選法 DIT: Decimation-In-Time 頻率抽選法 DIF: Decimation-In-Frequency,7-2 按時間抽取的FFT算法,7-2 按時間抽取的FFT算法,一、按時間抽取的算法原理 二、按時間抽取的算法特點 三、按時間抽取FFT算法的其他形式,2,2020/8/10,一、按時間抽取的算法原理,設(shè)序列點數(shù) N = 2L，L 為整數(shù)。 若不滿足，則補零 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,一個“蝶形運算”包含1次乘法，2次加法,2020/8/10,7,2020/8/10,8,分解后的運算量：,運算量減少了近一半,2020/8/10,N / 2仍為偶數(shù)，進一步分解：N / 2 N / 4,9,2020/8/10,10,同理：,其中：,這樣逐級分解，直到2點DFT,基2時間抽取FFT算法流圖,11,N=2,xk=x0, x1,2020/8/10,4點基2時間抽取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點基2時間抽取FFT算法流圖,8點基2時間

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點基2時間抽取FFT算法流圖,2020/8/10,基2時間抽取FFT算法,16,第一級,第二級,第三級,2020/8/10,二、按時間抽取的算法特點,17,1.計算速度 當N = 2L時，共有L級蝶形，每級N / 2個蝶形，每個蝶形有1次復(fù)數(shù)

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