ch3_1時(shí)間抽取FFT-北京交通大學(xué)陳后金教授信號(hào)處理課件_第1頁(yè)
ch3_1時(shí)間抽取FFT-北京交通大學(xué)陳后金教授信號(hào)處理課件_第2頁(yè)
ch3_1時(shí)間抽取FFT-北京交通大學(xué)陳后金教授信號(hào)處理課件_第3頁(yè)
ch3_1時(shí)間抽取FFT-北京交通大學(xué)陳后金教授信號(hào)處理課件_第4頁(yè)
ch3_1時(shí)間抽取FFT-北京交通大學(xué)陳后金教授信號(hào)處理課件_第5頁(yè)
已閱讀5頁(yè)，還剩36頁(yè)未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、近代數(shù)字信號(hào)處理近代數(shù)字信號(hào)處理(Advanced Digital Signal Processing) 電子信息工程學(xué)院電子信息工程學(xué)院信號(hào)與圖像處理研究室4點(diǎn)序列點(diǎn)序列2，3，3，2 DFT的計(jì)算復(fù)雜度的計(jì)算復(fù)雜度1, 1 , 0,10NmWkxmXkmNNk10233200000 NNNNWWWWXj12332 1 3210 NNNNWWWWX0233226420 NNNNWWWWXj1233239630 NNNNWWWWXkmNW946434046444240434241404040404044WWWWWWWWWWWWWWWWDj1j11111j1j11111kmNWkmNNmkNmN

2、kNWWW)()(mkNkmNWWmkNNmkNWW2nmknNmkNWW為整數(shù)nNWWnmknNmkN/,/12, 1 , 0 122Nrrxrxkx 122mXmXmXkmNNkWkxmX10mrNNrrmNNrWrxWrx)12(12/0212/0 122rmNNrmNrmNNrWrxWWrx2/12/02/12/0 122mrNNrmrNNrWrxmXWrxmX2/12/022/12/01 12 2記21mXWmXmXmN2/22/1NmXWNmXNmXNmN121 , 0Nm因此有因此有:21mXWmXmN由于X1m 和X2m隱含有周期性，可得mNNWmXWmXNmXmX11112/

3、2011j-1-j21mXWmXmXmN2/21mXWmXNmXmN 121 , 0 NmN=2xk=x0, x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWx 1 01111 1 0 xxXXx0 x2x1x3X10X11X20X212點(diǎn)DFT2點(diǎn)DFT111104W14W02W02WX 0X 1X 2X 31 , 0,2241mmXWmXmXm1 , 0,241mmXWmXmXm4點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 71111

4、08W18W28W38W3 , 2 , 1 , 0,4281mmXWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm4點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38WNN2log2復(fù)乘次數(shù)NN 2NN2log2N=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

5、=%.6en,t2);fprintf(FFT/DFT =%.6f%n,t1*100/t2);stem(abs(y1-y2), r. ) ; PNW4/0,NNNWW0NW8/38/28/0,NNNNNNNWWWW) 12/(10,NNNNWWWx0 x4x2x6X0X2X1X3111108W08W08Wx1x5x3x7X4X6X5X7111108W08W08W18W08W38W28W28W28W1111倒倒 序運(yùn)算序運(yùn)算(Bit-reverse Computations)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存儲(chǔ)單元存儲(chǔ)單元x000 x001 x010 x011 x1

6、00 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然順序輸入倒序變址變址xk2k1k0210kkkxkxkk 存儲(chǔ)單元數(shù)據(jù)不對(duì)換kk 存儲(chǔ)單元數(shù)據(jù)對(duì)換x0 x4x2x6X0X2X1X3111108W08W08Wx1x5x3x7X4X6X5X7111108W08W08W18W08W38W28W28W28W1111原位運(yùn)算原位運(yùn)算(In-place Computations)x0 x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)輸入序列 存儲(chǔ)單元存儲(chǔ)單元第一級(jí)輸出第二級(jí)輸入第二級(jí)輸出第三級(jí)輸入

