数字信号处理2课件

1、4.3 基2频率抽取 FFT算法 1、将N点DFT分解为两个N/2点DFT序列基础上。4.3 .1 基2频率抽取 FFT算法础上；频选法FFT建立在把X(k)分解成越来越短的子做法：将x(n)分成前后两段时选FFT建立在把将x(n)分解成越来越短的子序列基N = 2M对第二项令n=n-N/2n=n+N/2n:0(N/2)-1n : N/2N-1则令N/2点DFT(X(k)的偶次项)N/2点DFT(X(k)的奇次项)即有：(4.3-3)上式的运算关系可以用蝶形表示运算量：一次复乘；两次复加。n=0,1,2, (N/2)-1 同样是利用两个N/2点DFT，合成一个N点DFT。 均为N/2点DFT合

2、成N点(4.3-4)即例 N=8复乘计算量：2、继续将N/2点DFT分解为两个N/4点DFT。 对第二项令n=n-N/4n=n+N/4n:0(N/4)-1n : N/4(N/2)-1令l=0,1,2, (N/4)-1则：N/4点DFT(X1(k)的偶次项)l=0,1,2, (N/4)-1N/4点DFT(X1(k)的奇次项)l=0,1,2, (N/4)-1如法炮制，直至最后分解到2点DFT为止。(3)合成N/2点X1(r)即有：同理， X2(r)与X1(r)一样，可再分解为两个N/4点DFT ，即有X5(r)、X6(r) 。-1-1-1-1-1-1-1-1-1-1-1-1L级L-1级第L级蝶形运

3、算如图4.3-5所示。由图4.3-5可以看到频选FFT运算规律有以下几点二、运算规律计算量：复乘 mF=M(N/2)=(N/2)log2NXL-1(p)XL(p)XL-1(q)XL(q)1、同址计算计算。因为每个节点与前列的节点平行对应，所以是同址2、变址输出后，要经过变址运算再输出以保证输出的正确。输入是自然顺序，输出是码位倒序的，所以计算完以3、与时选蝶形转置频选的蝶形与时选蝶形互为转置关系，所以总的时选法与频选法互为转置关系。例图4.2-6转置图4.3-4。时选蝶形频选蝶形L级L-1级XL-1(p)XL(p)XL-1(q)XL(q)L级L-1级XL-1(p)XL(p)XL-1(q)XL(

4、q)其它形式的频选FFTFFT。由其它形式的时选FFT转置可以得到其它形式的频选由图4.2-12的转置形式得到如图4.3-7所示另一种形式的频选流图。由此可见，两者计算量相同mF=M(N/2)=(N/2)log2N图4.3-74.4、 IDFT的快速计算方法IFFT4.4.1、的快速计算方法IFFTIDFT的快速计算方法即快速傅里叶反变换，一般可用英文缩写为IFFT。上面所讨论的无论时选还是频选FFT算法均可用于IDFT运算，因为DFT与IDFT运算公式分别为及运算量进一步减少的方法X (k)=DFTx(n)比较两式可见，只要将，再将结果乘以1/N 就可以用DFT程序计算IDFT。x(n) =

5、IDFTX(k)但因为输入是频域序列X (k ) ，输出为时域序列 x(n) ，1)时选的FFT频选的IFFT；频选的FFT 时选的IFFT。2)为减少有限字长影响，一般 1/N = (1/2)M 可分到M级的运算中去。其基本蝶形为所以时选IFFT蝶形频选IFFT蝶形1/21/2L级XL(p)XL(q)L级XL(p)XL(q)L-1级XL-1(p)XL-1(q)L-1级XL-1(p)XL-1(q)流图的FFT、IFFT计算均为同址的。4.3-7，所以其反变换也对应这几个常用的流图。这几个每个蝶形的运算量：两次复乘；两次复加。总的计算量：因为最常用的FFT算法的流图是4.2-6、4.2-12、

