在上一节的讨论中我们知道离散傅里叶变换对满足以下关系式:
kn，k=0,1,2,…,N-1 X(k)?DFT[x(n)]??x(n)WNn?0N?11N?1?kn，n=0,1,…,N-1 x(n)?IDFT[X(k)]??X(k)WNNk?0式中，WN?e?j2?N。一般情况下时间序列x(n)及其离散傅里叶变换X(k)是用复数
表示的，由此可见直接计算DFT及IDFT需要N2次复数乘法及N(N?1)次复数加法。由于一次复数乘法要作4次实数乘法和两次实数加法，一次复数加法要作2次实数加法，所以做一次离散傅里叶变换需要做4N2次实数乘法及N(4N?2)次实数加法。随着序列长度N的增大、运算次数将剧烈地增加。离散傅里叶变换的应用十分广泛，有必要在计算方法上寻求改进，使其运算次数大大减少。
3.2 离散傅里叶变换的快速算法
60年代中期，Cooley和Tukey提出了一种离散傅里叶变换的快速算法，它所需的运算量大约为(Nlog2N)/2次复数乘法和Nlog2N次复数加法。因此，这种算法的出现，大大推动了离散傅里叶变换在各方面的应用。
目前比较普遍使用的算法，是基于Cooley和Tukey提出的基二算法， 继Cooley和Tukey之后，又有许多人致力于进一步减少DFT的运算量，提出了一些改进算法。其中最著名的算法是1975年IBM公司的Shmuel Winograd博士提出的WFTA算法(Winograd Fourier Transform Algorithm，简称WFTA算法)。
本节将先主要讨论FFT的基本思想，介绍基2FFT和WFTA算法，同时简要介绍一下在基二算法基础上发展起来的基四算法以及素因子算法。
3.3 FFT算法的基本思想
前面提到，N点DFT的复乘次数等于N2，显然，把N点DFT分解成几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WNm具有明显的周期性和对称性，其周期性表现为
Wm?lNN2?mN?e?j2?(m?lN)?e?jm (3.1) ?WN其对称性表现为
?mN?mN?m?m 或者 [WN (3.2) WN?WN]?WNWN
m?N2m (3.3) ??WNknFFT算法就是不断的把长序列的DFT分解成几个短序列的DFT，并利用WN的
周期性和对称性来减少DFT的运算次序。
3.4 FFT算法的几种经典算法
（1）按时域抽取的基2FFT算法——DIT-FFT
这种算法是将输入序列在时域上的次序按偶数和奇数来抽取，对于任意一个
N?2m点长序列的DFT运算，可以采用M次分解，最后分解成2点的DFT运算的组合，从而降低了运算量。
设序列x(n)的长度为N，且满足N?2m（m为自然数）。
第一次分解：按n的奇偶把x(n)分解为两个N/2点的子序列
NN?1和x2(r)?x(2r?1),r?0,1,...,?1 22N/2?1x1(r)?x(2r),r?0,1,...,则x(n)的 DFT为X(k)??j2?2krNkr?WN/2
?x(r)W1r?02krN?WkNN/2?1r?0?x(r)W22krN (3.4)
由于W2krN?eN/2?1所以X(k)??x(r)W1r?02krN?WkNN/2?1r?0?x(r)W22krNk?X1(k)?WNX2(k)，k=0,1,…,N-1
(3.5) 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT。由于X1(k)和X2(k)均以N/2为周期，且WNm?N2m，所以X(k)又可以表示为 ??WNkX(k)?X1(k)?WNX2(k)k?0,1,...,N/2?1 (3.6) kX(k?N/4)?X1(k)?WNX2(k),k?0,1,...,N/2?1， (3.7)
这样，就将N点的DFT分解为两个N/2点的DFT和式（3.6）以及式（3.7）的运算。
第二次分解：与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列
x3(l)?x1(2l),l?0,1,...,NN?1和x4(l)?x1(2l),l?0,1,...,?1，那么仿照第一次的结44果，
kX1(k)?X3(k)?WN,...,N/4?1 (3.8) /2X4(k),k?0,1kX1(k?N/4)?X3(k)?WN,...,N/4?1 (3.9 ) /2X4(k),k?0,1用同样的方法可以计算出
kX2(k)?X5(k)?WN,...,N/4?1 (3.10) /2X6(k),k?0,1kX2(k?N/4)?X5(k)?WN,...,N/4?1 (3.11) /2X6(k),k?0,1这样，经过第二次分解，又将N/2点DFT分解为两个N/4点DFT。 依此类推，经过M—1次分解，最后将N点的DFT分解成N/2个2点DFT。 下文将利用一个长度为 8的DFT例子说明算法的思想.当N=8时，根据上面的分析可知，计算可以分解为三步.图3-1、图3-2和图3-3分别显示了这三步计算的具体过程 ，图3-4展示了整个运算流程。
图（3-1） 8点DFT的第一次时域抽取分解图
图（3-2）8点DFT的第二次时域抽取分解图
图（3-3）8点DFT的第三次时域抽取分解图
图（3-4）8点DFT的运算流图
与DIT-FFT算法相对应，按频域抽取的基2FFT算法——DIF-FFT是把频域
输出X(k)按k是偶数或是奇数，逐级分解成2点的DFT运算，其原理与DIT-FFT算法相对偶，运算量也与DIT-FFT算法的相同，这里不再赘述。 （2）基4FFT算法
基本原理与基2FFT，算法大致相同.设N?2t的长序列，先将这样一个长度为N的DFT转换成四个长度为N/4的DFT来计算，所需乘法次数和加法次数各为3N和3N/4，每一个新的DFT又可以分解为四个长度为N/16的DFT，直至一个简单的蝶形为止。
实际上，基4算法需要访问内存的次数也可以减少一半，这样也有利于提高运算速度.但是基4算法点数的取值种类应该是基2FFT算法的一半，这样使得基4FFT的应用受到限制，而且基4FFT的蝶型图也比基2FFT，算法要复杂得多.其实从理论上说，基数越高总的计算量就越少，所以采用基8和基16算法应该可以使运算次数进一步减少，但减少量会越来越不显著，而基8、基16算法的蝶形图会更加复杂，硬件和软件实现也非常不便，所以一向以来对它们的研究与利用并不多.
（3）素因子算法（PFA）
素因子算法无论是基2还是基4算法，都对DFT的长度N有非常大的限制，它们必须是2 或4的N 次方.但是在实际应用往往是不可能的.由于这个原因，后来发展的DFT算法很好地解决了这个问题. 当复合数N可以按照Good映射分解为几个互素因子的乘积时，其FFT变换就可以避免旋转因子的影响。PFA算法就是采用了Good映射，将长度为N?N1?N2的一维DFT'转换成尺寸为N1?N2的二维DFT' ,然后以行一列方式沿每一维采用最有效的算法计算这个二维的DFT。
（4） WFTA算法
WFTA算法是建立在下标映射和数论上的一套新颖的算法.它的主要思想是把一个长度为N（N?N1?N2）离散傅立叶变换分解为两个互素的小N因子的离散傅立叶变换.首先计算出N2长度变换的结果，再利用结果进行N1长度的计算.在实际应用中，若N较大，我们还可以将N划分成多个互素小N的乘积。“小N”因子的DF I'是指2,3,4,5,7,8,9和16点的DFT 。