1、FFT算法分類:時間抽選法DIT: Decimation-In-Time頻率抽選法DIF: Decimation-In-Frequency7-2 按時間抽取的FFT算法17-2 按時間抽取的FFT算法一、按時間抽取的算法原理二、按時間抽取的算法特點三、按時間抽取FFT算法的其他形式2022/7/192一、按時間抽取的算法原理設(shè)序列點數(shù) N = 2L，L 為整數(shù)。若不滿足，則補零N為2的整數(shù)冪的FFT算法稱基-2FFT算法。將序列x(n)按n的奇偶分成兩組：2022/7/193則x(n)的DFT:2022/7/194再利用周期性求X(k)的后半部分2022/7/195一個“蝶形運算”包含1次乘法

2、，2次加法2022/7/1962022/7/197復數(shù)乘法復數(shù)加法一個N / 2點DFT(N / 2)2N / 2 (N / 2 1)兩個N / 2點DFTN 2 / 2N (N / 2 1)一個蝶形12N / 2個蝶形N / 2N總計分解后的運算量：運算量減少了近一半2022/7/198N / 2仍為偶數(shù)，進一步分解：N / 2 N / 42022/7/199同理：其中：這樣逐級分解，直到2點DFT基2時間抽取FFT算法流圖N=2xk=x0, x12022/7/19114點基2時間抽取FFT算法流圖x0 x2x1x3X10X11X20X212點DFT2點DFT-1-1-1-1X 0X 1X

3、2X 32022/7/19124點基2時間抽取FFT算法流圖2022/7/19138點基2時間抽取FFT算法流圖4點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-12022/7/19144點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18點基2時間抽取FFT算法流圖2022/7/1915基2時間抽取FFT算法第一級第二級第三級2022/7/1916二、按時間抽取的算法

4、特點1.計算速度 當N = 2L時，共有L級蝶形，每級N / 2個蝶形，每個蝶形有1次復數(shù)乘法2次復數(shù)加法。復數(shù)乘法：復數(shù)加法：比較DFT 2022/7/19172022/7/1918算法的計算復雜度復乘次數(shù)NN 22022/7/1919例 .如果一臺通用計算機的速度為平均每次復乘 ，每次復加 ，用它來計算512點的 ，問直接計算需要多少時間，用 運算需要多少時間。 解：(1)直接利用 計算： 復乘次數(shù)為 ，復加次數(shù)為 。 復乘所需時間 復加所需時間 所以直接利用DFT 計算所需時間： 2022/7/1920復乘所需時間 復加所需時間 所以用 FFT 計算所需時間 (2) 利用 計算： 復乘次數(shù)為 ，復加次數(shù)為 。 2022/7/19212.倒序排列n0n1n200011011001101倒位序 自然序0000000010041001010220101106301100114100101551010113611011177111倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xkk0 xk2 k101x110 x001x101x011x111010101012022/7/1923 3.同址運算 在同一級蝶形運算中，兩信號只