數字信號處理-時間抽取FF.ppt

《數字信號處理-時間抽取FF.ppt》由會員分享，可在線閱讀，更多相關《數字信號處理-時間抽取FF.ppt（41頁珍藏版）》請在裝配圖網上搜索。

數字信號處理 (Digital Signal Processing),,,信號與系統(tǒng)系列課程組 國家電工電子教學基地,離散傅里葉變換快速算法(FFT),問題的提出 解決問題的思路與方法 基2時間抽取FFT算法 基2頻率抽取FFT算法 FFT算法的實際應用—— 實序列的DFT計算，IDFT的快速計算方法,,時間抽取FFT,問題的提出,4點序列{2，3，3，2} DFT的計算復雜度,復數加法,N(N-1),復數乘法,N 2,如何提高DFT的運算效率?,時間抽取FFT,解決問題的思路,1. 將長序列DFT分解為短序列的DFT,2. 利用旋轉因子 的周期性、對稱性、可約性。,旋轉因子 的性質,(1) 周期性,(2) 對稱性,(3) 可約性,,時間抽取FFT,解決問題的方法,將時域序列逐次分解為一組子序列，利用旋轉因子的特性，由子序列的DFT來實現整個序列的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算法推導,因此有:,由于X1[m] 和X2[m]隱含有周期性，可得,時間抽取FFT,基2時間抽取FFT算法推導,基2時間抽取FFT算法的基本關系,,時間抽取FFT,基2時間抽取FFT算法流圖,N=2,x[k]={x[0], x[1]},4點基2時間抽取FFT算法流圖,,,,,,,,,,,,,,,,,,,,,X1[0],X1[1],X2[0],X2[1],-1,-1,-1,-1,X [0],X [1],X [2],X [3],,,4點基2時間抽取FFT算法流圖,,8點基2時間抽取FFT算法流圖,,,,,,,,,,,,,,,,,,,,,,,,,X1[0],X1[1],X1[2],X1[3],X2[0],X2[1],X2[2],X2[3],X [0],X [1],X [2],X [3],X [4],X [5],X [6],X [7],-1,-1,-1,-1,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,X1[0],X1[1],X1[2],X1[3],X2[0],X2[1],X2[2],X2[3],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,算法的計算復雜度,復乘次數,時間抽取FFT,計算速度的比較,N=1024*4; x = rand(N,1); tic; y1=fft(x); t1=toc; fprintf(\nFFT time =%.6e\n,t1) ; tic; y2=dftmtx(N)*x; t2=toc; fprintf(DFT time =%.6e\n,t2); fprintf(FFT/DFT =%.6f%%\n,t1*100/t2); stem(abs(y1-y2), r. ) ;,基2時間抽取FFT算法流圖,,,第一級,第二級,第三級,,FFT算法流圖旋轉因子 規(guī)律,第二級的蝶形系數為 ，蝶形節(jié)點的距離為2。,第一級的蝶形系數均為 ，蝶形節(jié)點的距離為1。,第三級的蝶形系數為 ，蝶形節(jié)點的距離為4。,第M級的蝶形系數為 ，蝶形節(jié)點的距離為N /2。,,倒 序運算(Bit-reverse Computations),倒序的實現——變址,,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),存儲單元,x[000] x[001] x[010] x[011] x[100] x[101] x[110] x[111],x[000] x[100] x[010] x[110] x[001] x[101] x[011] x[111],自然順序輸入,倒序,變址,,,x[k2k1k0],存儲單元 數據不對換,存儲單元 數據對換,,,,,,,原位運算(In-place Computations),原位運算,,x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7],A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),輸入序列,存儲單元,第一級輸出,第二級輸入,第二級輸出,第三級輸入,X1[0] X1[1] X2[0] X2[1] X3[0] X3[1] X4[0] X4[1],A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),X5[0] X5[1] X5[2] X5[3] X6[0] X6[1] X6[2] X6[3],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,例：已知x[k]={1,2,3,4}，利用基2-FFT算法流圖計算,1 3 2 4,4,6,-2,2 j,10,-2,-2+2j,-2-2j,DFT{x[k]}=,{10,,-2+2j,,-2,,-2-2j},例：試利用N=4基2時間抽取的FFT流圖計算8點序列x[k]={1, -1, 1, -1, 2, -1, 1,-1}的DFT。,解：,,根據基2時間抽取FFT算法原理，8點序列的DFT X[m]可由兩個4點序列的DFT X1[m]和X2[m]表達。如果按照序列x[k]序號的奇偶分解為x1[k]和 x2[k]，則存在,,其中 x1[k]={1, 1, 2, 1}， x2[k]={-1, -1, -1,-1} X1[m]和X2[m]可通過4點的FFT來計算。,例：試利用N=4基2時間抽取的FFT流圖計算8點序列x[k]={1, -1, 1, -1, 2, -1, 1,-1}的DFT。,解：,,,,,x1[k]={1, 1, 2, 1},3,-1,2,0,5,1,-1,-1,x1[0]=1 x1[2]=2 x1[1]=1 x1[3]=1,X1[m]={5,- 1, 1,- 1},例：試利用N=4基2時間抽取的FFT流圖計算8點序列x[k]={1, -1, 1, -1, 2, -1, 1,-1}的DFT。,,,x2[k]={-1, -1, -1, -1},X2[m]={-4, 0,0,0},X1[m]={5,- 1, 1,- 1},X[0]=5+(-4)=1,X[1]= -1+0=-1,X[2]= 1+0=1,X[3]= -1+0=-1,X[4]=5-(-4)=9,X[5]=-1-0= -1,X[6]=1-0= 1,X[7]=-1-0= -1,X[m]= {1 -1 1 -1 9 -1 1 -1},時間抽取FFT,序列補零,序列插零的DFT,x1[k]={1,2,3,4},x2[k]={1,2,3,4,0,0,0,0},x3[k]={1,0,2,0,3,0,4,0},DFT{x1[k]}={10, -2+2j, -2, -2-2j},DFT{x2[k]}={10, -0.4142-7.2426j, -2+2j, 2.4142-1.2426j, -2, 2.4142+1.2426j , -2-2j, -0.4142-7.2426j},DFT{x3[k]}={10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j},基2時間抽取FFT算法的基本關系,基3時間抽取FFT算法的基本關系,基4時間抽取FFT算法的基本關系,任意基時間抽取FFT算法,基4時間抽取FFT算法,時間抽取FFT,基4時間抽取FFT算法推導,,,時間抽取FFT,基4時間抽取FFT算法推導,,,時間抽取FFT,基4時間抽取FFT算法流圖,,時間抽取FFT,算法的計算復雜度,基2時間抽取FFT復乘次數：,,基4時間抽取FFT復乘次數：,時間抽取FFT,混合基時間抽取FFT算法,,,混合基時間抽取FFT算法推導 混合基時間抽取FFT算法流圖,時間抽取FFT,混合基時間抽取FFT算法,,,若序列,的長度可表示為N=pq，將序列,按時間抽取方式分解為p個q點序列,則根據時間抽取FFT算法原理可得基p時間 抽取FFT算法基本表示式為,分別為其DFT,時間抽取FFT,混合基時間抽取FFT算法,,,,時間抽取FFT,混合基時間抽取FFT算法,,,,，,時間抽取FFT,混合基時間抽取FFT算法,,,,，,時間抽取FFT,混合基時間抽取FFT流圖,,,,，,,