数字信号处理及Matlab实现课件作者李辉第4章节.ppt

§4.1引言 DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化，从而使DFT的运算在实际中真正得到了广泛的应用。 §4.2 直接计算DFT的问题及改进的途径 一.DFT的计算工作量 两者的差别仅在指数的符号和因子1/N. 二.改进的途径 1. 的对称性和周期性 利用上述特性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度.1965年,库利(cooley)和图基 (Tukey)首先提出FFT算法.对于N点DFT,仅需 (N/2)log2N 次复数乘法运算.例如N=1024=210 时， 需要(1024/2)log2 210 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍 §4.3 按时间抽取(DIT)的基-2 FFT算法 —库利-图基算法 一.算法原理(基-2FFT) (一)N/2点DFT 1.先将 按n的奇偶分为两组作DFT,设N=2L ,不足时,可补些零。这样有: n为偶数时: n为奇数时: 由于: 所以,上式可表示为: 其中, 2.两点结论: (1) X (k),X (k)均为N/2点的DFT。 (2) X(k)=X (k)+W X (k)只能确定出 X(k)的k= 个； 即前一半的结果。 有 一个N点的DFT计算转化为4个 的DFT计算和一级蝶形复合，计算过程下图所示 。 二、基-4 FFT运算次数 每个基本的4点FFT都不需要乘法，算法中只有乘旋转因子才有复数乘法，而每一个4点DFT只有3次乘旋转因子(有一个旋转因子 ，不需要乘)。而每一级(基-4 FFT的一级)有 个4点DFT，因而每级总共需要 次复乘。由于 ，则共有L级，但由于这里第一级运算不乘旋转因子，因而总的复乘次数(考虑到 )为 L1 而已知基-2 FFT的复乘次数为 ，因此，基-4 FFT比基-2 FFT乘法运算量更加节省。 §4-6 离散傅里叶反变换(IDFT)的快速计算方法 一.稍微变动FFT程序和参数可实现IFFT 利用FFT法求线性相关是用圆周相关代替线性相关，选择 ，且 （ 为整数)，令 当m=2时,则有（前两个蝶形） 当m=3时,则有（前两个蝶形） 可见,在某列进行蝶形运算的任意两个节点(行)k和j的节点变量 就完全可以确定蝶形运算的结果 ,与其它行(节点)无关。 这样,蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中,即实现所谓原位运算。每一组(列)有N/2个蝶形运算,所以只需N个存储单元，可以节 省存储单元。 2 倒位序规律 由图可知,输出X(k)按正常顺序排 列在存储单元,而输入是按顺序: 这种顺序称作倒位序,即二进制数 倒位。 n =0 0 n =1 0 n =0 1 n =1 1 n =0 1 n =1 1 0 1 0 1 0 1 0 1 (n2) x(000) 0 乾 x(100) 4 兑 x(010) 2 离 x(110) 6 震 x(001) 1巽 x(101) 5 坎 x(011) 3 艮 x(111) 7 坤 （偶） （奇） 这是由奇偶分组造成的,以N=8为例 说明如下: 3.倒位序实现 输入序列先按自然顺序存入存储单 元,然后经变址运算来实现倒位序排列 设输入序列的序号为n,二进制为 (n2 n1 n0 )2 ,倒位序顺序用 表示,其倒位序二进制为(n0 n1 n2 )2 ,例如 ，N=8时如下表： 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2