04数字信号处理2

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/2~N-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合成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级蝶形运算如图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(q)其它形式的频选FFTFFT。由其它形式的时选FFT转置可以得到其它形式的频选由图4.2-12的转置形式得到如图4.3-7所示另一种形式的频选流图。由此可见，两者计算量相同mF=M(N/2)=(N/2)log2N4.4、IDFT的快速计算方法IFFT4.4.1、的快速计算方法IFFTIDFT的快速计算方法即快速傅里叶反变换，一般可用英文缩写为IFFT。上面所讨论的无论时选还是频选FFT算法均可用于IDFT运算，因为DFT与IDFT运算公式分别为及运算量进一步减少的方法X(k)=DFT[x(n)]比较两式可见，只要将，再将结果乘以1/N就可以用DFT程序计算IDFT。x(n)=IDFT[X(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、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经系统处理后再作IDFT得到处理后的数据。例如，用DFT实现FIRDF时，对输入的一段数据作DFT，例如，对DFT我们选图4.2-12的时选法，（是输入为自然对IDFT我们选图4.4-3的IFFT频选法，（是输入为倒都不需做倒序运算，运算框图如图4.4-4所示。序位的，输出位自然顺序的）。这样，正、反两次变换序位、输出倒序位的）。将系统的H(k)也按倒序位存储；图4.2-12(时选FFT)图4.4-3(频选IFFT)图4.4-4选；反之，FFT为频选，IFFT必为时选。注意：系统序位要一致的话，FFT为时选，IFFT必为频4.4.2、运算量进一步减少的方法前面讨论的时选FFT与频选FFT算法，算法简单，编程效率高，得到广泛应用。由前面讨论的FFT算法可知，N=2M点FFT的复数乘法次数为NM/2。实际运算量是否还能再减少？回答是肯定的。下面介绍以程序的复杂换取运算量减少的方法。1、无需运算的因子级蝶形、…。由图4.2-6可以看到在第一级蝶形中，只有一种旋转因子因为与这些因子相乘时不用作实际的复数乘法。以时选FFT流图为例，从左到右依次为第一级蝶形、第二，因此不需要复数乘法运算；第二级蝶形有两个无关紧要的旋转因子、两级不需要复数乘法的运算外，所需实际复数乘法数为(4.4-3)所以也不需要复数乘法运算。去除一、二也不需要复数乘法运算。以此类推，L≥3时，第L级的两个无关紧要的旋转因子与减少复数乘法的次数为2N/2L=N/2L-1。蝶形运算，所以第三级共有2N/23=N/4个蝶形。因为同一旋转因子对应着2M-L=N/2L个从L=3到L=M共减少复数乘法的次数为考虑以上这些减少的复数乘法后，这时的复数乘法运算次数为实现一次复数乘法，一般需要四次实数乘法，两次实2、减少运算的因子数加法。但当任意复数a+jb与相乘时，有式中，实数加法和两次实数乘法。从L=3到L=M级，每级都包含，第L级中，最后一级，减少的实数乘法次数与(4.4-4)式对应2M-L=N/2L个蝶形运算，所以从第三级到相同为(N/2)-2次。3、改进后的实数乘法计算量考虑所有相关的旋转因子，从实数运算考虑，计算N=2M点FFT的实数乘法次数为在基2FFT程序中，含有全部旋转因子的，该算法为一类元运算。类型越多，编程越复杂。当N较大时，乘法运算的减少乘法次数是一类蝶形单元运算的75%。量是相当可观的。例N=4096时，三类蝶形单元运算的后三种运算也称为多类蝶形单元运算。显然，蝶形单元实际应用中，旋转因子的生成方法影响FFT运算速度。产生旋转因子方法有两种，一种方法是每级运算时直接计算产生，优点是实时运算占用内存少，缺点是运算速度受限。另一种方法是事先计算出所有的过程中查表得到所需系数，优点是运算速度快，缺点，0≤m≤(N/2)-1，存放在数组中。在程序执行是要占较多内存。作业1、3、5、7