第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley 和Tukey 提出了计算离散傅里叶变换（DFT ）的快速算法，将DFT 的运算量减少了几个数量级。

从此，对快速傅里叶变换（FFT ）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT 的出现和发展而迅速发展。

根据对序列分解与选取方法的不同而产生了FFT 的多种算法，基本算法是基２DIT 和基２DIF 。

FFT 在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。

快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。

DFT 的定义式为)(k X =)()(10k R W n x N N n knN∑-= 在所有复指数值knN W 的值全部已算好的情况下，要计算一个)(k X 需要N 次复数乘法和N －1次复数加法。

算出全部N 点)(k X 共需2N 次复数乘法和)1(-N N 次复数加法。

即计算量是与2N 成正比的。

FFT 的基本思想：将大点数的DFT 分解为若干个小点数DFT 的组合，从而减少运算量。

N W 因子具有以下两个特性，可使DFT 运算量尽量分解为小点数的DFT运算：（1） 周期性：k N n N kn N nN k N W W W )()(++== （2） 对称性：k N N k NW W -=+)2/(利用这两个性质，可以使DFT 运算中有些项合并，以减少乘法次数。

例子：求当N ＝4时，X(2)的值)()]3()1([)]2()0([)()]3()1([)]2()0([)3()2()1()0()()2(04240464442404324对称性－＝周期性W x x x x W x x W x x W x W x W x W x W n x X n n +++++=+++==∑=通过合并，使乘法次数由4次减少到1次，运算量减少。

FFT 的算法形式有很多种，但基本上可以分为两大类：按时间抽取（DIT ）和按频率抽取（DIF ）。

4.1 按时间抽取（DIT ）的FTT为了将大点数的DFT 分解为小点数的DFT 运算，要求序列的长度N 为复合数，最常用的是MN 2=的情况（M 为正整数）。

该情况下的变换称为基2FFT 。

下面讨论基2情况的算法。

先将序列x(n)按奇偶项分解为两组 ⎩⎨⎧=+=)()12()()2(21r x r x r x r x 12,,1,0-=Nr Λ将DFT 运算也相应分为两组==)]([)(n x DFT k X ∑-=1)(N n knNWn x∑∑-=-==1n 010)()(N n kn NN n n kn NWn x Wn x 为奇数为偶数＋∑∑-=+-=++12/0)12(12/02)12()2(N r k r NN r rk NWr x Wr x ＝∑∑-=-=+12/02212/021)()(N r rkN k NN r rk NW r xWWr x ＝∑∑-=-=+12/02/212/02/1)()(N r rkN k NN r rkN W r xWWr x ＝（因为rk N rk N W W 2/2=） )()(21k X W k X kN +=其中)(1k X 、)(2k X 分别是)()(21n x n x 、的N/2点的DFT)(1k X 120,)2()(12/02/12/02/1-≤≤=∑∑-=-=N k W r x Wr x N r rk N N r rkN ＝ )(2k X 120,)12()(12/02/12/02/2-≤≤+=∑∑-=-=N k Wr x Wr x N r rk N N r rk N ＝ 至此，一个N 点DFT 被分解为两个N/2点的DFT 。

上面是否将全部N 点的)(k X 求解出来了？分析：)(1k X 和)(2k X 只有N/2个点（12,,1,0-=Nk Λ），则由)(k X )()(21k X W k X kN+=只能求出)(k X 的前N/2个点的DFT ，要求出全部N 点的)(k X ，需要找出)(1k X 、)(2k X 和)2/(N k X +的关系，其中12,,1,0-=N k Λ。

由式子)(k X )()(21k X W k X kN+=可得 )2/(N k X +)2/()2/(22/1N k X W N k X N k N+++=+化简得 )2/(N k X +＝)()(21k X W k X kN-=，12,,1,0-=Nk Λ 这样N 点DFT 可全部由下式确定出来：⎪⎩⎪⎨⎧-=++=)()()2/()()()(2121k X W k X N k X k X W k X k X kN kN 12,,1,0-=N k Λ （＊） 上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运算。

abkNWbW a kN +bW a kN --1图 蝶形运算符号通过这样的分解以后，每一个N ／2点的DFT 只需要4)2(22N N =次复数乘法，两个N/2点的DFT 需要2)2(222N N =次复乘，再加上将两个N ／2点DFT 合并成为N 点DFT 时有N ／2次与W 因子相乘，一共需要22222N N N ≈+次复乘。

可见，通过这样的分解，运算量节省了近一半。

因为MN 2=，N/2仍然是偶数，因此可以对两个N/2点的DFT 再分别作进一步的分解，将两个N/2点的DFT 分解成两个N/4点的DFT 。

例如对)(1r x ，可以在按其偶数部分及奇数部分进行分解：⎩⎨⎧=+=)()12()()2(4131l x l x l x l x 14,,1,0-=Nl Λ则的运算可相应分为两组：)(1k X ∑∑-=+-=++14/0)12(2/114/022/1)12()2(N l k l N N l lkN Wl x Wl x ＝∑∑-=-=+14/04/42/14/04/3)()(N l lkN k N N l lk N W l xWWl x ＝)()(42/3k X W k X kN += 14,,1,0-=Nk Λ将系数统一为以Ｎ为周期，即kN k N W W 22/=，可得⎪⎩⎪⎨⎧-=++=)()()4/()()()(42314231k X W k X N k X k X W k X k X kN kN 14,,1,0-=N k Λ 同样，对)(2k X 也可进行类似的分解。

一直分解下去，最后是２点的DFT ，２点DFT 的运算也可用碟形符号来表示。

这样，对于一个823==N 的DFT 运算，其按时间抽取的分解过程及完整流图如下图所示。

这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。

分析上面的流图，MN 2=，一共要进行M 次分解，构成了从x(n)到X(k)的M 级运算过程。

每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要N/2次复乘和N 次复加，则按时间抽取的M 级运算后总共需要复数乘法次数：N NM N m F 2log 22=⋅=复数加法次数：N N M N a F 2log =⋅=根据上面的流图，分析ＦＦＴ算法的两个特点，它们对ＦＦＴ的软硬件构成产生很大的影响。

（１） 原位运算也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。

根据运算流图分析原位运算是如何进行的。

原位运算的结构可以节省存储单元，降低设备成本。

（２） 变址分析运算流图中的输入输出序列的顺序，输出按顺序，输入是“码位倒置”的顺序。

见图。

码位倒置顺序码位倒置的变址处理在实际运算中，直接将输入数据x(n)按码位倒置的顺序排好输入很不方便，一般总是先按自然顺序输入存储单元，然后通过变址运算将自然顺序的存储换成码位倒置顺序的存储，这样就可以进行FFT的原位运算。

变质的功能如图所示。

用软件实现是通用采用雷德（Rader）算法，算出I的倒序Ｊ以后立即将输入数据X(I)和X(J)对换。

尽管变址运算所占运算量的比例很小，但对某些高要求的应用（尤其在实时信号处理中），也可设法用适当的电路结构直接实现变址。

例如单片数字信号处理器TMS320C25就有专用于FFT的二进制码变址模式。

4.２ 按频率抽取（DIF ）的FTT除时间抽取法外，另外一种普遍使用的FFT 结构是频率抽取法。

频率抽取法将输入序列不是按奇、偶分组，而是将Ｎ点DFT 写成前后两部分：==)]([)(n x DFT k X ∑-=1)(N n knN W n x ∑∑-=-==12/1)2/(0)()(N N n kn NN n knNWn x Wn x ＋∑∑-=+-=++12/0)2/(12/0)2/()(N n k N n NN n nk NWN n x Wn x ＝nkN N n k N N W N n x W n x ∑-=++12/0)2/()]2/()([＝因为k k N N N NW W )1(,1)2/(2/-=-=，k 为偶数时1)1(=-k ，k 为奇数时1)1(-=-k ，由此可将X(k)分解为偶数组和奇数组：nkN N n kW N n x n x k X ∑-=+-+12/0)]2/()1()([)(＝nrN N n nrNN n WN n x n x W N n x n x r X 2/12/0212/0)]2/()([)]2/()([)2(∑∑-=-=++=++＝nr N nN N n nr NN n W WN n x n x W N n x n x r X 2/12/0)12(12/0)]2/()([)]2/()([)12(∑∑-=+-=+-=+-+＝令⎩⎨⎧+-=++=nNW N n x n x n x N n x n x n x )]2/()([)()2/()()(21 12/,,1,0-=N n Λ这两个序列都是N/2点的序列，对应的是两个N/2点的DFT 运算：nrN N n W n x r X 2/12/01)]()2(∑-=＝rn N N n W n x r X 2/12/02)()12(∑-=+＝这样，同样是将一个N 点的DFT 分解为两个N/2点的DFT 了。

频率抽选法对应的碟形运算关系图如下：abn NW ba +nNW b a )(--1对于N=8时频率抽取法的FFT 流图如下：这种分组的办法由于每次都是按输出X(k)在频域的顺序上是属于偶数还是奇数来分组的，称为频率抽取法。

与前面按时间抽取的方法相比，相同点 问题：如何利用快速算法计算IDFT ？ 分析IDFT 的公式：1,,1,0,)(1)]([)(1-===∑-=-N n Wk X Nk X IDFT n x N k nk NΛ比较DFT 的公式：1,,1,0,)()]([)(1-===∑-=N k Wn x n x DFT k X N n nk NΛ得知可用两种方法来实现IDFT 的快速算法：（１）只要把DFT 运算中的每一个系数nkN W 该为nkNW -，并且最后再乘以常数N1，就可以用时间抽取法或频率抽取的FFT 算法来直接计算IDFT 。