數(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),因此有:,由于X1m 和X2m隱含有周期性,可得,時(shí)間抽取FFT,基2時(shí)間抽取FFT算法推導(dǎo),基2時(shí)間抽取FFT算法的基本關(guān)系,時(shí)間抽取FFT,基2時(shí)間抽取FFT算法流圖,N=2,xk=x0, x1,4點(diǎn)基2時(shí)間抽取FFT算法流圖,X10,X11,X20,X21,-1,-1,-1,-1,X 0,X 1,X 2,X 3,4點(diǎn)基2時(shí)間抽取FFT算法流圖,8點(diǎn)基2時(shí)間抽取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點(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 =%.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時(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ǔ)單元,x000 x001 x010 x011 x100 x101 x110 x111,x000 x100 x010 x110 x001 x101 x011 x111,自然順序輸入,倒序,變址,xk2k1k0,存儲(chǔ)單元 數(shù)據(jù)不對(duì)換,存儲(chǔ)單元 數(shù)據(jù)對(duì)換,原位運(yùn)算(In-place Computations),原位運(yùn)算,x0 x4 x2 x6 x1 x5 x3 x7,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),輸入序列,存儲(chǔ)單元,第一級(jí)輸出,第二級(jí)輸入,第二級(jí)輸出,第三級(jí)輸入,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),第三級(jí)輸出,時(shí)間抽取FFT,例:已知xk=1,2,3,4,利用基2-FFT算法流圖計(jì)算,1 3 2 4,4,6,-2,2 j,10,-2,-2+2j,-2-2j,DFTxk=,10,-2+2j,-2,-2-2j,例:試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列xk=1, -1, 1, -1, 2, -1, 1,-1的DFT。,解:,根據(jù)基2時(shí)間抽取FFT算法原理,8點(diǎn)序列的DFT Xm可由兩個(gè)4點(diǎn)序列的DFT X1m和X2m表達(dá)。如果按照序列xk序號(hào)的奇偶分解為x1k和 x2k,則存在,其中 x1k=1, 1, 2, 1, x2k=-1, -1, -1,-1 X1m和X2m可通過4點(diǎn)的FFT來計(jì)算。,例:試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列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,例:試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列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,時(shí)間抽取FFT,序列補(bǔ)零,序列插零的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時(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流圖,,,- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 數(shù)字信號(hào) 處理 時(shí)間 抽取 FF
鏈接地址:http://italysoccerbets.com/p-2830482.html