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)周期性，即FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这一原理产生了许多不同的算法，但它们在计算速度上均取得了大致相当的改善。在本章中我们集中讨论两类基本的FFT算法。第一类称为按时间抽取(Decimation-in-Time)的基2FFT算法，它的命名来自如下事实：在把原计算安排成较短变换的过程中，序列x(n)(通常看作是一个时间序列)可逐次分解为较短的子序列。第二类称为按频率抽取(Decimation-in-Frequency)的基2FFT算法，在这类算法中是将离散傅里叶变换系数序列X(k)分解为较短的子序列。前面两种算法特别适用于N等于2的幂的情况。对于N为合数的情况，本章也将介绍两种处理方法。3.5.2时间抽选基2FFT算法(库里—图基算法)根据DFT的定义按照规则(2)，将X(k)分成前后两组，即按照式(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)Ix(1)，x(5)Ix(3)，x(7)}4个2项信号。G(k)和H(k)分别计算如下:(3.69)将图3.16与图3.15所示的信号流程图合并，便得到图3.17所示的信号流程图。将2点DFT的信号流程图移入图3.17，得到图3.19所示的8点时间抽选的完整的FFT流程图。从图3.19中可看出几个特点：(1)流程图的每一级的基本计算单元都是一个蝶形；(2)输入x(n)不按自然顺序排列，称为“混序”排列，而输出X(k)按自然顺序排列，称为“正序”排列，因而要对输入进行“变址”；(3)由于流程图的基本运算单元为蝶形，所以可以进行“同址”或“原位”计算。3.5.3蝶形、同址和变址计算大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。2．同址(原位)计算可以看出，每一级的蝶形的输入与输出在运算前后可以存储在同一地址(原来位置上)的存储单元中，这种同址运算的优点是可以节省存储单元，从而降低对计算机存储量的要求或降低硬件实现的成本。3．变址计算在实际运算中，按码位倒置顺序输入数据x(n)，特别当N较大时，是很不方便的。因此，数据总是按自然顺序输入存储，然后通过“变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换的程序可用图3.21来说明。图中用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)的存储单元中。最后介绍一下时间抽选FFT算法的另外一些形式的流程图。对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不论节点位置怎样排列，所得到的流程图总是等效的，因而都能得到DFT的正确结果，只是数据的提取和存储次序不同而已。另一种形式的流程图是将节点排列成输入和输出两者都是正序排列，但这类流程图不能进行同址计算，因而需要两列长度为N的复数存储器。3.5.4频率抽选基2FFT算法其次，按规则(2)，将频率偶奇分，即在实际计算中，首先形成序列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计算，其推导过程如下。对频率再进行偶奇分，则得频率的偶数项为与时间抽