57 第四章快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT) 将其频域也离散化成有限长序列 .但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965 年, Cooley 和 Tukey 提出了计算离散傅里叶变换(DFT )的快速算法,将 DFT 的运算量减少了几个数量级。从此,对快速傅里叶变换 (FFT)算法的研究便不断深入,数字信号处理这门新兴学科也随FFT 的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT 的多种算法,基本算法是基2DIT 和基2 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...