1、快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基DIT 和基DIF。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。快速傅里叶变换（FFT）
2、是计算离散傅里叶变换（DFT）的快速算法。DFT 的定义式为knN 1X (k ) = x(n)WNRN (k )n =0N在所有复指数值 W kn 的值全部已算好的情况下，要计算一个 X (k ) 需要 N次复数乘法和 N1 次复数加法。算出全部 N 点 X (k ) 共需 N 2 次复数乘法 和 N ( N 1) 次复数加法。即计算量是与 N 2 成正比的。FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。WN 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT运算：W（1） 周期性：( k + N ) nNN= W knN=
3、W ( n + N ) k（2） 对称性：W ( k + N / 2 ) = W kNN利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子：求当 N4 时，X(2)的值344444X (2) =n =0x(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(周期性)44 x(0) + x(2) x(1) + x(3)W 04(对称性)通过合并，使乘法次数由 4 次减少到 1 次，运算量减少。FFT 的算法形式有很多种，但基本上可以分为两大类：按时间抽取（DIT）和按
4、频率抽取（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 运算也相应分为两组Nr = 0,1,L, 2 1N 1NX (k ) = DFT x(n) = x(n)W knn =0N 1N= x(n)W knN 1N x(n)W knn=0n为偶数n =0n 为奇数N / 21 (2
5、 )2 rk +N / 21 (2+ 1)( 2 r +1) kxr =0r WNxrWNr =0N / 212 rk +N / 21k 2 rkr =0x1 (r )WNWNkr =0x2 (r )WNrkN / 21 x1 (r )Wr =0N / 2 + WNN / 21 x2 (r )Wr =0rkN / 2（因为W2 rkN）rk= WN / 2k= X 1 (k ) + WN X 2 (k )其中 X 1 (k ) 、 X 2 (k ) 分别是 x1 (n)、x2 (n) 的 N/2 点的 DFTN / 21N / 21NrkrkX 1 (k ) x1 (r )WN / 2 = x
6、(2r )WN / 2 ,0 k 1r =0r =02N / 2 1N / 2 1rkrkNX 2 (k ) x 2 (r )W N / 2 = x(2r + 1)W N / 2 ,0 k 1r =0r =0 2至此，一个 N 点 DFT 被分解为两个 N/2 点的 DFT。上面是否将全部 N 点的 X (k ) 求解出来了？分析： X 1 (k ) 和NX 2 (k ) 只有 N/2 个点（ k = 0,1,L,2 1 ），则 由1 N 2X (k ) = X (k ) + W k X (k ) 只能求出 X (k ) 的前 N/2 个点的 DFT，要求出全部 N 点的 X (k ) ，需要
7、找出 X 1 (k ) 、 X 2 (k ) 和 X (k + N / 2) 的关系，其N中 k = 0,1,L, 2 1。由式子 X (k ) = X 1N(k ) + W k X2 (k ) 可得1 NX (k + N / 2) = X (k + N / 2) + W k + N / 2kX 2 (k + N / 2) 化简得NX (k + N / 2) = X 1 (k ) WN X 2 (k ) ， k = 0,1,L, 2 1这样 N 点 DFT 可全部由下式确定出来：1N2 X (k ) = X (k ) + W k X (k )1N2 X (k + N / 2) = X (k )
8、 W k X (k )k = 0,1,L, N 12（）上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运 算。Naa + W k bWNkba W k b-1N图蝶形运算符号2通过这样的分解以后，每一个 N2 点的 DFT 只需要 ( N ) 2 = N次复数乘242法，两个 N/2 点的 DFT 需要 2( N ) 2 = N次复乘，再加上将两个 N2 点22DFT 合并成 为 N 点 DFT 时有 N 2 次与 W 因 子相 乘，一 共需 要2N+ N22N 2次复乘。可见，通过这样的分解，运算量节省了近一半。2因为 N = 2 M ，N/2 仍然是偶数，因此可以对两个
9、N/2 点的 DFT 再分别作进一步的分解，将两个 N/2 点的 DFT 分解成两个 N/4 点的 DFT。例如对 x1 (r) ，可以在按其偶数部分及奇数部分进行分解：x1 (2l ) = x3 (l )x1 (2l + 1) = x4 (l )则的运算可相应分为两组：Nl = 0,1,L, 4 1N / 41X 1 (k ) x1 (2l )Wl =02lkN / 2N / 41+ x1 (2l + 1)Wl =0( 2l +1) kN / 2N / 41+lk3 ( )/ 4kN / 2N / 414 ( )lkN / 4xl =0l WNWkx l Wl =0N= X 3 (k ) +
10、 WN / 2 X 4 (k )N / 2将系数统一为以为周期，即W kk = 0,1,L, 4 1N= W 2 k ，可得13N X (k ) = X (k ) + W 2 kX 4 (k )2 kk = 0,1,L, N 1X 1 (k + N / 4) = X 3 (k ) WNX 4 (k )4同样，对 X 2 (k ) 也可进行类似的分解。一直分解下去，最后是点的DFT，点 DFT 的运算也可用碟形符号来表示。这样，对于一个 N = 2 3 = 8的 DFT 运算，其按时间抽取的分解过程及完整流图如下图所示。这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取
11、的，故称为“时间抽取法”。分析上面的流图， N = 2 M ，一共要进行 M 次分解，构成了从 x(n)到X(k)的 M 级运算过程。每一级运算都是由 N/2 个蝶形运算构成，因此每一 级运算都需要 N/2 次复乘和 N 次复加，则按时间抽取的 M 级运算后总共需 要复数乘法次数： mF= N M2= N log N22复数加法次数： aF= N M = N log 2 N根据上面的流图，分析算法的两个特点，它们对的软硬件构成产生很大的影响。（） 原位运算 也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储 在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图 分
12、析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备 成本。（） 变址 分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序。见图。自然顺序二进制表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110011371111117码位倒置顺序01234567X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7) 码位倒置的变址处理在实际运算中，直接将输入数据 x(n)按码位倒置的顺序排好输入很不方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行 FFT 的原位运算。变质 的功能如图所示。用软件实现是通用采用雷德（Rader）算法，算出 I 的倒 序以后立即将输入数据 X(I)和 X(J)对换。尽管变址运算所占运算量的比例 很小，但对某些高要求的应用（尤其在实时信号处理中），也可设法用适当 的电路结构直接实现变址。例如单片数字信号处理器 TMS320C25 就有专用 于 FFT 的二
