數(shù)字信號處理-時間抽取FF.ppt

數(shù)字信號處理 (Digital Signal Processing),信號與系統(tǒng)系列課程組 國家電工電子教學基地,離散傅里葉變換快速算法(FFT),問題的提出 解決問題的思路與方法 基2時間抽取FFT算法 基2頻率抽取FFT算法 FFT算法的實際應(yīng)用 實序列的DFT計算，IDFT的快速計算方法,時間抽取FFT,問題的提出,4點序列2，3，3，2 DFT的計算復雜度,復數(shù)加法,N(N-1),復數(shù)乘法,N 2,如何提高DFT的運算效率?,時間抽取FFT,解決問題的思路,1. 將長序列DFT分解為短序列的DFT,2. 利用旋轉(zhuǎn)因子 的周期性、對稱性、可約性。,旋轉(zhuǎn)因子 的性質(zhì),(1) 周期性,(2) 對稱性,(3) 可約性,時間抽取FFT,解決問題的方法,將時域序列逐次分解為一組子序列，利用旋轉(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算法推導,基2時間抽取FFT算法的基本關(guān)系,時間抽取FFT,基2時間抽取FFT算法流圖,N=2,xk=x0, x1,4點基2時間抽取FFT算法流圖,X10,X11,X20,X21,-1,-1,-1,-1,X 0,X 1,X 2,X 3,4點基2時間抽取FFT算法流圖,8點基2時間抽取FFT算法流圖,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,8點基2時間抽取FFT算法流圖,第一級,第二級,第三級,8點基2時間抽取FFT算法流圖,時間抽取FFT,算法的計算復雜度,復乘次數(shù),時間抽取FFT,計算速度的比較,N=1024*4; x = rand(N,1); tic; y1=fft(x); 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算法流圖旋轉(zhuǎn)因子 規(guī)律,第二級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為2。,第一級的蝶形系數(shù)均為 ，蝶形節(jié)點的距離為1。,第三級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為4。,第M級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為N /2。,倒 序運算(Bit-reverse Computations),倒序的實現(xiàn)變址,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),存儲單元,x000 x001 x010 x011 x100 x101 x110 x111,x000 x100 x010 x110 x001 x101 x011 x111,自然順序輸入,倒序,變址,xk2k1k0,存儲單元 數(shù)據(jù)不對換,存儲單元 數(shù)據(jù)對換,原位運算(In-place Computations),原位運算,x0 x4 x2 x6 x1 x5 x3 x7,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),輸入序列,存儲單元,第一級輸出,第二級輸入,第二級輸出,第三級輸入,X10 X11 X20 X21 X30 X31 X40 X41,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),X50 X51 X52 X53 X60 X61 X62 X63,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),第三級輸出,時間抽取FFT,例：已知xk=1,2,3,4，利用基2-FFT算法流圖計算,1 3 2 4,4,6,-2,2 j,10,-2,-2+2j,-2-2j,DFTxk=,10,-2+2j,-2,-2-2j,例：試利用N=4基2時間抽取的FFT流圖計算8點序列xk=1, -1, 1, -1, 2, -1, 1,-1的DFT。,解：,根據(jù)基2時間抽取FFT算法原理，8點序列的DFT Xm可由兩個4點序列的DFT X1m和X2m表達。如果按照序列xk序號的奇偶分解為x1k和 x2k，則存在,其中 x1k=1, 1, 2, 1， x2k=-1, -1, -1,-1 X1m和X2m可通過4點的FFT來計算。,例：試利用N=4基2時間抽取的FFT流圖計算8點序列xk=1, -1, 1, -1, 2, -1, 1,-1的DFT。,解：,x1k=1, 1, 2, 1,3,-1,2,0,5,1,-1,-1,x10=1 x12=2 x11=1 x13=1,X1m=5,- 1, 1,- 1,例：試利用N=4基2時間抽取的FFT流圖計算8點序列xk=1, -1, 1, -1, 2, -1, 1,-1的DFT。,x2k=-1, -1, -1, -1,X2m=-4, 0,0,0,X1m=5,- 1, 1,- 1,X0=5+(-4)=1,X1= -1+0=-1,X2= 1+0=1,X3= -1+0=-1,X4=5-(-4)=9,X5=-1-0= -1,X6=1-0= 1,X7=-1-0= -1,Xm= 1 -1 1 -1 9 -1 1 -1,時間抽取FFT,序列補零,序列插零的DFT,x1k=1,2,3,4,x2k=1,2,3,4,0,0,0,0,x3k=1,0,2,0,3,0,4,0,DFTx1k=10, -2+2j, -2, -2-2j,DFTx2k=10, -0.4142-7.2426j, -2+2j, 2.4142-1.2426j, -2, 2.4142+1.2426j , -2-2j, -0.4142-7.2426j,DFTx3k=10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j,基2時間抽取FFT算法的基本關(guān)系,基3時間抽取FFT算法的基本關(guān)系,基4時間抽取FFT算法的基本關(guān)系,任意基時間抽取FFT算法,基4時間抽取FFT算法,時間抽取FFT,基4時間抽取FFT算法推導,時間抽取FFT,基4時間抽取FFT算法推導,時間抽取FFT,基4時間抽取FFT算法流圖,時間抽取FFT,算法的計算復雜度,基2時間抽取FFT復乘次數(shù)：,基4時間抽取FFT復乘次數(shù)：,時間抽取FFT,混合基時間抽取FFT算法,混合基時間抽取FFT算法推導 混合基時間抽取FFT算法流圖,時間抽取FFT,混合基時間抽取FFT算法,若序列,的長度可表示為N=pq，將序列,按時間抽取方式分解為p個q點序列,則根據(jù)時間抽取FFT算法原理可得基p時間 抽取FFT算法基本表示式為,分別為其DFT,時間抽取FFT,混合基時間抽取FFT算法,時間抽取FFT,混合基時間抽取FFT算法,，,時間抽取FFT,混合基時間抽取FFT算法,，,時間抽取FFT,混合基時間抽取FFT流圖,，,