华科-机械工程测试信息信号分析-课件-ch6-03-数字信号分析.ppt

MEASUREMENT

INFORMATION

SIGNALANALYSIS

INMECHANICALENGINEERING;课件资料下载：

邮箱地址：

密码：

注意下载时不要删除原始文件;第六章数字信号分析(I)

DFT与FFT;§6-5现代谱分析方法-最大熵谱估计;6-3FFT算法;通常x(n)和WNnk都是复数，所以计算一个x(k)的值需要N次复数乘法运算，和N-1次复数加法运算。那么，所有的X(k)就要N2次复数乘法运算，N(N-1)次复数加法运算。当N很大时，运算量将是惊人的,如N=1024，那么要完成1048576次(一百多万次)运算。难以做到实时处理。;、改进的途径;利用上述特性，可以将有些项合并，并将DFT分解为短序列，从而降低运算次数，提高运算速度。1965年，库利(cooley)和图基(Tukey)首先提出FFT算法。对于N点DFT，仅需(N/2)log2N次复数乘法运算。例如N=1024=210时，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%，速度提高20倍。;、库利-图基算法;库利-图基算法;库利-图基算法;库利-图基算法;库利-图基算法;4.蝶形运算;5.计算工作量分析;例如：N=8时的DFT,可以分解为两个N/2=4点的DFT。具体方法如下：

(1)n为偶数时，即x(0)，x(1)，x(2)，x(3)；

分别记作：;(2)n为奇数时，分别记作:;x1(0)=x(0)

x1(1)=x(2)

x1(2)=x(4)

x1(3)=x(6)

x2(0)=x(1)

x2(1)=x(3)

x2(2)=x(5)

x2(3)=x(7);(二)N/4点DFT

由于N=2L，所以N/2仍为偶数，可以进一步把每个N/2点的序列再按其奇偶局部分解为两个N/4的子序列。例如，n为偶数时的N/2点分解为:;从而可得到前N/4点的X1(k);;例如，N=8时的DFT可分解为四个N/4的DFT，具体步骤如下：;(2)将原序列x(n)的“偶中奇”局部:;(4)将原序列x(n)的“奇中奇”局部:;-1;这样,又一次分解,得到四个N/4点DFT，两级蝶形运算，其运算量有大约减少一半即为N点DFT的1/4。

对于N=8时DFT，N/4点即为两点DFT，因此;亦即,;-1;此FFT算法，是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的，所以称作按时间抽取的算法(DIT)。

二、运算量

由上述分析可知，N=8需三级蝶形运算N=2=8，由此可知，N=2L共需L级蝶形运算,而且每级都由N/2个蝶形运算组成，每个蝶形运算有一次复乘，两次复加。;因此，N点???FFT的运算量为：

复乘:mF=(N/2)L=(N/2)log2N

复加:aF=NL=Nlog2N

由于计算机的乘法运算比加法运算所需的时间多得多，故以乘法运算作为比较基准。;三、DIT的FFT算法的特点;由运算流图可知，一共有N个输入/出行，一共有log2N=L列(级)蝶形运算(根本迭代运算)。

设用m(m=1,2,…,L)表示第m列；用k,j表示蝶形输入数据所在的(上/下)行数(0,1,2,…,N-1)；这时任何一个蝶形运算可用下面通用式表示，即：;所以，当m=1时，那么有〔前两个蝶形〕;当m=2时，那么有(前两个蝶形);可见，在某列进行蝶形运算的任意两个节点(行)k和j的节点变量Xm-1(k)，Xm-1(j)就完全可以确定蝶形运算的结果Xm(k)，Xm(j)，与其它行(节点)无关。这样，蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中，即实现所谓原位运算。每一组(列)有N/2个蝶形运算，所以只需N个存储单元，可以节省存储单元。;2.倒位序规律

由图可知，输出X(k)按正常顺序排列在存储单元，而输入是按顺序：;n0=0，(偶);3.倒位序实现

输入序列先按自然顺序存入存储单元，然后经变址运算来实现倒位序排列

设输入序列的序号为n，二进制为(n2n1n0)2，倒位序顺序用表示，其倒位序二进制为(n0n1n2)2，例如，N=8时如下表：;00000000

10011004

2