离散傅里叶变换.ppt
测试信号分析与处理课程,第四章 离散傅里叶变换及其快速算法,数字谱分析是数字信号处理的基本内容，通过对信号的频谱分析，掌握信号特征，以便对信号作进一步处理，达到提取有用信息的目的。包括序列的傅立叶变换、离散傅立叶级数、离散傅立叶变换和快速傅立叶变换第一节 序列的傅里叶变换 第二节 离散傅里叶级数（DFS）第三节 离散傅里叶变换（DFT）第四节 离散傅里叶变换的性质,测试信号分析与处理课程,第五节 快速傅里叶变换第六节 IDFT的快速算法（IFFT）第七节 实序列的FFT高效算法第八节 频率域采样理论,第一节 序列的傅里叶变换,已知序列x(n)的Z变换为：如X(Z)在单位圆上是收敛的，则将在单位圆上的Z变换定义为序列的傅里叶变换，即 序列的傅立叶变换定义为单位圆上的Z变换，因此其同Z变换具有相同的性质,一、定义,二、物理意义与存在条件,序列傅立叶变换存在条件,序列必须绝对可和,比较这两个反变换,三、特点与应用,非周期序列的傅里叶变换（频谱）的特点在于它是 周期为 的连续周期函数，其周期为。,是连续周期函数，因此也可以进行傅立叶级数展开,序列可以表示为复指数序列分量的叠加，而对复指数序列的响应完全由系统的频率响应 确定，既可以推出输出的傅立叶变换为：,三、特点与应用,第二节 离散傅里叶级数（DFS）,一、傅里叶变换在时域和频域中的对称规律,第二节 离散傅里叶级数（DFS）,第二节 离散傅里叶级数（DFS）,一个域中（时域或频域）是连续的，对应另一个域中（频域或时域）是非周期的。一个域中（时域或频域）是离散的，对应另一个域中（频域或时域）是周期的。,第二节 离散傅里叶级数（DFS）,二、离散傅里叶级数（定量表达周期序列的傅立叶级数展开式）离散周期信号的频谱，即离散傅里叶级数(DFS)。非周期序列的频谱一个非周期序列x(n)可以分解为一系列连续的不同频率的复指数序列 的叠加积分，其频谱 表示了这些不同频率分量的复幅度，频率是周期性的，独立分量在 到 之间。,周期序列的频谱是非周期序列频谱的离散化，根据频谱的含义，意味着一个周期序列可以分解成一系列 为离散（）的指数序列分量 的叠加，其频率间隔：设任意k次频率的复指数序列分量 的复幅度用 表示，则可以推出周期序列的傅立叶级数变换对。,离散傅里叶级数的变换对表达式,离散傅立叶级数的正反变换，为数字信号分析和处理做好了理论准备，因为时域和频域都是离散化；但是他们都是周期序列，需要在理论上对序列的有限化进一步研究，以解决离散信号分析处理或系统设计以及实现等实用化方面的问题。,第三节 离散傅里叶变换（DFT）,第三节 离散傅里叶变换（DFT）,一、离散傅里叶变换DFT定义式离散傅里叶变换就是对有限长序列进行傅里叶变换的表示式。定义一个周期序列在第一个周期内的有限长序列值为此周期序列的主值区间，表示为：正变换反变换,第三节 离散傅里叶变换（DFT）,矩阵形式或,第三节 离散傅里叶变换（DFT）,二、DFT的物理意义 1 非周期序列的频谱，即它的傅立叶变换，是一个连续的周期性频谱；2 有限长序列的DFT却是离散的序列，两者虽然不同，但存在着重要的联系。可以证明：有限长序列的傅立叶变换DFT是该序列频谱的抽样值。,有限长序列的DFT就是序列在单位圆上的Z变换（即有限长序列的傅里叶变换或频谱）以 为间隔的抽样值,第四节 离散傅里叶变换的性质,线性特性 时移特性 1）圆周移位序列2）时移定理频移特性,过程、圆移位,序列在时域中圆周移位，频域上将产生附加相移,序列在时域上乘于复指数序列，则在频域上将发生圆周移位,第四节 离散傅里叶变换的性质,圆周卷积特性 1）时域圆周卷积 2）频域圆卷积 若实数序列奇偶性（对称性）帕斯瓦尔定理：变换过程中能量是守恒的。,顺时针,左移,逆时针转动,再顺时针读数.,H(-n)NRN(n),H(1-n)NRN(n),H(2-n)NRN(n),H(3-n)NRN(n),y(0),例：长度为4的两个有限长序列x(n)=1,2,3,4和h(n)=4,3,2,1)计算其循环卷积（圆周卷积）解：将x(n)按逆时针方向依次均匀分布在内圆上，将序列h(n)按顺时针方向依次均匀分布在外圆上，依次逆时针旋转外圆，增加时间序号，将内外圆数值对应相乘并求和。得到y(n)=24,22,24,30.,第五节 快速傅里叶变换,DFT是利用计算机进行信号谱分析的理论依据，但计算量太大；快速傅立叶变换是以较少计算量实现DFT的快速算法，FFT是数字信号处理中最基本的算法。本节分析直接计算的工作量及DFT的特点，最后研究基2时析型FFT（基2时间抽选法）一、DFT直接运算的工作量,计算机运算时（编程实现）：,运算量,(a+jb)(c+jd)=(ac-bd)+j(bc+ad),第五节 快速傅里叶变换,按定义计算，需要 次复数乘和(N-1)N次复数加运算，若序列为复数，则每次复数乘包括4次实数乘和2次实数加，每次复数加包含2次实数加，因此对于长度为N的序列，运算总共有4 次实数乘和2+2(N-1)N次实数加。随着N的增加，实时处理就无法实现。,例：计算一个 N点DFT，共需N2次复乘。以做一次 复乘1s计，若N=4096，所需时间为,例：石油勘探，有24个通道的记录，每通道波形记 录长度为5秒，若每秒抽样500点/秒，1）每通道总抽样点数：500*5=2500点 2）24通道总抽样点数：24*2500=6万点 3）DFT复乘运算时间：N2=(60000)2=36*108次,由于计算量大，且要求相当大的内存，难以实现实时处理，限制了DFT的应用。长期以来，人们一直在寻求一种能提高DFT运算速度的方法。,FFT便是 Cooley&Tukey 在1965 年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。,第五节 快速傅里叶变换,二、DFT运算的特点（从公式入手，利用自身运算特点，提出解决问题的方法）1 的周期性，即对变量n和k，均为周期函数2 的对称性,利用周期性和对称性，使W中的元素许多变成相等的，从而减少计算量。除此之外，将大点数DFT转化为小点数DFT，也可以减少DFT的计算量。,其中l和m为整数。,第五节 快速傅里叶变换,二、基2时析型FFT算法（时间抽取法）输入序列的长度是2的整数次幂1.算法原理 对长度为（L为正整数，若原序列的长度不满足此条件，则可用零补足）的序列x(n),按序列各项序号的奇偶将序列分成两个子序列（大点数化为小点数），有偶序号序列 奇序号序列,上式中 分别为 的N/2点DFT，即：,这是 前N/2点DFT,对于 后N/2点的DFT,显然，可采用蝶式运算图来表示上述前N/2和后N/2两式，如下图所示：,X(n)的DFT最后结果,根据奇偶对分，最后一定能得到N个单项序列（序列长度为1），而单项序列的DFT就是其本身。计算N项序列的DFT，只需要按照碟形算法逐次合成，由N个1点长序列的DFT合成N/2个2点长序列的DFT，再由N/2个2点长序列的DFT合成N/4个4点长序列的DFT，依次进行，最后得到N点长序列的DFT。,第五节 快速傅里叶变换,2.算法的具体实现,第五节 快速傅里叶变换,3.流程图规律1),2点组成一个基本的运算单元，称为蝶形单元，相互交叠的蝶形单元构成一个蝶群，每级由一系列的蝶群组成。蝶形单元的宽度为蝶距，蝶群的宽度为蝶群宽。,第五节 快速傅里叶变换,2）L级蝶形运算，每一级都是“同址运算”，就是每级计算结果都占用同一地址单元，无需要另开存储空间。3）每个蝶形单元的运算，都包括乘，并与相应的DFT结果加减各一次 4）同一级中，的分布规律相同第i级(点DFT):;.;,5）时间序列是按时间先后顺序排列的，称为自然顺序，但FFT计算时，需要符合快速算法的要求，需要一种乱序输入，才能获得X(K)按自然顺序的输出，也就是需要对输入进行相应处理，即所谓的码位倒置或输入重排。,第五节 快速傅里叶变换,4 输入重排（输入序列不再为原序列的自然顺序，需要重排）,第五节 快速傅里叶变换,5.运算量比较N（）点的FFT总运算量为复数乘复数加 利用基2时析型FFT求序列的DFT同直接计算序列的DFT的复数乘运算次数之比为,DFT有快速算法FFT，IDFT是否有快速算法呢？IFFT是IDFT的快速算法。,第六节 IDFT的快速算法（IFFT）,一、IFFT算法在FFT的时间抽取算法中，第一次分解的结果是,第六节 IDFT的快速算法（IFFT）,依次类推，可以求出x(n)的各点，下面是整个8点IFFT的信号流程图。,如果不在每次迭代后增加1/2，可以最后的输出序列中每个元素除以N。,二、利用FFT的程序求IFFT的方法,IFFT与FFT的信号流图还是存在区别，不能用FFT程序实现IFFT算法。,输入序列变输出序列，WN的不同，输出序列的每个元素除以N，是X(k)倒序重排，x(n)自然顺序排列。,X(k)的共轭作为输入，结果取共轭，再除以N就得到了x(n)。,第七节 实序列的FFT高效算法,当输入序列为实数数据时，进一步可以提高FFT运算效率同时计算两组实序列的DFT（两组同长序列构成新的序列）,由于x(n)和y(n)为实序列，有,用N点序列的DFT结果获得2N点长实序列的DFT结果,求出z(n)对应的Z(K)，可以得到x(n)和y(n)对应的X(K)和Y(K).,x1(n)和x2(n）组成一个复序列，利用上面的结果求出X1(K)和X2(K),第八节 MATLAB中用于FFT计算的函数,一 函数 fft二 函数ifft 一维快速傅立叶正逆变换三 应用实例t=0:0.001:0.6;x=sin(2*pi*50*t)+sin(2*pi*120*t);y=x+1.5*randn(1,length(t);正弦信号与随机噪声叠加Y=fft(y,512);求含噪声信号的离散傅立叶变换（数字谱）P=Y.*conj(Y)/512;计算功率谱f=1000*(0:255)/512;plot(f,P(1:256);功率谱中在频率50HZ，120HZ处存在该频率的成分,第九节 频率域采样理论,时域采样定理：在一定条件下可以由时域离散采样信号恢复原来的连续信号，其中内插函数是取样函数。X(K)是怎么样得到的？序列傅立叶变换的采样值得到，能否由X(K)恢复原来的时域信号或者原来的频谱函数呢？,推导过程见书本，结论是：任意序列x(n)，对应的Z变换为X(z)，X(z)在单位圆上的z变换就是序列的傅立叶变换，具有连续的频谱，将其作N点等间隔采样，得到X(k),再作IDFT，得到的不一定是x(n)本身，而是x(n)以N为周期的周期延拓序列的主值序列。,第九节 频率域采样理论,频域采样定理 如果序列x(n)的长度为M,则只有当频域采样点数 时，才有即可由频域采样 X(k)恢复原序列x(n)，否则产生时域混叠现象。上式称为频域采样定理。由X(k)恢复X(z)的内插公式和内插函数分别为书本公式4-38和4-39。作业1，9，10,
