1、數字信號處理方式-時間抽取FFT算法離散傅里葉變換快速算法(FFT)問題的提出解決問題的思路與方法 基2FFT算法基2頻率抽取FFT算法FFT算法的實際應用 實序列的DFTIDFT的快速計算方法問題的提出4點序列2，3，3，2 DFT的計算復雜度復數加法N(N-1)復數乘法N 2如何提高DFT的運算效率?解決問題的思路1. 將長序列DFT分解為短序列的DFT2. 利用旋轉因子 的周期性、對稱性、可約性。旋轉因子 的性質(1) 周期性(2) 對稱性(3) 可約性解決問題的方法 將時域序列逐次分解為一組子序列，利用旋轉因子的特性，由子序列的DFT來實現整個序列的DFT。 基2時間抽取(Decima

2、tion in time)FFT算法 基2頻率抽取(Decimation in frequency)FFT算法基2時間抽取FFT算法基2時間抽取FFT算法推導基2時間抽取FFT算法流圖基2時間抽取FFT算法的計算復雜度基2時間抽取FFT算法流圖規律基2時間抽取FFT算法推導基2時間抽取FFT算法推導因此有:由于X1m 和X2m隱含有周期性，可得基2時間抽取FFT算法推導1j-1-j基2時間抽取FFT算法的根本關系基2時間抽取FFT算法流圖N=2xk=x0, x14點基2時間抽取FFT算法流圖x0 x2x1x3X10X11X20X212點DFT2點DFT-1-1-1-1X 0X 1X 2X 34

3、點基2時間抽取FFT算法流圖8點基2時間抽取FFT算法流圖4點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-14點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18點基2時間抽取FFT算法流圖第一級第二級第三級8點基2時間抽取FFT算法流圖算法的計算復雜度復乘次數復乘次數NN 2計算速度的比較N=1024*4;x = rand(N,1);tic; y1=fft(x);

4、t1=toc; fprintf(nFFT time =%.6en,t1) ;tic; y2=dftmtx(N)*x; t2=toc;fprintf(DFT time =%.6en,t2);fprintf(FFT/DFT =%.6f%n,t1*100/t2);stem(abs(y1-y2), r. ) ; 基2時間抽取FFT算法流圖第一級第二級第三級FFT算法流圖旋轉因子 規律第二級的蝶形系數為 ，蝶形節點的距離為2。第一級的蝶形系數均為 ，蝶形節點的距離為1。第三級的蝶形系數為 ，蝶形節點的距離為4。第M級的蝶形系數為 ，蝶形節點的距離為N /2。倒 序運算(Bit-reverse Compu

5、tations)倒序的實現變址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存儲單元x000 x001 x010 x011 x100 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然順序輸入倒序變址xk2k1k0存儲單元數據不對換存儲單元數據對換原位運算(In-place Computations)原位運算x0 x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)輸入序列存儲單元第一級輸出第二級輸入第二級輸出第三級輸入X10X11X20X21X30X31X40X41A(1)A(

6、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)第三級輸出例：xk=1,2,3,4，利用基2-FFT算法流圖計算13244 6-22 j10-2-2+2j-2-2jDFTxk=10, -2+2j,-2,-2-2j04W14Wx0 x3x1x2X3X1X2X0-1-1-1-1例：試利用N=4基2時間抽取的FFT流圖計算8點序列xk=1, -1, 1, -1, 2, -1,

7、 1,-1的DFT。解： 根據基2時間抽取FFT算法原理，8點序列的DFT Xm可由兩個4點序列的DFT X1m和X2m表達。如果按照序列xk序號的奇偶分解為x1k和 x2k，那么存在 其中 x1k=1, 1, 2, 1， x2k=-1, -1, -1,-1X1m和X2m可通過4點的FFT來計算。例：試利用N=4基2時間抽取的FFT流圖計算8點序列xk=1, -1, 1, -1, 2, -1, 1,-1的DFT。解： x1k=1, 1, 2, 13-12051-1-1x10=1x12=2x11=1x13=1 X1m=5,- 1, 1,- 1例：試利用N=4基2時間抽取的FFT流圖計算8點序列x

8、k=1, -1, 1, -1, 2, -1, 1,-1的DFT。 x2k=-1, -1, -1, -1 X2m=-4, 0,0,0 X1m=5,- 1, 1,- 1X0=5+(-4)=1X1= -1+0=-1X2= 1+0=1X3= -1+0=-1X4=5-(-4)=9X5=-1-0= -1X6=1-0= 1X7=-1-0= -1Xm= 1 -1 1 -1 9 -1 1 -1序列補零,序列插零的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.

9、2426j, -2+2j, 2.4142-1.2426j, -2, 2.4142+1.2426j , -2-2j, -0.4142-7.2426jDFTx3k=10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j基2時間抽取FFT算法的根本關系基3時間抽取FFT算法的根本關系基4時間抽取FFT算法的根本關系任意基時間抽取FFT算法基4時間抽取FFT算法1j-1-j基4時間抽取FFT算法推導基4時間抽取FFT算法推導基4時間抽取FFT算法流圖算法的計算復雜度基2時間抽取FFT復乘次數：基4時間抽取FFT復乘次數：混合基時間抽取FFT算法 混合基時間抽取FFT算法推導