6、4.3-4、共有M级，每级N/2个蝶形。mF=M(N/2)2=MN=Nlog2NaF=M(N/2)2=MN=Nlog2N所以， 可以IFFT与FFT子程共用。如果希望FFT与IFFT子程序共用，还可以选择下面的方法。因为又因为 对结果再取共轭； 访问FFT子程序； 乘以1/N。 对X(k)取共轭得X*(k) ；步骤思路：适当选择FFT与IFFT算法，有可能避免倒序位的算法。处理过的数据。这时DFT与IDFT相当是两个变换的级联。乘以系统的DFT（H(k)），然后再作乘积的IDFT，得到如果只对数据作一次变换，显然在同址计算情况下，要在输入或输出作变址运算。但在许多实际应用中，是将数据的DFT经

7、系统处理后再作IDFT得到处理后的数据。例如，用DFT实现FIR DF时，对输入的一段数据作DFT，例如，对DFT我们选图4.2-12的时选法， （是输入为自然对IDFT我们选图4.4-3的IFFT频选法， （是输入为倒都不需做倒序运算，运算框图如图4.4-4所示。序位的，输出位自然顺序的）。这样，正、反两次变换序位、输出倒序位的）。将系统的H(k)也按倒序位存储；出顺序IDFT入顺序出倒序DFT入倒序倒序存FIR DF 图4.2-12(时选FFT)图4.4-3(频选IFFT)图4.4-4选；反之，FFT为频选，IFFT必为时选。注意：系统序位要一致的话，FFT为时选，IFFT必为频4.4.2

8、、运算量进一步减少的方法前面讨论的时选FFT与频选FFT算法，算法简单，编程效率高，得到广泛应用。由前面讨论的FFT算法可知，N = 2M 点FFT的复数乘法次数为NM/2 。实际运算量是否还能再减少？回答是肯定的。下面介绍以程序的复杂换取运算量减少的方法。1、无需运算的因子旋转因子，如、等。 在DFT运算中，若，则称其为无关紧要的级蝶形、。由图4.2-6可以看到在第一级蝶形中，只有一种旋转因子因为与这些因子相乘时不用作实际的复数乘法。以时选FFT流图为例，从左到右依次为第一级蝶形、第二，因此不需要复数乘法运算；第二级蝶形有两个无关紧要的旋转因子 、两级不需要复数乘法的运算外，所需实际复数乘法

9、数为 (4.4-3) 所以也不需要复数乘法运算。去除一、二在第三级蝶形有两个无关紧要的旋转因子与也不需要复数乘法运算。 以此类推，L3时，第L级的两个无关紧要的旋转因子与减少复数乘法的次数为2N / 2L = N/2L-1 。蝶形运算，所以第三级共有2N / 23 = N/4个蝶形。因为同一旋转因子对应着2M-L = N/2L个从 L=3 到 L = M共减少复数乘法的次数为考虑以上这些减少的复数乘法后，这时的复数乘法运算次数为实现一次复数乘法，一般需要四次实数乘法，两次实2、减少运算的因子数加法。但当任意复数 a+jb 与相乘时，有 式中，实数加法和两次实数乘法。 由式(4.4-6) 可见，

10、任意复数与 相乘只需要两次这样，所有含有的蝶形，减少两次实数乘法。从 L=3 到 L = M级，每级都包含，第 L 级中，最后一级，减少的实数乘法次数与 (4.4-4)式对应2M-L = N/2L个蝶形运算，所以从第三级到相同为 (N/2) - 2次。 3、改进后的实数乘法计算量考虑所有相关的旋转因子，从实数运算考虑，计算N = 2M点FFT的实数乘法次数为在基2FFT程序中，含有全部旋转因子的，该算法为一类蝶形单元运算；去掉了 旋转因子的，为二类蝶形单元运算；去掉了 、旋转因子的，为三类蝶形单元运算；去掉了 、的旋转因子，又对 作了处理的，为四类蝶形单元运算。 类型越多，编程越复杂。当N较大时，乘法运算的减少乘法次数是一类蝶形单元运算的75%。量是相当可观的。例N=4096时，三类蝶形单元运算的后三种运算也称为多类蝶形单元运算。显然