按频率抽取的FFT算法.pptx

一、按频率抽取的算法原理设序列点数 N=2L，L 为整数。若不满足，则补零将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半1第1页/共16页2则x(n)的DFT:第2页/共16页3 按k的奇偶将X(k)分成两部分：第3页/共16页令4 则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N/2点DFT，记为X1(k)和X2(k)第4页/共16页5x1(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)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)第5页/共16页6N/2仍为偶数，进一步分解：N/2 N/46第6页/共16页7x3(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)第7页/共16页逐级分解，直到2点DFT8同理：其中：第8页/共16页3NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点DFTX0X6X2X44点DFTX1X3X5X7第9页/共16页10X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点DFT-1-1-1-12NW0NW-1-1-1-12点DFT2点DFT2点DFT第10页/共16页110NW1NW2NW3NW-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页二、按频率抽取的算法特点121.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数乘法：复数加法复数加法：无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率抽取算法无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率抽取算法这两种这两种FFTFFT算法是完全等价的。算法是完全等价的。第12页/共16页132.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒置顺序的。其整序规则与按时间抽取算法是完全一致的。13第13页/共16页 3.同址运算该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律其蝶形系数的分布规律与按时间抽取算法是完全对称的。14第14页/共16页三、与按时间抽取算法的对称性二者具有完全对称的蝶距规律蝶形结构和运算流图也都是完全对称的需要的复乘和复加次数也相同频率抽取法运算流图是时间抽取法运算流图的转置，若知道其中一个，应用转置关系就可以得到另一个。15第15页/共16页16感谢您的观看！第16页/共16页