济南大学机械工程学院工程测试与信息处理课件 第十六课.ppt

既然这样分解是有效的，由于N=2M，因而N/2仍是偶数，可以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的子序列。 这种方法的每一步分解，都是按输入序列在时间上的次序是属于偶数还是属于奇数来分解为两个更短的子序列，所以称为“按时间抽取法”。 对N=2M的一般情况， 第L级的旋转因子为： 设序列 经时域抽选(倒序)后，存入数组 。 如果蝶形运算的两个输入数据相距B个点，应用原位计算，则第L级蝶形运算可表示成如下形式： nk可以用以下表达式来替换 将式（3-34）代入式（3-33），可得 如果定义: n=0, 1, …, N-1 图 4-8 倒序程序框图 3. WNp的确定及运算规律 N点DIT-FFT运算流图中，每级都有N/2个蝶形，每个蝶形乘以因子 ， 称其为旋转因子。为完成运算， 必须找出 的变换规律。 用L表示从左向右的运算级数（L=1, 2 …M）， 可观察到：第L级共有2 L-1个不同的旋转因子。 时的各级旋转因子表示如下： 按这两个式子确定第L级运算的旋转因子。 . DIT-FFT程序框图 图 4-9 DIT-FFT运算程序框图 4.3.4 按时间抽取的FFT算法的其他形式流图 显然，对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的，所得最后结果都是x(n)的DFT的正确结果，只是数据的提取和存放的次序不同而已。这样就可得到按时间抽取的FFT算法的若干其他形式流图。 将图4-5中和x(4)水平相连的所有节点和x(1)水平相连的所有节点位置对调，再将和x(6)水平相连的所有节点与和x(3)水平相连的所有节点对调，其余诸节点保持不变，可得图4-10的流图。 图4-10与图4-5的蝶形相同，运算量也一样，不同点是： 图 4-10 时间抽取、 输入自然顺序、 输出倒位序的FFT流图 ① 数据存放的方式不同，图4-5是输入倒位序、输出自然顺序，图4-10是输入自然顺序、输出倒位序； ②取用系数的顺序不同，图4-5的最后一列是按 的顺序取用系数，且其前一列所用系数是后一列所用系数中具有偶数幂的那些系数（例如 ）；图4-10是最后一列是按 的顺序取用系数，且其前一列所用系数是后一列所用系数的前一半， 这种流图是最初由库利和图基给出的时间抽取法。 经过简单变换，也可得输入与输出都是按自然顺序排列的流图以及其他各种形式的流图 。 3.4 按频率抽取（DIF）的基 -2 FFT算法 3.4.1 算法原理 仍设序列点数为N=2M，M为正整数。在把输出X(k)按k的奇偶分组之前，先把输入序列按前一半、后一半分开（不是按偶数、 奇数分开）， 把N点DFT写成两部分。 k=0, 1, …, N-1 式中，用的是 ，而不是 ，因而这并不是N/2点DFT。 由于 ，故 ，可得 k=0, 1, …, N-1 （3-23） 当k为偶数时，(-1)k=1；k为奇数时，(-1)k=-1。因此，按k的奇偶可将X(k)分为两部分， 依次分解。 （3-27） 图 4-11 频率抽取法蝶形运算单元 这样，我们就把一个N点DFT按k的奇偶分解为两个N/2点的DFT了。 N=8时，上述分解过程示于图4-12。 与时间抽取法的推导过程一样，由于N=2M，N/2仍是一个偶数，因而可以将每个N/2点DFT的输出再分解为偶数组与奇数组，这就将N/2点DFT进一步分解为两个N/4 点DFT。 这两个N/4点DFT的输入也是先将N/2点DFT的输入上下对半分开后通过蝶形运算而形成的。 图 4-12 按频率抽取的第一次分解 图 4-14 按频率抽取的第二次分解 这样的分解可以一直进行到第M次（N=2M），第M次实际上是做两点DFT，它只有加减运算。 然而，为了有统一的运算结构，仍然用一个系数为WN0的蝶形运算来表示， 这N/2个两点DFT的N个输出就是x(n)的N点DFT的结果X(k)。 图4-15表示一个N=8 完整的按频率抽取的基-2 FFT运算结构。 图 4-15 按频率抽取的FFT（N=8