按時間抽取的FFT算法講義

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

2、kx n Wx n 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-2-255 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又2022-2-2561212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW

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

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

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

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

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

8、 1010.5 10512512 10.130816TNNs所以直接利用DFT 計算所需時間： 121.441536TTTs2022-2-2521復乘所需時間 612625 10log25125 10log 5120.011522NTNs 622620.5 10log0.5 10512log 5120.002304TNNs復加所需時間 所以用 FFT 計算所需時間 120.013824TTTs(2) 利用 計算： 復乘次數(shù)為 ，復加次數(shù)為 。 FFT2log2NN2logNN222.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序00000000100410010102201011063011001141001015510101136110111771112102()nn n n0 122()nn nn2 102( )()x nnn n n2022-2-2523倒序倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x1