§7-3-按频率抽取的FFT算法

1、一、按频率抽取的算法原理二、按频率抽取的算法特点三、与按时间抽取算法的对称性1一、按频率抽取的算法原理设序列点数 N = 2L，L 为整数。若不满足，则补零将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半23 则则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 4 按按k的奇偶将

2、的奇偶将X(k)分成两部分：分成两部分：221krkr0,1,.,/2 1rN/2 120(2 )( )2NnrNnNXrx nx nW/ 2 1(21)0(21)( )2NnrNnNXrx nxnW/ 2 1/ 20( )2NnrNnNx nx nW/2 1/20( )2NnnrNNnNx nx nWW令512( )( )2( )( )2nNNx nx nx nNxnx nx nW0,1,.,12Nn 则则X(2r)和和X(2r+1)分别是分别是x1(n)和和x2(n)的的 N / 2点点DFT，记为记为X1(k)和和X2(k)6x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2

3、(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)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)1NW0NW2NW3NW7N /2仍为偶数，进一步分解：N /2 N /47311411/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 313414( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n0,1,.,14N

4、k 8x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=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逐级分解，直到2点DFT90,1,.,14Nk 525626( )(2 )( )( )(21)( )XkXkDFT x nXkXkDFT x n同理：同理：其中：其中：522622/2( )( )(/4)( )( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn rkNNkWNkxkxrX2/12/0

5、2/2 rkNkNNkWWNkxkxrX2/12/02/1212/1 ,0 Nr3NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X711X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT120NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X

6、3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1时间抽取和频率抽取FFT算法：二、按频率抽取的算法特点131.计算速度 当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每个蝶形有1次复数乘法2次复数加法。2log22FNNmLN复数乘法复数乘法：2logFaNLNN复数加法复数加法：142.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒置顺序的。其整序规则与按时间抽取算法是完全一致的。14 3.同址运算该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律其蝶形系数的分布规律与按时间抽取算法是完全对称的。15三、与按时间抽取算法的对