57 第四章快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT) 将其频域也离散化成有限长序列 .但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965 年， Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换 （FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT 的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT 的多种算法，基本算法是基２DIT 和基２ DIF 。FFT 在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅里叶变换（FFT）是计算离散傅里叶变换（DFT ）的快速算法。DFT 的定义式为)(kX=)()(10kRWnxNNnknN在所有复指数值knNW的值全部已算好的情况下，要计算一个)(kX需要N次复数乘法和N－ 1 次复数加法。算出全部N 点)(kX共需2N次复数乘法和)1(NN次复数加法。即计算量是与2N成正比的。FFT 的基本思想：将大点数的DFT 分解为若干个小点数DFT 的组合，从而减少运算量。NW因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的DFT运算：（1）周期性：kNnNknNnNkNWWW)()(（2）对称性：kNNkNWW)2/(58 利用这两个性质，可以使DFT 运算中有些项合并，以减少乘法次数。例子：求当 N＝4 时， X(2) 的值)()]3()1([)]2()0([)()]3()1([)]2()0([)3()2()1()0()()2(042404644424043024对称性－＝周期性WxxxxWxxWxxWxWxWxWxWnxXnn通过合并，使乘法次数由4 次减少到 1 次，运算量减少。FFT 的算法形式有很多种，但基本上可以分为两大类：按时间抽取（DIT ）和按频率抽取（DIF）。4.1 按时间抽取（ DIT ）的 FTT 为了将大点数的DFT 分解为小点数的DFT 运算，要求序列的长度N 为复合数，最常用的是MN2的情况（ M 为正整数）。该情况下的变换称为基 2FFT。下面讨论基2 情况的算法。先将序列 x(n)按奇偶项分解为两组)()12()()2(21rxrxrxrx12,,1,0Nr将 DFT 运算也相应分为两组)]([)(nxDFTkX10)(NnknNWnx1n 010)()(NnknNNnnknNWnxWnx为奇数为偶数＋12/0)12(12/02)12()2(NrkrNNrrkNWrxWrx＝59 12/02212/021)()(NrrkNkNNrrkNWrxWWrx＝12/02/212/02/1)()(NrrkNkNNrrkNWrxWWrx＝（因为rkNrkNWW2/2）)()(21kXWkXkN其中)(1 kX、)(2 kX分别是)()(21nxnx、的 N/2 点的 DFT )(1 kX120,)2()(12/02/12/02/1NkWrxWrxNrrkNNrrkN＝)(2 kX120,)12()(12/02/12/02/2...
