第5章快速傅立叶变换.ppt

本章的主要内容则是若干计算离散傅立叶变换的快速算法，包括：基—2（包括按时间抽选及按频率抽选）算法，快速算法，分裂基算法、混合基算法、线性调频变换算法及相关的MATLAB仿真。 因为流程图的外形像一只蝴蝶，所以称之为蝶形图，由图可见，一个蝶形图包含1次复乘，2次复加。现在来看一下，经过第一次转换以后计算量是否减少了，又减少了多少？ 由（5-2-3）式可以看出，计算一个N点的DFT，首先需要计算2个N/2点的DFT。一个N/2点的DFT需要N2/4次复乘，N/2(N/2-1)次复加，两个N/2点DFT共需2×(N/2)2=N2/2次复数乘法和N(N/2-1)次复数加法。将2个N/2点的DFT转换成一个N点的DFT还需要N/2个蝶形运算（即N/2次复乘，N次复加）。综合以上，可见现在所需要的计算量为：(N2/2)+(N/2)=N(N+1)/2次复数乘法和N(N/2-1)+N=N2/2次复数加法 。 当N很大时(N2/2)+(N/2)≈N2/2。可见，通过这样分解后计算一个N点的DFT则需要N2/2次复加与N2/2次复乘。与直接计算N点的DFT计算量相比几乎节省了一半的计算量，特别是当N较大时，这种分解带来的效益是相当可观的。所以可以对N/2点的子序列进一步分解，直至不能分解为止。下面我们以N=8为例，完整的介绍这种快速算法及相应的流程图。 当N=8时第一次分解后，  同理,由 和 的周期性和 的对称性可得到： 其中： 把N/2点序列分解成2个N/4点的DFT的过程如下面的流程图所示： 与 都是2点的DFT不能再继续分解，直接计算可知： 同理可以得出： 计算得出： 当N=8时，一个完整的DIT—FFT运算流图如下： 5.2.2 运算量的比较 观察上面的运算流图可知：当N=2L时，其运算流图有L级蝶形图构成，每一级均有N/2个蝶形运算，一个蝶形运算需要1次复乘，2次复加。则L级的蝶形图共需复乘： 次； 复加： 次。直接计算DFT所需运算：复乘， 次；复加： 由于计算机上乘法运算所需的时间比加法运算所需的时间多得多，故以乘法为例，直接DFT复数乘法次数是 ,FFT复数乘法次数 ,直接计算 DFT与FFT算法的计算量之比为 ： 5.2.3时间抽取算法FFT（DIT—FFT）的运算特点： 一、 原位运算（同址运算） 当数据输入到存储器中以后，每一级运算的结果仍然储存在 同一组存储器中，直到最后输出，中间无需其它存储器，这叫 原位计算。 从图5-4可以看出这种运算是很有规律的，其每级（每列）计 算都是由N/2 个蝶形运算构成的，每一个蝶形结构完成下述基本 迭代运算： 式中，m表示第m列迭代，i, j则分别为该蝶形单元两个 输入数据所在行数。式（5-2-6）的蝶形运算如图5-6所示。 由上面完整的运算流程图5-4可以看出，第m级蝶形运 算的输出数据仅与该级蝶形运算的输入数据有关，与前 m-1级蝶形的输入数据无关，且第m-1级蝶形运算的输出 数据为第m级蝶形运算的输入数据。某任何一个蝶形运算 的两个输入节点i和j的节点变量进行蝶形运算后，得到结 果为该蝶形运算两个输出节点，i, j两节点的节点变量， 而和其他节点变量无关，因而可以采用原位运算。 例如，N=8的FFT运算，输入x(0)，x(4)，x(2)，x(6)…， x(7)可分别存入A(1)，A(2)，…，A(8)这8个存储单元中，在第一 级运算中，首先是存储单元A(1)，A(2)中x(0)，x(4)进入蝶形运 算，x(0)，x(4)输入运算器后，其数值不再需要保存，因此蝶形 运算的结果可仍然送回存储单元A(1)，A(2)中保存，然后A(3)， A(4)中x(2)，x(6)再进入蝶形运算，其结果再送回A(3)，A(4)，一 直到算完A(7)，A(8)，则完成了第一级运算过程。第二级运算仍 可采用这种原位的方式，但是进入蝶形结的组合关系不同，首先 进入蝶形结的是A(1)、A(3)存储单元中的数据， 运算结果仍可送回A(1)、A(3)保存，然后进入蝶形结的是 A(2)、A(4)…，依此类推，每一级运算均可在原位进行， 这种原位运算结构可节省存储单元，降低设备成本，还