按频率抽取的FFT算法PPT学习教案

1、会计学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点点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点DFTN/2点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点DFTN/4点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点点DFTX0X6X2X44点点DFTX1X3X5X7第9页/共16页11X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点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时间抽取和频率抽取FFT算法：第11页/共16页132log