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 nkNNNnnkNNnnkNNnWnxWnxWnxkX12/12010 kNnNNnnkNNnWNnxWnxkX21201202 nkNkNnWNnxnx21120kkNNW12对第二项令n=n-N/2n=n+N/2n:0(N/2)-1n:N/2N-1则 rnNNnWNnxnxrX212022 rXWnxrnNNn12/1120令 r
2、XrXrXrXkX2112212,2,1,0NrN/2点DFT(X(k)的偶次项)nrNNnWNnxnxrX12120212 rnNnNNnWWNnxnx21202 rXWnxrnNNn22/2120N/2点DFT(X(k)的奇次项)2/1Nnxnxnx nNWNnxnxnx2/2nNW nx2/Nnx 2/Nnxnx nNWNnxnx2/即有：(4.3-3)上式的运算关系可以用蝶形表示运算量：一次复乘；两次复加。n=0,1,2,(N/2)-1 kXnxkXnxnxNN22/212/1 kX rXWnxrXrnNNn12/11202 rXWnxrXrnNNn22/212012 同样是利用两个N
3、/2点DFT，合成一个N点DFT。均为N/2点DFT合成N点(4.3-4)即即1NW2NW0NW3NW 0 x 4x 6x 1x 3x 2x 5x 7x 0X 1X 2X 3X 4X 5X 7X 6XDFTN点2DFTN点2例 N=8222222222NNNNNmF 11124211/21/21/200/4NNNnrnrnrNNNnnn NXrxn Wxn Wxn W复乘计算量：2、继续将N/2点DFT分解为两个N/4点DFT。对第二项令n=n-N/4n=n+N/4n:0(N/4)-1n:N/4(N/2)-1 1144411/21/2004NNNnrnrNNnnNXrxn WxnW nrNrN
4、nWNnxnx2/1114041rrNNrNNWW1242/lXlXlXlXrX41311122令l=0,1,2,(N/4)-1 nlNNnWNnxnxlXlX22/111403142 lXWnxnlNNn34/3120则：N/4点DFT(X1(k)的偶次项)l=0,1,2,(N/4)-1 nlNNnWNnxnxlX122/111401412 nlNnNNnWWNnxnx4/2/111404 lXWnxnlNNn44/4140N/4点DFT(X1(k)的奇次项)l=0,1,2,(N/4)-1 4/113Nnxnxnx nNWNnxnxnx2/1144/lXnxlXnxnxNN44/434/31
5、如法炮制，直至最后分解到2点DFT为止。(3)合成N/2点X1(r)即有：同理，X2(r)与X1(r)一样，可再分解为两个N/4点DFT，即有X5(r)、X6(r)。0 x 4x 6x 1x 3x 2x 5x 7x 0X 1X 2X 3X 4X 5X 7X 6X1NW2NW0NW3NW2NW0NW2NW0NW0NW0NW0NW0NW1NW2NW0NW3NW2NW0NW2NW0NW0NW0NW0NW0NW-1-1-1-1-1-1-1-1 02x 12x 22x 32x 01x 11x 21x 31x-1-1-1-1 0 x 4x 6x 1x 3x 2x 5x 7x 0X 1X 2X 3X 4X
6、5X 7X 6XL级级L-1级级第L级蝶形运算如图4.3-5所示。pNW由图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
7、级级L-1级级pNWXL-1(p)XL(p)XL-1(q)XL(q)L级级L-1级级pNWXL-1(p)XL(p)XL-1(q)XL(q)其它形式的频选其它形式的频选FFTFFT。由其它形式的时选FFT转置可以得到其它形式的频选由图4.2-12的转置形式得到如图4.3-7所示另一种形式的频选流图。由此可见，两者计算量相同mF=M(N/2)=(N/2)log2N0NW 0X 1X 2X 3X 4X 5X 7X 6X 0 x 4x 6x 1x 3x 2x 5x 7x1NW2NW0NW3NW2NW0NW2NW0NW0NW0NW0NW图4.3-74.4、IDFT的快速计算方法的快速计算方法IFFT4.
8、4.1、的快速计算方法、的快速计算方法IFFTIDFT的快速计算方法即快速傅里叶反变换，一般可用英文缩写为IFFT。上面所讨论的无论时选还是频选FFT算法均可用于IDFT运算，因为DFT与IDFT运算公式分别为及运算量进一步减少的方法及运算量进一步减少的方法 nkNNnWnx10X(k)=DFTx(n)nkNNkWkXN1011NNWW比较两式可见，只要将，再将结果乘以1/N 就可以用DFT程序计算IDFT。x(n)=IDFTX(k)但因为输入是频域序列X(k)，输出为时域序列 x(n)，1)时选的FFT频选的IFFT；频选的FFT 时选的IFFT。2)为减少有限字长影响，一般 1/N=(1/
9、2)M 可分到M级的运算中去。其基本蝶形为所以pNW21pNW21时选时选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 nkNNkWkXNnx101
10、nkNNknkNNkWkXNWkXNnx101011 kXDFTN1 nkNNkWkXNnxnx101所以，可以IFFT与FFT子程共用。如果希望FFT与IFFT子程序共用，还可以选择下面的方法。因为又因为 nxnxnxkXkXN1DFT取共轭子程序取共轭 对结果再取共轭；访问FFT子程序；乘以1/N。对X(k)取共轭得X*(k)；步骤思路：适当选择FFT与IFFT算法，有可能避免倒序位的算法。处理过的数据。这时DFT与IDFT相当是两个变换的级联。乘以系统的DFT（H(k)），然后再作乘积的IDFT，得到如果只对数据作一次变换，显然在同址计算情况下，要在输入或输出作变址运算。但在许多实际应用
11、中，是将数据的DFT经系统处理后再作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为时选，
12、IFFT必为频4.4.2、运算量进一步减少的方法、运算量进一步减少的方法前面讨论的时选FFT与频选FFT算法，算法简单，编程效率高，得到广泛应用。由前面讨论的FFT算法可知，N=2M 点FFT的复数乘法次数为NM/2。实际运算量是否还能再减少？回答是肯定的。下面介绍以程序的复杂换取运算量减少的方法。1、无需运算的因子旋转因子，如0NW、2/NNW、4/NNW等。在DFT运算中，若jWpN、1，则称其为无关紧要的级蝶形、。由图4.2-6可以看到在第一级蝶形中，只有一种旋转因子因为与这些因子相乘时不用作实际的复数乘法。以时选FFT流图为例，从左到右依次为第一级蝶形、第二10NW，因此不需要复数乘法
13、运算；10NW第二级蝶形有两个无关紧要的旋转因子 jWNN4/、两级不需要复数乘法的运算外，所需实际复数乘法数为22MNmF (4.4-3)所以也不需要复数乘法运算。去除一、二在第三级蝶形有两个无关紧要的旋转因子10NW与4/NNW也不需要复数乘法运算。以此类推，L3时，第L级的两个无关紧要的旋转10NW4/NNW因子与减少复数乘法的次数为2N/2L=N/2L-1。蝶形运算，所以第三级共有2N/23=N/4个蝶形。因为同一旋转因子对应着2M-L=N/2L个从 L=3 到 L=M共减少复数乘法的次数为MLMLLMLNNN21212122122433132/112/1121221211212233
14、3MMNN2232/1122/112212MMNN22N考虑以上这些减少的复数乘法后，这时的复数乘法运算次数为 23222222MNNMNCM实现一次复数乘法，一般需要四次实数乘法，两次实2、减少运算的因子数加法。但当任意复数 a+jb 与2/218/jWNN相乘时，有 bjajbajbaj22221jBAbajba22)(22baAabbaB2222式中，实数加法和两次实数乘法。由式(4.4-6)可见，任意复数与 8/NNW相乘只需要两次8/NNW8/NNW8/NNW8/NNW这样，所有含有的蝶形，减少两次实数乘法。从 L=3 到 L=M级，每级都包含，第 L 级中，最后一级，减少的实数乘法
15、次数与 (4.4-4)式对应2M-L=N/2L个蝶形运算，所以从第三级到相同为(N/2)-2次。3、改进后的实数乘法计算量、改进后的实数乘法计算量考虑所有相关的旋转因子，从实数运算考虑，计算 2223242NMNRM102132MNN=2M点FFT的实数乘法次数为在基2FFT程序中，含有全部旋转因子的，该算法为一类蝶形单元运算；去掉了 1rNW旋转因子的，为二类蝶形单元运算；去掉了 jWrN1rNW、旋转因子的，为三类蝶形单元运算；去掉了 jWrN1rNW、的旋转因子，又对 作了处理的，为四类蝶形单8/NNW元运算。类型越多，编程越复杂。当N较大时，乘法运算的减少乘法次数是一类蝶形单元运算的75%。量是相当可观的。例N=4096时，三类蝶形单元运算的后三种运算也称为多类蝶形单元运算。显然，蝶形单元NmjNmWmN/2sin/2cos实际应用中，旋转因子的生成方法影响 FFT 运算速度。mNW产生旋转因子方法有两种，一种方法是每级运算时直接计算产生，优点是实时运算占用内存少，缺点是运算速度受限。另一种方法是事先计算出所有的过程中查表得到所需系数，优点是运算速度快，缺点，0m(N/2)-1，存放在数组中。在程序执行是要占较多内存。作业1、3、5、7