7、X10X11X20X21X30X31X40X41A(1)A(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)第三級(jí)輸出例：已知xk=1,2,3,4，利用基2-FFT算法流圖計(jì)算DFTkxmX13244 622 j1022+2j22jDFTxk= 10, 2+2j,2,22j04W14Wx0 x3x1x2X3X1X2X01111試?yán)迷嚴(yán)肗=4基基2時(shí)間抽取的時(shí)間抽取的

8、FFT流圖計(jì)算流圖計(jì)算8點(diǎn)序列點(diǎn)序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。 根據(jù)基根據(jù)基2時(shí)間抽取時(shí)間抽取FFT算法原理，算法原理，8點(diǎn)序列的點(diǎn)序列的DFT Xm可由兩個(gè)可由兩個(gè)4點(diǎn)序列的點(diǎn)序列的DFT X1m和和X2m表達(dá)。如果表達(dá)。如果按照序列按照序列xk序號(hào)的奇偶分解為序號(hào)的奇偶分解為x1k和和 x2k，則存在，則存在 3 , 2 , 1 , 04281281mmXWmXmXmXWmXmXmm 其中其中 x1k=1, 1, 2, 1， x2k=-1, -1, -1,-1X1m和和X2m可通過(guò)可通過(guò)4點(diǎn)的點(diǎn)的FFT來(lái)計(jì)算。來(lái)計(jì)算。-1-1j-1-1試?yán)迷嚴(yán)?/p>

9、N=4基基2時(shí)間抽取的時(shí)間抽取的FFT流圖計(jì)算流圖計(jì)算8點(diǎn)序列點(diǎn)序列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例：試?yán)美涸嚴(yán)肗=4基基2時(shí)間抽取的時(shí)間抽取的FFT流圖計(jì)算流圖計(jì)算8點(diǎn)序列點(diǎn)序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。 x2k=-1, -1, -1, -1 X2m=-4, 0,0,03, 2, 1 , 04281281 mmXWmXmXmXWmXmXmm X1m=5,- 1, 1,- 1X0=5+

10、(-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序列補(bǔ)零序列補(bǔ)零,序列插零的序列插零的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, 22jDFTx2k=10, 0.41427.2426j, 2+2j, 2.41421.2426j, 2, 2.41421.2426j , 22j, 0.41427.2426jDFTx3k=10, 2+2j, 2,

11、 22j, 10, 2+2j, 2, 22j基基2時(shí)間抽取時(shí)間抽取FFT算法的基本關(guān)系算法的基本關(guān)系21mXWmXmXmN基基3時(shí)間抽取時(shí)間抽取FFT算法的基本關(guān)系算法的基本關(guān)系3221mXWmXWmXmXmNmN基基4時(shí)間抽取時(shí)間抽取FFT算法的基本關(guān)系算法的基本關(guān)系433221mXWmXWmXWmXmXmNmNmN任意基時(shí)間抽取FFT算法433221mXWmXWmXWmXmXmNmNmN jj4/3 4/2jj4/ 433221433221433221mXWmXWmXWmXNmXmXWmXWmXWmXNmXmXWmXWmXWmXNmXmNmNmNmNmNmNmNmNmNmNmNmNNWmX

12、WmXWmXWmXNmXNmXNmXmX3423201j1j11111j1j111114/34/24/1j-1-jmNmNmNNWmXWmXWmXWmXNmXNmXNmXmX3423201j1j11111j1j111114/34/24/ 32 1 0j1j11111j1j11111 32 1 0iiiiiiiixxxxXXXX0NWmNW2mNW3mNW 4 /1NmXmX2mX3mX4mXmX 4 / 2NmX 4 / 3NmX111111111111jjjjx0 x8x12x1x5x9x13x2x4x6x10 x14x3x7x11x15360246X0X2X3X4X5X6X7X8X1X9X10X11X12X13X14X15901230X4mX3mX1mX2m0000NN2log2NNNNMN24log83) 1(log43) 1(43kx,21kxkxkxp) 1(3221mXW

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論