令 得到
上面两式所表示的是N/2的DFT。
在实际计算中，首先形成序列g(n)和h(n)，然后计算h(n)WNn，最后分 别计算g(n) 和h(n)WNn的N/2点DFT，便得到偶数输出点和奇数输出点 的DFT。计算流程图如图3. 24所示。
由于N是2的整数幂，所以N/2仍然是偶数。这样，可以将N/2点DFT 的输出再分为偶数组和奇数组，也就是将N/2点的DFT计算进一步分 解为两个N/4点的DFT计算，其推导过程如下。 将g(n)分为前后两组，得到
图中用n表示自然顺序的标号，用l表示码位倒置的标号。当l=n时， x(n)和x(l)不必互相调换。当l≠n时， 必须将x(l)和x(n)互相调换，但只 能调换一次，为此必须规定每当l>n时，要将x(l)和x(n)相互调换，即 把原来存放x(n)的存储单元中的数据调入存储x(l)的存储单元中，而 把原来存储x(l)的存储单元中的数据调入到存储x(n)的存储单元中。 这样，按自然序输入的数据x(n)经过变址计算后变成了码位倒 置的排列顺序，便可进入第一级的蝶形运算。
3. 5. 3 蝶形、同址和变址计算 1. 蝶形计算 任何一个N为2的整数幂(即N=2M)的DFT，都可以通过M次分解，最 后成为2点的 DFT来计算。M次分解构成了从x(n)到X(k)的M级迭代计 算，每级由N/2个蝶形组成。图3.20表示了蝶形的一般形式表示。 其输入和输出之间满足下列关系：
从上式可以看出完成一个蝶形计 算需一次复数乘法和两次复数加法。 因此，完成N点的时间抽选FFT计 算的总运算量为
大多数情况下复数乘法所花的时间最多，因此下面ቤተ መጻሕፍቲ ባይዱ以复数乘 法的计算次数为例来与直接计算进行比较。 直接计算DFT需要的乘法次数为αD=N2，于是有
例如，当N=1024时，则： 205，即直接计算DFT所需复数乘法 次数约为FFT的205倍。显然，N越大，FFT的速度优势越大。 表3. 2列出了不同N值所对应的两种计算方法的复数乘法次数和 它们的比值。
蝶形运算的特点是，首先每一个蝶形运算都需要两个输入数 据，计算结果也是两个数据，与其它结点的数据无关，其它蝶形 运算也与这两结点的数据无关、因此，一个蝶形 运算一旦计算完 毕，原输入数据便失效了。这就意味着输出数据可以立即使用原 输 人数据结点所占用的内存。原来的数据也就消失了。输出、输 人数据利用同一内存单 元的这种蝶形计算称为同位(址)计算。 可以看出， 每一级的蝶形的输入与输出在运算前后可以存储在 同一地址(原来位置上)的存储单元中，这种同址运算的优点是可以 节省存储单元，从而降低对计算机存储量的要求或降低硬件实现 的成本。
因为
所以
(3.66)
按照式(3.65)和式(3.66)可画出图3．15所示的信号流程图。
式(3.65)和式(3.66)把原来N点DFT的计算分解成两个N/2点DFT的计 算。照此可进一 步把每个N/2点DFT的计算再各分解成两个N/4点 DFT的计算。具体说来，是把{x(0)，x(2)，x(4)，x(6)}和{x(1)，x(3)， x(5)，x(7)}分为{x(0)，x(4) | x(2)，x(6)}和{x(1)，x(5) | x(3)，x(7)}。这样， 原信号序列被分成{x(0)，x(4) | x(2)，x(6) I x(1)，x(5) I x(3)，x(7)}4个2项 信号。G(k)和H(k)分别计算如下:
3. 5. 2 时间抽选基2FFT算法(库里—图基算法) 这种算法简称为时间抽选FFT算法，其基本出发点是，利用旋 转因子WNk的对称性和周期性，将一个大的DFT分解成一些逐次 变小的DFT来计算。 分解过程遵循两条规则： ①对时间进行偶奇分解； ②对频率进行前后分解。 设N＝2M，M为正整数。为了推导方便，取N＝23＝8，即离散时间 信号为
2．同址(原位)计算 图3. 19包含log2N级迭代运算，每级由N/2个蝶形计算构成。蝶形计 算的优点是可以进行所谓同址或原位计算。 现在来考察第一级的计算规律。设将输入x(0)，x(4)，x(2)，x(6)， x(1)，x(5)，x(3)，x(7)分别存入计算机的存储单元M(1), M(2), M(3),…， M(7)和M(8)中。首先，存储单元M(1)和M(2)中的数据x(0)和x(4)进入运 算器并进行蝶形运算，流图中各蝶形的输入量或输出量是互不相 重的，任何一个蝶形的二个输入量经蝶形运算后，便失去了利用 价值，不再需要保存。这样，蝶形运算后的结果便可以送到M(1)和 M(2)存储起来。类似地，M(3)和M(4)中的x(2)和x(6)进入运算器进行蝶 形运算后的结果也被送回 到M(3)和M(4)保存，等等。第二级运算与 第一级类似，不过，M(1)和M(3)存储单元中的数 据进行蝶形运算后 的结果被送回M(1)和M(3)保存，M(2)和M(4)中的数据进行蝶形运算 后送回M(2)和M(4)保存，等等。这样一直到最后一级的最后一个蝶 形运算完成。
(3.67)
(3.68)
(3.69)
(3.70) 这样，用式(3.67)～(3.70)4个公式就可计算图3.15中的两组N/2点 DFT。图3.16所示的是其中一组G(k)的计算。
将图3.16与图3.15所示的信号流程图合并，便得到图3.17所示的信 号流程图。
因为N=8，所以上图中N/4点的DFT就是2点的DFT，不能再分解了。
FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换 逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这 一原理产生了许多不同的算法，但它们在计算速度上均取得了 大致相当的改善。 在本章中我们集中讨论两类基本的FFT算法。 第一类 称为按时间抽取(Decimation-in-Time)的基2FFT算法，它 的命名来自如下事实：在把原计算安排成较短变换的过程中， 序列x(n)(通常看作是一个时间序列)可逐次分解为较短的子序列。 第二类称为按频率抽取(Decimation-in-Frequency)的基2FFT算法， 在这类算法中是将离散傅里叶变换系数序列X(k)分解为较短的 子序列。 前面两种算法特别适用于N等于2的幂的情况。 对于N为合数的情况，本章也将介绍两种处理方法。
在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。 DFT的定义
其中
将DFT定义式展开成方程组
将方程组写成矩阵形式
用向量表示
用复数表示：
从矩阵形式表示可以看出，由于计算一个X(k)值需要N次复乘法和 (N-1)次复数加法，因而计算N个X(k)值，共需N2次复乘法和N(N-1)次 复加法。每次复乘法包括4次实数乘法和2次实数加法，每次复加 法包括2次实数加法，因此计算N点的DFT共需要4N2次实数乘法和 (2N2+2N·(N-1))次实数加法。当N很大时，这是一个非常大的计算量。 FFT算法主要利用了WNk的两个性质： (1)对称性，即 (2)周期性，即 r为任意整数。
第03章 离散傅里叶变换及其快 速算法
邹江 zoujiang@
3. 5 快速傅里叶变换(FFT)
3.5.1 DFT的计算量 离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信 号的频谱、功率谱和线性卷积等。但是，如果使用定义式(3.20)来 直接计算DFT，当N很大时，即使使用高速计算机，所花的时间也 太多。因此，如何提高计算DFT的速度，便成了重要的研究课题。 1965年库利 (Cooley)和图基(Tukey)在前人的研究成果的基础上提出了 快速计算DFT的算法，之后，又出现了各种各样快速计算DFT的方 法，这些方法统称为快速傅里叶变换(Fast Fourier Transform)，简称为 FFT。FFT的出现，使计算DFT的计算量减少了两个数量级，从而成 为数字信号处理强有力的工具。 快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法。它是 DSP领域中的一项重大突破，它考虑了计算机和数字硬件实现的约 束条件、研究了有利于机器操作的运算结构，使DFT的计算时间缩 短了1~2个数量级，还有效地减少了计算所需的存储容量，FFT技术 的应用极大地推动了DSP的理论和技术的发展。
最后介绍一下时间抽选FFT算法的另外一些形式的流程图。对于任 何流程图，只要保持 各节点所连支路及其传输系数不变，则不论 节点位置怎样排列，所得到的流程图总是等效的，因而都能得到 DFT的正确结果，只是数据的提取和存储次序不同而已。 把图3. 19中与x(4)水平相邻的所有节点和与x(1)水平相邻的所有节 点交换，把与x(6)水平相邻的所有节点和与 x(3)水平相邻的所有节点 交换，而与x(2)、x(5)和x(7)水平相邻各节点位置不变，就可以从图3. 19得到图3.22。图3.22与图3.19的区别只是节点的排列不同，而支路 传输比，即WN的 各次幂保持不变。显然图3.22所示流程图的输入是 正序(自然顺序)排列的，输出是码位倒置 排列的，所以输出要进行 变址计算。图3. 22所示的流程图相当于最初由库利和图基给出的时 间抽选算法。
3．变址计算 从图3. 19所示的流程图看出，同址计算要求输入x(n)是“混序” 排列的。所谓输入为“混 序”，并不是说输入是杂乱无章的，实 际上它是有规律的。如果输入x(n)的序号用二进制码来 表示，就可 以发现输入的顺序恰好是正序输入的“码位倒置”，表3. 3列出了 这种规律。
在实际运算中，按码位倒置顺序输入数据x(n)，特别当N较大时， 是很不方便的。因此，数据总是按自然顺序输入存储，然后通过 “变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换 的程序可用图3. 21来说明。
另一种形式的流程图是将节点排列成输入 和输出两者都是 正序排列，但这类流程图不能进行同址计算，因而需要两列 长度为N的复数存储器。
3.5.4 频率抽选基2FFT算法 频率抽选基2FFT算法简称为频率抽选，它的推导过程遵循两个 规则：①对时间前后分；②对频率偶奇分。 设N＝2M，M为正整数。为推导方便，取N=23＝8。 首先，根据规则(1)，将x(n)分成前一半和后一半，即 x(n)＝{x(0), x(1), x(2), x(3), I x(4), x(5), x(6), x(7)} 这样