按頻率抽取的FFT算法PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1按頻率抽取的按頻率抽取的FFT算法算法2第1頁/共16頁3則則x(n)的的DFT:1/2 1100/2( )( )( )( )NNNnknknkNNNnnn NX kx n Wx n Wx n W/2 1/2 1200( )2NNNnknkNNnnNx n Wx nW/2 1/20( )2NNknkNNnNx nx nWW/2 10( )( 1)2NknkNnNx nx nW 0,1,.,1kN/21NNW 第2頁/共16頁4 按按k的奇偶將的奇偶將X(k)分成兩部分：分成兩部分：221krkr0,1,.,/2 1rN/2 120(2 )( )2NnrNnNXrx nx nW/2 1(

2、21)0(21)( )2NnrNnNXrx nx nW/2 1/20( )2NnrNnNx nx nW/2 1/20( )2NnnrNNnNx nx nWW第3頁/共16頁512( )( )2( )( )2nNNx nx nx nNx nx nx nW0,1,.,12Nn 則則X(2r)和和X(2r+1)分別是分別是x1(n)和和x2(n)的的 N / 2點(diǎn)點(diǎn)DFT，記為，記為X1(k)和和X2(k)第4頁/共16頁6x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5

3、)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)1NW0NW2NW3NW第5頁/共16頁77311411/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 313414( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n0,1,.,14Nk 第6頁/共16頁8x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)

4、=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)0/2NW1/2NW第7頁/共16頁90,1,.,14Nk 525626( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n同理：同理：其中：其中：522622/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 第8頁/共16頁 rkNNkWNkxkxrX2/12/02/2 rkNkNNkWWNkxkxrX2/12/02/1212/1 ,0 Nr3NW-1-12NW-1-11NW-1-1

5、0NW-1-1x0 x4x1x5x2x6x3x74點(diǎn)點(diǎn)DFTX0X6X2X44點(diǎn)點(diǎn)DFTX1X3X5X7第9頁/共16頁11X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2點(diǎn)點(diǎn)DFT-1-1-1-12NW0NW-1-1-1-12點(diǎn)點(diǎn)DFT2點(diǎn)點(diǎn)DFT2點(diǎn)點(diǎn)DFT第10頁/共16頁120NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1時(shí)間抽取和頻率抽取FFT算法：第11頁/共16頁132log