ch3_1時間抽取FFT-北京交通大學陳后金教授信號處理課件

1、近代數(shù)字信號處理近代數(shù)字信號處理(Advanced Digital Signal Processing) 電子信息工程學院電子信息工程學院信號與圖像處理研究室4點序列點序列2，3，3，2 DFT的計算復雜度的計算復雜度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點DFT2點DFT111104W14W02W02WX 0X 1X 2X 31 , 0,2241mmXWmXmXm1 , 0,241mmXWmXmXm4點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 71111

4、08W18W28W38W3 , 2 , 1 , 0,4281mmXWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm4點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38WNN2log2復乘次數(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倒倒 序運算序運算(Bit-reverse Computations)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存儲單元存儲單元x000 x001 x010 x011 x1

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

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)第三級輸出例：已知xk=1,2,3,4，利用基2-FFT算法流圖計算DFTkxmX13244 622 j1022+2j22jDFTxk= 10, 2+2j,2,22j04W14Wx0 x3x1x2X3X1X2X01111試利用試利用N=4基基2時間抽取的時間抽取的

8、FFT流圖計算流圖計算8點序列點序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。 根據(jù)基根據(jù)基2時間抽取時間抽取FFT算法原理，算法原理，8點序列的點序列的DFT Xm可由兩個可由兩個4點序列的點序列的DFT X1m和和X2m表達。如果表達。如果按照序列按照序列xk序號的奇偶分解為序號的奇偶分解為x1k和和 x2k，則存在，則存在 3 , 2 , 1 , 04281281mmXWmXmXmXWmXmXmm 其中其中 x1k=1, 1, 2, 1， x2k=-1, -1, -1,-1X1m和和X2m可通過可通過4點的點的FFT來計算。來計算。-1-1j-1-1試利用試利用

9、N=4基基2時間抽取的時間抽取的FFT流圖計算流圖計算8點序列點序列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例：試利用例：試利用N=4基基2時間抽取的時間抽取的FFT流圖計算流圖計算8點序列點序列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序列補零序列補零,序列插零的序列插零的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時間抽取時間抽取FFT算法的基本關系算法的基本關系21mXWmXmXmN基基3時間抽取時間抽取FFT算法的基本關系算法的基本關系3221mXWmXWmXmXmNmN基基4時間抽取時間抽取FFT算法的基本關系算法的基本關系433221mXWmXWmXWmXmXmNmNmN任意基時間抽取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