按時間抽取的FFT算法

1、時間抽選法時間抽選法DIT: Decimation-In-Time頻率抽選法頻率抽選法DIF: Decimation-In-Frequency7-2 按按時間抽取的FFT算法一、按時間抽取的算法原理二、按時間抽取的算法特點三、按時間抽取FFT算法的其他形式22022-3-21一、按時間抽取的算法原理設(shè)序列點數(shù) N = 2L，L 為整數(shù)。若不滿足，則補零N為2的整數(shù)冪的FFT算法稱基-2FFT算法。將序列x(n)按n的奇偶分成兩組：3 12221xrx rxrxr0,1,.,/2 1rN2022-3-214 則則x(n)的的DFT: 111000NNNnknknkNNNnnnXkx n Wx n

2、 Wx n Wn為偶數(shù)n為奇數(shù)/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN2022-3-215 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又2022-3-2161212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,

3、/2 1kN 一個一個“蝶形運算蝶形運算”包含包含1次乘法，次乘法，2次加法次加法2022-3-2172022-3-21復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個一個N / 2點點DFT(N / 2)2N / 2 (N / 2 1)兩個兩個N / 2點點DFTN 2 / 2N (N / 2 1)一個蝶形一個蝶形12N / 2個蝶形個蝶形N / 2N總計總計8分解后的運算量：分解后的運算量：運算量減少了近一半運算量減少了近一半22/2/2/2NNN2/2 1/2N NNN2022-3-21N / 2仍為偶數(shù)，進一步分解：N / 2 N / 491314(2 )( )(21)( )xlx lxlxl0,

4、1,.,/41lN13/ 2413/ 24()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 2022-3-21102/2kkNNWW統(tǒng)一系數(shù)：10同理同理：25/ 2625/ 26()()()()()()4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 其中：其中：552( )( )(2 )XkDFT xlDFT xl662( )( )(21)XkDFT xlDFT xl0,1,.,/ 41lN這樣逐級分解，直到這樣逐級分解，直到2點點DFT基2時間抽取FFT算法流圖11N=2xk=x0, x1 1 0002xWxX 1 0 1 12xWxX0

5、x 1 x0X-102W 1 X 1 002xWx2022-3-214點基2時間抽取FFT算法流圖12x0 x2x1x3X10X11X20X212點DFT2點DFT111104W14W02W02WX 0X 1X 2X 31 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm2022-3-21132022-3-214點基2時間抽取FFT算法流圖8點基2時間抽取FFT算法流圖144點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3 , 2 , 1

6、, 0,4281mmXWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm2022-3-21154點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W8點基2時間抽取FFT算法流圖2022-3-21基基2時間抽取時間抽取FFT算法算法16第一級第一級第二級第二級第三級第三級2022-3-21二、按時間抽取的算法特點171.計算速度 當(dāng)N = 2L時，共有L級蝶形，每級N / 2個蝶形，每個蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。2log22FNNmLN復(fù)數(shù)乘法復(fù)數(shù)

7、乘法：2logFaNLNN復(fù)數(shù)加法復(fù)數(shù)加法：222()2()loglog2FFmDFTNNNmFFTNN比較比較DFT 2022-3-21182022-3-21算法的計算復(fù)雜度算法的計算復(fù)雜度19復(fù)乘次數(shù)NN 2NN2log22022-3-21例 .如果一臺通用計算機的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來計算512點的 ，問直接計算需要多少時間，用 運算需要多少時間。 5 s0.5 s DFT x nFFT解：(1)直接利用 計算： 復(fù)乘次數(shù)為 ，復(fù)加次數(shù)為 。 DFT2N1N N 復(fù)乘所需時間 626215 105 105121.31072TNs復(fù)加所需時間 6260.5 1010.5

8、10512512 10.130816TNNs所以直接利用DFT 計算所需時間： 121.441536TTTs2022-3-2120復(fù)乘所需時間 612625 10log25125 10log 5120.011522NTNs 622620.5 10log0.5 10512log 5120.002304TNNs復(fù)加所需時間 所以用 FFT 計算所需時間 120.013824TTTs(2) 利用 計算： 復(fù)乘次數(shù)為 ，復(fù)加次數(shù)為 。 FFT2log2NN2logNN2022-3-2121222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序0000000010041001010220101106301100114100101551010113611011177111222 1 02()nn nn0122()nn n n2 102( )()x nnn n n23倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x011x1110