第9章 离散傅里叶变换的计算.ppt

9.0 引言 降低离散傅里叶变换的计算量 方法： 利用离散傅里叶变换系数的对称性和周期性 主要算法： Goertzel算法 按时间抽取的FFT算法 按频率抽取的FFT算法 里程碑： 1965年 Cooley Tukery 9.1 离散傅里变换的高效计算 N点有限长序列的DFT： 傅里叶变换系数的性质 对称性（复共轭对称） 利用对称性可直接计算n 和 N-n 离散傅里变换快速算法的寻找过程 1805年的高斯 Runge(1905),Danielson Lanczos(1942)指出DFT的计算量正比于N log N 而不是NN。 1965年Cooley Tukery的论文指出，当N为复合数时，可以进行分解。该论文为DFT的快速算法的发现指出了一条行之有效的方法。此后出现了一大批快速算法：按时间抽取的FFT算法、按频率抽取的FFT算法、素因子法等等。 9.2 Goertzel算法 利用了周期性 计算量 极点： 2次实乘 4次实加（每个样本的计算量） 2N次实乘 4N次实加 零点： 迭代的最后一次计算 4次实乘 4次实加 共需： 2N2+4N次实乘 4N2+4N次实加 利用共轭对称 一次可以算出两个点的极点，零点复共轭。所以一次可以算出两个点。 N2+2N次实乘 2N2+2N次实加 可以计算N点DFT其中的任意长（M） 其计算量MN 9.3 按时间抽取的FFT算法 一.DFT的计算工作量 通常x(n)和 都是复数,所以计算一个X(k)的值需要N次复数乘法运算,和 次复数加法运算.那么,所有的X(k)就要N2次复数乘法运算,N(N-1)次复数加法运算.当N很大时,运算量将是惊人的,如N=1024,则要完成1048576 次(一百多万次)运算.这样,难以做到实时处理. 二.改进的途径 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倍 按时间抽取(DIT)的FFT算法 —库利-图基算法 一.算法原理(基2FFT) (一)N/2点DFT 由于: 所以,上式可表示为: 9.6 用卷积实现DFT 有些情况下卷积比FFT的计算量小 9.6.1 Winograd 傅里叶变换 其计算量：乘法的计算量正比于N。但加法的计算量多，因此适合乘法比加法运算慢的多得场合。 对于具有乘加单元的DSP等还是FFT快。 9.6.2 线性调频变换算法 因果化—右移N-1 完成FFT 作业： P539 9.1、9.3 3.蝶形运算 -1 4.N=8时,按k的奇偶分解过程 先蝶形运算，后DFT: -1 -1 -1 -1 W W W W N N N N 0 1 2 3 5.仿照DIT的方法 再将N/2点DFT按k的奇偶分解为两个 N/4点的DFT,如此进行下去,直至分解为 2点DFT。 (0) X(0) (1) X(4) (2) X(2) (3) X(6) (4) X(1) (5) X(5) (6) X(3) (7) X(7) -1 -1 -1 -1 W W W W N N N N 0 1 2 3 -1 -1 -1 -1 W W W W N N N N 0 2 0 2 -1 -1 -1 -1 W W W W N N N N 0 0 0 0 例如 N=8时DIF的FFT流图如下： 二.原位运算 每级(列)都是由N/2个蝶形运算构成,即 -1 W N r 三.蝶形运算两节点的距离 一般公式为2L-m =N/2m 例如 N=23 =8 ： (1)m=1 时的