华东理工大学MATLAB合编.ppt

第四章 快速傅立叶变换 Fast Fourier Transform ;第一节 直接计算DFT的问题及改进途径;2. DFT的运算量 ;计算机运算时（编程实现）： ;;例：计算一个 N点DFT ，共需N2次复乘。以做一次 复乘1μs计，若N =4096，所需时间为; 由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。长期以来，人们一直在寻求一种能提高DFT运算速度的方法。;第二节 改善DFT运算效率的基本途径;;2、将长序列DFT利用对称性和周期性分解为短 序列DFT的思路;N点 DFT; FFT算法的基本思想： 利用DFT系数的特性，合并DFT运算中的某些项 把长序列DFT→短序列DFT，从而减少运算量。;第三节 按时间抽选的基2-FFT算法;先将x(n)按n的奇偶分为两组，作变量置换: 当n=偶数时，令n=2r; 当n=奇数时，令n=2r+1;; 带入DFT中;所以 ; X1(k)、X2(k)只有N/2个点，以N/2为周期；而X (k)却有N个点，以N为周期。要用X1(k)、X2(k)表达全部的X (k) 值，还必须利用WN系数的周期特性。;后半部分;;;先将N=8点的DFT分解成2个4点DFT： 可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)~X(3)，由X(k)给出 X(4)~X(7)，由X(k+N/2)给出; N=8点的直接DFT的计算量为： 复乘：N2次 = 64次 复加：N(N-1)次 = 8×7=56次;N点DFT的一次时域抽取分解图(N=8) ;因为4点DFT还是比较麻烦，所以再继续分解。 ;那么，X1(k)又可表示为 ;X2(k)也可以进行相同的分解： ;N点DFT的第二次时域抽取分解图(N=8) ;8;N点DIT―FFT运算流图(N=8) ;3、DIT―FFT算法与直接计算DFT运算量的比较;FFT算法与直接计算DFT所需乘法次数的比较曲线;;x(0) ; 如上所述，N点DIT―FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WNP，称其为旋转因子，p称为旋转因子的指数。;对N=2M的一般情况，第L级的旋转因子为：; 设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点(B=2L-1)，应用原位计算，则蝶形运算可表示成如下形式：;3) 编程思想及流程图;4）码位倒序;自然顺序n;倒序规律; 对于数N，在其二进制最高位加1，等于加N/2。;倒 序 排 列 算 法 的 流 程 图;第四节 按频率抽选的基2-FFT算法;;;;DIF―FFT一次分解运算流图(N=8) ;DIF―FFT二次分解运算流图(N=8) ;DIF―FFT运算流图(N=8) ; 时间抽取算法与频率抽取算法的比较;第五节 IDFT的快速算法－IFFT;DIT―IFFT运算流图 ;DIT―IFFT运算流图(防止溢出) ; 如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：;例1、如果通用计算机的速度为平均每次复乘需要 5?s，每次复加需要0.5?s，用它来计算512点 的DFT[x(n)]，问：;2）用FFT进行运算：;例2、长度为240点的序列x(n)与长度为N点的h(n)卷 积。当N=10和240时，直接进行卷积 x(n)*h(n) 和用 IFFT[X(K)·H(K)] 的方法相比，那种方法求 解y(n)的效率更高？;直接进行卷积（N=10）：;直接进行卷积（N=240）：;第六节 进一步而减少运算量的措施; 一个旋转因子对应一个蝶形单元。;表4.1 基2-FFT在各种蝶形单元下所需的实数乘法的次数;2、旋转因子的生成; (2) 另一种方法是用N/2点的FFT计算一个N点长的FFT。; 根据DIT―FFT的思想，序列按奇偶序号分开后有： ; 步骤一、分解x(n)为偶序号x1(n)和奇序号x2(n)，构造y(n): y(n) = x1(n)+ jx2(n) ，对y(n)求N/2点FFT，并由 结果Y(k)分解出X1(k)和X2(k)。;用步骤一的方法求;第七节 其他快速算法介绍