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

《數(shù)字信號(hào)處理-時(shí)間抽取FF.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)字信號(hào)處理-時(shí)間抽取FF.ppt（41頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

數(shù)字信號(hào)處理 (Digital Signal Processing),,,信號(hào)與系統(tǒng)系列課程組 國家電工電子教學(xué)基地,離散傅里葉變換快速算法(FFT),問題的提出 解決問題的思路與方法 基2時(shí)間抽取FFT算法 基2頻率抽取FFT算法 FFT算法的實(shí)際應(yīng)用—— 實(shí)序列的DFT計(jì)算，IDFT的快速計(jì)算方法,,時(shí)間抽取FFT,問題的提出,4點(diǎn)序列{2，3，3，2} DFT的計(jì)算復(fù)雜度,復(fù)數(shù)加法,N(N-1),復(fù)數(shù)乘法,N 2,如何提高DFT的運(yùn)算效率?,時(shí)間抽取FFT,解決問題的思路,1. 將長序列DFT分解為短序列的DFT,2. 利用旋轉(zhuǎn)因子 的周期性、對(duì)稱性、可約性。,旋轉(zhuǎn)因子 的性質(zhì),(1) 周期性,(2) 對(duì)稱性,(3) 可約性,,時(shí)間抽取FFT,解決問題的方法,將時(shí)域序列逐次分解為一組子序列，利用旋轉(zhuǎn)因子的特性，由子序列的DFT來實(shí)現(xiàn)整個(gè)序列的DFT。,基2時(shí)間抽取(Decimation in time)FFT算法,基2頻率抽取(Decimation in frequency)FFT算法,時(shí)間抽取FFT,基2時(shí)間抽取FFT算法,,,基2時(shí)間抽取FFT算法推導(dǎo) 基2時(shí)間抽取FFT算法流圖 基2時(shí)間抽取FFT算法的計(jì)算復(fù)雜度 基2時(shí)間抽取FFT算法流圖規(guī)律,時(shí)間抽取FFT,基2時(shí)間抽取FFT算法推導(dǎo),時(shí)間抽取FFT,基2時(shí)間抽取FFT算法推導(dǎo),因此有:,由于X1[m] 和X2[m]隱含有周期性，可得,時(shí)間抽取FFT,基2時(shí)間抽取FFT算法推導(dǎo),基2時(shí)間抽取FFT算法的基本關(guān)系,,時(shí)間抽取FFT,基2時(shí)間抽取FFT算法流圖,N=2,x[k]={x[0], x[1]},4點(diǎn)基2時(shí)間抽取FFT算法流圖,,,,,,,,,,,,,,,,,,,,,X1[0],X1[1],X2[0],X2[1],-1,-1,-1,-1,X [0],X [1],X [2],X [3],,,4點(diǎn)基2時(shí)間抽取FFT算法流圖,,8點(diǎn)基2時(shí)間抽取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點(diǎn)基2時(shí)間抽取FFT算法流圖,,,,第一級(jí),第二級(jí),第三級(jí),8點(diǎn)基2時(shí)間抽取FFT算法流圖,,時(shí)間抽取FFT,算法的計(jì)算復(fù)雜度,復(fù)乘次數(shù),時(shí)間抽取FFT,計(jì)算速度的比較,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時(shí)間抽取FFT算法流圖,,,第一級(jí),第二級(jí),第三級(jí),,FFT算法流圖旋轉(zhuǎn)因子 規(guī)律,第二級(jí)的蝶形系數(shù)為 ，蝶形節(jié)點(diǎn)的距離為2。,第一級(jí)的蝶形系數(shù)均為 ，蝶形節(jié)點(diǎn)的距離為1。,第三級(jí)的蝶形系數(shù)為 ，蝶形節(jié)點(diǎn)的距離為4。,第M級(jí)的蝶形系數(shù)為 ，蝶形節(jié)點(diǎn)的距離為N /2。,,倒 序運(yùn)算(Bit-reverse Computations),倒序的實(shí)現(xiàn)——變址,,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),存儲(chǔ)單元,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],存儲(chǔ)單元 數(shù)據(jù)不對(duì)換,存儲(chǔ)單元 數(shù)據(jù)對(duì)換,,,,,,,原位運(yùn)算(In-place Computations),原位運(yùn)算,,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),輸入序列,存儲(chǔ)單元,第一級(jí)輸出,第二級(jí)輸入,第二級(jí)輸出,第三級(jí)輸入,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),第三級(jí)輸出,時(shí)間抽取FFT,例：已知x[k]={1,2,3,4}，利用基2-FFT算法流圖計(jì)算,1 3 2 4,4,6,-2,2 j,10,-2,-2+2j,-2-2j,DFT{x[k]}=,{10,,-2+2j,,-2,,-2-2j},例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1, -1, 1, -1, 2, -1, 1,-1}的DFT。,解：,,根據(jù)基2時(shí)間抽取FFT算法原理，8點(diǎn)序列的DFT X[m]可由兩個(gè)4點(diǎn)序列的DFT X1[m]和X2[m]表達(dá)。如果按照序列x[k]序號(hào)的奇偶分解為x1[k]和 x2[k]，則存在,,其中 x1[k]={1, 1, 2, 1}， x2[k]={-1, -1, -1,-1} X1[m]和X2[m]可通過4點(diǎn)的FFT來計(jì)算。,例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列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},例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列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},時(shí)間抽取FFT,序列補(bǔ)零,序列插零的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時(shí)間抽取FFT算法的基本關(guān)系,基3時(shí)間抽取FFT算法的基本關(guān)系,基4時(shí)間抽取FFT算法的基本關(guān)系,任意基時(shí)間抽取FFT算法,基4時(shí)間抽取FFT算法,時(shí)間抽取FFT,基4時(shí)間抽取FFT算法推導(dǎo),,,時(shí)間抽取FFT,基4時(shí)間抽取FFT算法推導(dǎo),,,時(shí)間抽取FFT,基4時(shí)間抽取FFT算法流圖,,時(shí)間抽取FFT,算法的計(jì)算復(fù)雜度,基2時(shí)間抽取FFT復(fù)乘次數(shù)：,,基4時(shí)間抽取FFT復(fù)乘次數(shù)：,時(shí)間抽取FFT,混合基時(shí)間抽取FFT算法,,,混合基時(shí)間抽取FFT算法推導(dǎo) 混合基時(shí)間抽取FFT算法流圖,時(shí)間抽取FFT,混合基時(shí)間抽取FFT算法,,,若序列,的長度可表示為N=pq，將序列,按時(shí)間抽取方式分解為p個(gè)q點(diǎn)序列,則根據(jù)時(shí)間抽取FFT算法原理可得基p時(shí)間 抽取FFT算法基本表示式為,分別為其DFT,時(shí)間抽取FFT,混合基時(shí)間抽取FFT算法,,,,時(shí)間抽取FFT,混合基時(shí)間抽取FFT算法,,,,，,時(shí)間抽取FFT,混合基時(shí)間抽取FFT算法,,,,，,時(shí)間抽取FFT,混合基時(shí)間抽取FFT流圖,,,,，,,