信号与处理15教程.ppt

第十章 快速离散傅立叶变换 ;第十章 快速离散傅立叶变换 ;第一节 改进DFT计算的方法;直接计算DFT的运算量; 对所有k: 复乘: 复加: N(N-1) 即复数运算量与 近似成正比 (不考虑 情况) ;对每一个固定k :;改善运算效率的途径 （1）利用 的对称性和周期性等特性合并运算项 复共轭对称性: 对n和k的周期性: 可约性 特殊值; 式中其它各对称项也可以找到类似归并办法.这样乘法次数大约可减少一半. (2) 大点数DFT逐次分解成小点数DFT)分解 正是FFT算法的基本原理 ;FFT的基本原理： 为了提高DFT的运算效率, 把大点数DFT按倒位序逐次分解为更小点数DFT的合成.在分解过程中,要利用系数 的对称性和周期性. 如果算法是逐次分解时间序列得到的,那么这种分解算法称为按时间抽取算法.阐述按时间抽取原理最方便的方法是研究 这种特殊情况.由于N为2的整数幂,可以不断将x(n)一分为二. 这就是最常用的基-2FFT算法. 如果序列不满足这个条件,可以人为地加上若干零点得到.;第二节 按时间抽取FFT算法;是x(n)按n为奇、偶数分为2个子序列，得:;上式可写为:;其中: ;上式表明一个N点的DFT可以分解成两个 点的 DFT. 这两个 点的DFT又可按式合成一个N点 DFT 一个问题: 和 的长度为 , 它们的DFT 和 的点数也为 , 而x(k)却有N个点。 利用 的周 期性解决这一问题，即：;表达为前后两个部分:;这样只要求出0 ~ -1 区间所有 和 ,就可以求出0~N-1 区间内全部X(k)的值.这就是FFT运算的关键所在。用以下信号流图表示为：;复乘: 1 复加: 2; 仍为偶数,可以;第二级分解; 与第一级分解一样,利用 和 隐含的周期性, 为 改写为前，后两部分:;由此一个 ;也可以进行同样分解:;第二节 按时间抽取FFT算法;为 ;系数统一为 (今后都使用统一的系数),这样,;根据前面的分析,第二级分解组合比第一级分解后的 运算量又降低了一半.; 例如 组成的2点DFT 可用??式计算: 类似,其它3个2点长DFT都可以用一个蝶式运算单元求得,综合这三级分解过程,可得到一个完整的8点DFT信号流图.;第二节 按时间抽取FFT算法; 运算量分析 由DIT FFT信号流图可见,对于任何一个 点DFT运算,都可以通过M次分解,最后分解成2点DFT运算的组合.这样的M级分解,就构成了M级运算过程.每级N/2个蝶形运算. 每一级: 复乘: 复加: ;结论: DIF FFT运算量与 近似成正比.;第二节 按时间抽取FFT算法; 为节点，m：表示第m列叠代。p,q：为数据所在行数，对应信号流图下图所示：;第二节 按时间抽取FFT算法;（2） 的确定 每一级的旋转因子都不相同，但排列很有规律，下表所示。;2. 原址运算;第二节 按时间抽取FFT算法;存储器号 数据;倒位序排列是由于不断将DFT运算分解为较小点数DFT计算造成的。序列x(n)首先分成偶数标号和奇数标号两个子序列：偶数序列出现在流图上半部,奇数序列出现在流图下半部。从形式上说,这样的划分可通过分析标号n的二进制表示 的最低位 来实现。标号为偶数，则 =0，标号为奇数，则 =1。这样 =0的标号出现在流图上半部; =1的标号出现在下半部。下一次奇偶序列的分解又分别根据标号二进制表示的倒数第二位 开始,根据 分别将第一次分解生成的两个子序列再一次按奇偶性分开。持续该过程,直得到N个长度为1的子序列。最后的排列顺序呈”倒位序”;所