————第四章———— 快速傅里叶变换FFT所谓的快速算法，就是根据原始变换定义算法的运算规律及其中的某些算子的特殊性质，找出减少乘法和加法运算次数的有效途径，实现原始变换的各种高效算法。

一种好的快速算法可使变换速度提高几个数量级。

由于快速算法很多，而且还在不断研究和发展。

较成熟的算法都有现成的程序。

所以，通过教材中介绍的四种快速算法，主要学习研究快速算法的基本思想和减少运算量的途径，熟悉各种快速算法的特点、运算效率和适用情况。

为今后研究新的快速算法和合理选用快速算法打好基础。

4.1 学 习 要 点4.1.1 直接计算N 点DFT 的运算量 对于()(),10∑-==N n knN W n x k X 1,,1,0-=N k复数乘法次数：2N M c =复数加法次数：()1-=N N A c当1>>N 时，复数乘法和加法次数都接近为2N 次，随着N 增大非线性增大。

4.1.2 减少运算量的基本途径DFT 定义式中只有两种运算：()n x 与knN W 的乘法相加。

所以，knN W 的特性对乘法运算量必有影响。

（1）根据的对称性、周期性和特殊值减少乘法运算次数。

①对称性：kN N k N W W -=+2，()k k NNW 12-=，()kNk N N W W =*- ②周期性：kN lNk NW W =+。

③knN W 的特殊值(无关紧要旋转因子)：1;;124-===±N NNNN Wj W W 。

对这些因子不能进行乘法运算。

（2）将较大数N 点DFT 分解为若干个小数点DFT 的组合，减少运算量。

这正是FFT 能大量节省运算量的关键。

4.1.3 四种快速算法的基本思想及特点 根据上述减少运算量的途径，巧妙地在时域或频域进行不同的抽取分解与组合，得到不同的快速算法。

下面简要归纳四种快速算法的基本思想和特点。

1. 基2 DFT-FFT 算法（1）算法思想：时域M 级奇偶抽取，并利用kNN k N W W -=+2，将N 点DFT 变成M 级蝶形运算。

（2）运算量：复数乘法次数： N NM N M c 2log 22=⋅=复数加法次数： N N M N A c 2log =⋅=（3）特点：运算流图结构规则，可原位计算，程序简短，应用广泛。

2. 基2 DIF-FFT 算法（1）算法思想：频域对()k X 进行M 级奇偶抽取，并利用()kk NNW 12-=，将N 点DFT变成M 级DIF-FFT 蝶形运算。

（2）运算量及特点与基2 DIF-FFT 相同3. 分裂基快速算法（1）算法思想：基2 FFT 算法简单，基4FFT 算法效率较高。

分裂基是将基2分解和基4分解糅合在一起形成的高效新算法。

具体是对每次的频域奇偶抽取的偶数输出使用基2算法（按二进制抽取），而奇数输出使用基4算法（按四进制抽取）。

（2）运算量：复数乘法次数： ()92192log 312m c N N N M -+-=复数加法次数： N N A c 2log = （3）特点：①在MN 2=的快速算法中，分裂基算法的乘法次数最少，接近理论最小值。

比基2 FFT 减少33%，比基4减少11%。

②运算流图结构规则，可同址计算，程序简短，便于DSP 实现。

4.2 教材第四章习题解答1. 如果通用计算机的速度为平均每次复数乘需要5s μ，每次复数加需要1s μ，用来计算N=1024点DFT ，问直接计算需要多少时间。

用FFT 计算呢？照这样计算，用FFT 进行快速卷积对信号进行处理时，估算可实现时处理的信号最高频率。

