[工学]详解FFT快速傅里叶变换FFT.doc

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