數(shù)字信號處理時間抽取FFT

1、數(shù)字信號處理(Digital Signal Processing) 離散傅里葉變換快速算法(FFT)問題的提出解決問題的思路與方法 基2時間抽取FFT算法基2頻率抽取FFT算法FFT算法的實際應用 實序列的DFT計算，IDFT的快速計算方法時間抽取FFT問題的提出4點序列2，3，3，2 DFT的計算復雜度復數(shù)加法N(N-1)復數(shù)乘法N 2如何提高DFT的運算效率?時間抽取FFT解決問題的思路1. 將長序列DFT分解為短序列的DFT2. 利用旋轉(zhuǎn)因子 的周期性、對稱性、可約性。時間抽取FFT旋轉(zhuǎn)因子 的性質(zhì)(1) 周期性(以N為周期)(2) 對稱性(3) 可約性時間抽取FFT解決問題的方法 將時

2、域序列逐次分解為一組子序列，利用旋轉(zhuǎn)因子的特性，由子序列的DFT來實現(xiàn)整個序列的DFT。 基2時間抽取(Decimation in time)FFT算法 基2頻率抽取(Decimation in frequency)FFT算法時間抽取FFT基2時間抽取FFT算法基2時間抽取FFT算法推導基2時間抽取FFT算法流圖基2時間抽取FFT算法的計算復雜度基2時間抽取FFT算法流圖規(guī)律時間抽取FFT基2時間抽取FFT算法推導時間抽取FFT基2時間抽取FFT算法推導因此有:由于X1m 和X2m隱含有周期性，可得時間抽取FFT基2時間抽取FFT算法流圖N=2xk=x0, x1時間抽取FFT4點基2時間抽取F

3、FT算法流圖x0 x2x1x3X10X11X20X212點DFT2點DFT-1-1-1-1X 0X 1X 2X 3時間抽取FFT4點基2時間抽取FFT算法流圖時間抽取FFT8點基2時間抽取FFT算法流圖4點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-1時間抽取FFT4點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18點基2時間抽取FFT算法流圖時間抽取FFT第一級第

4、二級第三級8點基2時間抽取FFT算法流圖時間抽取FFTFFT算法流圖旋轉(zhuǎn)因子 規(guī)律第二級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為2。第一級的蝶形系數(shù)均為 ，蝶形節(jié)點的距離為1。第三級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為4。第M級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為N /2。時間抽取FFT8點基2時間抽取FFT算法流圖第一級第二級第三級時間抽取FFT算法的計算復雜度復乘次數(shù)復乘次數(shù)NN 2時間抽取FFT原位運算x0 x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)輸入序列存儲單元第一級輸出第二級輸入第二級輸出第三級輸入X10X11X20X21X30X31X40X41A

5、(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X50X51X52X53X60X61X62X63A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X 0X 1X 2X 3X 4X 5X 6X 7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三級輸出時間抽取FFT倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xkk0 xk2 k101x110 x001x101x011x11101010101時間抽取FFT倒序的實現(xiàn)變址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存儲單元x000 x001 x010

6、 x011 x100 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然順序輸入倒序變址xk2k1k0存儲單元數(shù)據(jù)不對換存儲單元數(shù)據(jù)對換時間抽取FFT例：已知xk=1,2,3,4，利用基2FFT算法流圖計算13244 6-2-2 -j10-2-2+2j-2-2jDFTxk=10, -2+2j,-2,-2-2j04W14Wx0 x3x1x2X3X1X2X0-1-1-1-1時間抽取FFT補零,插零序列的DFTx1k=1,2,3,4x2k=1,2,3,4,0,0,0,0 x3k=1,0,2,0,3,0,4,0DFTx1k=10, -2+2j, -2, -2-2jDFTx2k=10, -0.4142-7.2426j, -2+2j, 2.4142-1.2426j, -