解：当N=1024=210时，直接计算DFT 的复数运算次数为N 2=10242次复数加法计算次数为104755210231024)1(=⨯=-N N 次直接计算所用计算时间T D 为s T D 290432.61010475521024105626=⨯+⨯⨯=--用FFT 计算1024点DFT 所需计算时间为ms N N N NT D 84.3510log log 21056226=⨯+⨯⨯=-- 快速卷积时，要计算一次N 点FFT （考虑到)]([)(n h DFT k H =已计算好存入内存），一次N 点IFFT 和N 次频率复数乘法。

所以，计算1024点快速卷积的计算时间约为s s s T T F c μμμ76800102457168010242=⨯+=+=次复数乘计算时间所以，每秒钟处理的采样点数（即采样频率）次3.13333107680010246=⨯<-s f /秒。

由采样定理知，可实时处理的信号最高频率为HZ f f s 7.666623.133332max ==<应当说明，实际实现时，m ax f 还要你小一些。

这是由于采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分还要计算两次。

重叠部分长度与()n h 长度有关，而且还有存取数据指令周期等。

3. 已知()X k 和()Y k 是两个N 点实序列()x n 和()y n 的DFT ，若要从()X k 和()Y k 求()x n 和()y n ，为提高运算效率，试设计用一次N 点IFFT 来完成。

解：因为()x n 和()y n 均为实序列，所以，()X k 和()Y k 为共轭对称序列，j ()Y k 为共轭反对称序列。

可令()X k 和j ()Y k 分别作为复序列)(k F 的共轭对称分量和共轭反对称分量， 即)()()()()(k F k F k jY k X k F op ep +=+=计算一次N 点IFFT 得到)](Im[)](Re[)]([)(n f j n f k F IFFT n f +==由DFT 的共轭对称性可知，)()]([)]([)](Im[)()]([)]([)](Re[n jy k jY IDFT k F IDFT n f j n x k X IDFT k F IDFT n f op ep ======故)]()([21)()]()([21)(n f n f jn y n f n f n x **-=+=4. 设()x n 是长度()X k 为2N 的有限长实序列，()X k 为()x n 的确N 点DFT 。

（1）试设计用一次N 点FFT 完成计算()X k 的高效算法。

（2）若已知()X k ，试设计用一次N 点IFFT 实现求()x n 的2N 点IDFT 运算。

解：（1）在时域分别抽取偶书点和奇数点()x n 得到两个N 点实序列)(1n x 和)(2n x ：1,,1,0),12()(1,,1,0),2()(21-=+=-==N n n x n x N n n x n x根据DIT-FFT 的思想，只要求得)(1n x 和)(2n x 的N 点DFT,再经过简单的一级蝶形运算就得到()x n 的2N 点DFT 。

因为)(1n x 和)(2n x 均为实序列，所以根据DFT 的共轭对称性，可用一次N 点FFT 求得)(1k X 和)(2k X 。

具体方法如下： 令 )()()(21n jx n x n y +=1,1,0)],([)(-==N k n y DFT k Y则 )]()([21)()]([)(11k N Y k Y k Y n x DFT k X ep -+===* )]()([21)()]([)(22k N Y k Y k Y n jx DFT k jX op --===*2N 点)()]([k X n X DFT =可由)(1k X 和)(2k X 得到)()()(1,,1,0),()()(221221k X W k X N k X N k k X W k X k X k Nk N -=+-=+=这样，通过一次N 点IFFT 计算就完成了计算2N 点DFT 。

当然还要进行运算量相对很少的，由)(k Y 求)(1k X ，)(2k X 和)(k X 的运算。

（2）和（1）相同，设1,,1,0),12()(1,,1,0),2()(21-=+=-==N n n x n x N n n x n x1,1,0)],([)(1,1,0)],([)(2211-==-==N k n x DFT k X N k n x DFT k X则应满足关系式)()()(1,,1,0),()()(221221k X W k X N k X N k k X W k X k X kNk N -=+-=+=由上式可解出kN W N k X k X k X N k X k X k X -+-=++=221)]()([21)()]()([21)(由以上分析可得到运算过程如下： ① 由)(k X 计算出)(1k X 和)(2k XkN W N k X k X k X N k X k X k X -+-=++=221)]()([21)()]()([21)(② 由)(1k X 和)(2k X 构成N 点频域序列)(k Y)()()()()(21k Y k Y k jX k X k Y op ep +=+=其中)()(1k X k Y ep =，)()(2k jX k Y op =，进行N 点IFFT 得到1,,1,0)],(Im[)](Re[)]([)(-=+==N n n y j n y k Y IFFT n y由DFT 的共轭对称性知)()]([)]()([21)](Im[)()]([)]()([21)](Re[21n jx k Y DFT n y n y n y j n x k Y DFT n y n y n y op ep ==-===+=**③ 由)(1n x 和)(2n x 合成()x n120,)21(),2()(21-≤≤⎪⎪⎩⎪⎪⎨⎧=-==N n n n x n nx n x 奇数，偶数在便成实现时，只要将存放)(1n x 和)(2n x 的两个数组的元素分别依次存放()x n 的数组的偶数和奇数数组元素中即可。

5. 按照下面的IDFT 算法：1()[()][[()]]x n IDFT X k DFT X k N**==编写IFFT 程序，其中的FFT 部分不用写出清单，可调用FFT 子程序。

解：通过调用FFT 子程序实现题中所给IFFT 算法程序框图如题5图解所示。

数组X[N]用于存放输入X（k）、中间结果及最终结果x(n)。

用matlab语言编写的IFFT程序清单如下：％题4.6计算IFFT的程序％Xk:被变换数据X（k）％XN:IFFT[X(k)]结果x(n)%N:x(n),X(k)长度Xk＝[X(0) X(1) …X(N-1)];n=size(Xk);N=n(2); %取得X（k）的长度Xk＝conj(Xk); %取复共轭XN=fft(Xk); ％计算FFT[X(k)]XN=conj(XN)/N;Stem(real(XN)); %绘制x(n)序列波形图说明：数据向量Xk也可以通过键盘，数据文件或函数计算等多种方法建立，本程序使用最简单的方法，在程序中直接赋值Xk向量。