第4章 离散傅里叶变换PPT讲稿.ppt

《第4章 离散傅里叶变换PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第4章 离散傅里叶变换PPT讲稿.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 离散傅里叶离散傅里叶变换第1页，共59页，编辑于2022年，星期一测试信号分析与处理课程测试信号分析与处理课程第五节第五节 快速傅里叶变换快速傅里叶变换第六节第六节 IDFT IDFT的快速算法（的快速算法（IFFTIFFT）第七节第七节 实序列的实序列的FFTFFT高效算法高效算法第八节第八节 频率域采样理论频率域采样理论第2页，共59页，编辑于2022年，星期一第一节第一节 序列的傅里叶变换序列的傅里叶变换 v已知序列x(n)的Z变换为：v如X(Z)在单位圆上是收敛的，则将在单位圆上的Z变换定义为序列的傅里叶变换，即 v序列的傅立叶变换定义为单位圆上的Z变换，因此其同Z变换具有

2、相同的性质一、定义一、定义第3页，共59页，编辑于2022年，星期一v二、物理意义与存在条件 x(t)x(n)正变换 反变换 分析 综合连续非周期连续周期序列傅立叶变换存在序列傅立叶变换存在条件条件序列必须绝对可和序列必须绝对可和比较这两个反变换比较这两个反变换第4页，共59页，编辑于2022年，星期一三、特点与应用三、特点与应用v非周期序列的傅里叶变换（频谱）的特点在于它是 周期为 的连续周期函数，其周期为 。是连续周期函数，因此也可以进行傅立叶级数展开是连续周期函数，因此也可以进行傅立叶级数展开第5页，共59页，编辑于2022年，星期一v序列可以表示为复指数序列分量的叠加，而对复指数序列的

3、响应完全由系统的频率响应 确定，既可以推出输出的傅立叶变换为：三、特点与应用三、特点与应用第6页，共59页，编辑于2022年，星期一第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）一、傅里叶变换在时域和频域中的对称规律一、傅里叶变换在时域和频域中的对称规律v 第7页，共59页，编辑于2022年，星期一第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v 第8页，共59页，编辑于2022年，星期一第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v一个域中（时域或频域）是连续的，对应另一个域中（频域或时域）是非周期的。v一个域中（时域或频域）是离散的，对应另一个域中（频域或时域）是

4、周期的。第9页，共59页，编辑于2022年，星期一第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）二、离散傅里叶级数（二、离散傅里叶级数（定量表达周期序列的傅立叶级数展开式定量表达周期序列的傅立叶级数展开式）v离散周期信号的频谱，即离散傅里叶级数(DFS)。v非周期序列的频谱v一个非周期序列x(n)可以分解为一系列连续的不同频率的复指数序列 的叠加积分，其频谱 表示了这些不同频率分量的复幅度，频率是周期性的，独立分量在 到 之间。第10页，共59页，编辑于2022年，星期一v周期序列的频谱是非周期序列频谱的离散化，根据频谱的含义，意味着一个周期序列可以分解成一系列 为离散（）的指数序列分

5、量 的叠加，其频率间隔：v设任意k次频率的复指数序列分量 的复幅度用 表示，则可以推出周期序列的傅立叶级数变换对。第11页，共59页，编辑于2022年，星期一v离散傅里叶级数的变换对表达式 第12页，共59页，编辑于2022年，星期一v离散傅立叶级数的正反变换，为数字信号分析和处理做好了理论准备，因为时域和频域都是离散化；v但是他们都是周期序列，需要在理论上对序列的有限化进一步研究，以解决离散信号分析处理或系统设计以及实现等实用化方面的问题。第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）第13页，共59页，编辑于2022年，星期一第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）一

6、、离散傅里叶变换一、离散傅里叶变换DFT定义式定义式v离散傅里叶变换就是对有限长序列进行傅里叶变换的表示式。定义一个周期序列在第一个周期内的有限长序列值为此周期序列的主值区间，表示为：正变换反变换 第14页，共59页，编辑于2022年，星期一第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）v矩阵形式或 第15页，共59页，编辑于2022年，星期一第16页，共59页，编辑于2022年，星期一第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）二、二、DFT的物理意义的物理意义 1 非周期序列的频谱，即它的傅立叶变换，是一个连续的周期性频谱；2 有限长序列的DFT却是离散的序列，两者虽然不

7、同，但存在着重要的联系。可以证明：有限长序列的傅立叶变换DFT是该序列频谱的抽样值。第17页，共59页，编辑于2022年，星期一v有限长序列的DFT就是序列在单位圆上的Z变换（即有限长序列的傅里叶变换或频谱）以 为间隔的抽样值 第18页，共59页，编辑于2022年，星期一第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v线性特性线性特性 v时移特性时移特性 1）圆周移位序列2）时移定理v频移特性频移特性 过程、圆移位过程、圆移位序列在时域中圆周移位，频域上将产生附加相移序列在时域中圆周移位，频域上将产生附加相移序列在时域上乘于复指数序列，则在频域上将发生圆周移位序列在时域上乘于复指数序列

8、，则在频域上将发生圆周移位第19页，共59页，编辑于2022年，星期一第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v圆周卷积特性 1）时域圆周卷积 2）频域圆卷积 若v实数序列奇偶性（对称性）v 帕斯瓦尔定理：变换过程中能量是守恒的。第20页，共59页，编辑于2022年，星期一第21页，共59页，编辑于2022年，星期一第22页，共59页，编辑于2022年，星期一第23页，共59页，编辑于2022年，星期一第24页，共59页，编辑于2022年，星期一第25页，共59页，编辑于2022年，星期一顺时针顺时针,左移左移,逆时针转动逆时针转动,再再顺时针读数顺时针读数.第26页，共59页，

9、编辑于2022年，星期一H(-n)NRN(n)H(1-n)NRN(n)H(2-n)NRN(n)H(3-n)NRN(n)y(0)第27页，共59页，编辑于2022年，星期一例：长度为例：长度为4的两个有限长序列的两个有限长序列x(n)=1,2,3,4和和h(n)=4,3,2,1)计算其循环卷积（圆周卷积）计算其循环卷积（圆周卷积）解：将解：将x(n)按逆时针方向依次均匀分布在内圆上，将序列按逆时针方向依次均匀分布在内圆上，将序列h(n)按顺按顺时针方向依次均匀分布在外圆上，依次逆时针旋转外圆，增加时时针方向依次均匀分布在外圆上，依次逆时针旋转外圆，增加时间序号，将内外圆数值对应相乘并求和。得到间

10、序号，将内外圆数值对应相乘并求和。得到y(n)=24,22,24,30.第28页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换DFT是利用计算机进行信号谱分析的理论依据，但计算量太大；是利用计算机进行信号谱分析的理论依据，但计算量太大；快速傅立叶变换是以较少计算量实现快速傅立叶变换是以较少计算量实现DFT的快速算法，的快速算法，FFT是数字信号处理是数字信号处理中最基本的算法。本节分析直接计算的工作量及中最基本的算法。本节分析直接计算的工作量及DFT的特点，最后研究基的特点，最后研究基2时时析型析型FFT（基（基2时间抽选法）时间抽选法）一、一、DFT直接运算的

11、工作量直接运算的工作量第29页，共59页，编辑于2022年，星期一计算机运算时（编程实现）：计算机运算时（编程实现）：N N次复乘，次复乘，次复乘，次复乘，N-1N-1次复加次复加次复加次复加 N N个点个点个点个点 第30页，共59页，编辑于2022年，星期一复数乘法复数加法一个X(k)NN 1N个X(k)(N点DFT)N 2N(N 1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N 1)=2(2N 1)N个X(k)(N点DFT)4N 22N(2N 1)运算量运算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)第31页，共59页，编辑于2022年，星期一第五节

12、第五节 快速傅里叶变换快速傅里叶变换按定义计算，需要按定义计算，需要 次复数乘和次复数乘和(N-1)N次复数加运算，若序列为复数，次复数加运算，若序列为复数，则每次复数乘包括则每次复数乘包括4次实数乘和次实数乘和2次实数加，每次复数加包含次实数加，每次复数加包含2次实数加，次实数加，因此对于长度为因此对于长度为N的序列，运算总共有的序列，运算总共有4 次实数乘和次实数乘和2 +2(N-1)N次实次实数加。随着数加。随着N的增加，实时处理就无法实现。的增加，实时处理就无法实现。第32页，共59页，编辑于2022年，星期一例：计算一个例：计算一个 N点点DFT，共需，共需N2次复乘次复乘。以做一次

13、。以做一次 复乘复乘1s计，若计，若N=4096，所需时间为，所需时间为例：石油勘探，有例：石油勘探，有24个通道的记录，每通道波形记个通道的记录，每通道波形记 录长度为录长度为5秒，若每秒抽样秒，若每秒抽样500点点/秒，秒，1）每通道总抽样点数：）每通道总抽样点数：500*5=2500点点 2）24通道总抽样点数：通道总抽样点数：24*2500=6万点万点 3）DFT复乘运算时间：复乘运算时间：N2=(60000)2=36*108次次第33页，共59页，编辑于2022年，星期一 由于计算量大，且要求由于计算量大，且要求相当大的内存相当大的内存，难以实现实时处理难以实现实时处理，限制了限制了

14、DFT的应用。长期以来，人们一直在寻求一种能的应用。长期以来，人们一直在寻求一种能提高提高DFT运算速度运算速度的方法。的方法。FFT便是便是 Cooley&Tukey 在在1965 年提出的的快速算年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。科成为一个新兴的应用学科。第34页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换二、二、DFT运算的特点（运算的特点（从公式入手，利用自身运算特点，提出解决问题的从公式入手，利用自身运算特点，提出解决问题的方法方法）1 的

15、周期性，即对变量n和k，均为周期函数2 的对称性 利用周期性和对称性，使利用周期性和对称性，使W中的元素许多变成相等的，从而减中的元素许多变成相等的，从而减少计算量。除此之外，将大点数少计算量。除此之外，将大点数DFT转化为小点数转化为小点数DFT，也可，也可以减少以减少DFT的计算量。的计算量。其中其中l和和m为整数。为整数。第35页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换二、基二、基2时析型时析型FFT算法（算法（时间抽取法时间抽取法）输入序列的长度是输入序列的长度是2的整数次幂的整数次幂1.1.算法原理算法原理 对长度为对长度为 （L L为正整数，若

16、原序列的长度不为正整数，若原序列的长度不满足此条件，则可用零补足）的序列满足此条件，则可用零补足）的序列x(n),x(n),按序列各项按序列各项序号的奇偶将序列分成两个子序列（大点数化为小点数）序号的奇偶将序列分成两个子序列（大点数化为小点数），有，有偶序号序列偶序号序列 奇序号序列奇序号序列第36页，共59页，编辑于2022年，星期一上式中上式中 分别为分别为 的的N/2N/2点点DFTDFT，即：，即：这是这是 前前前前N/2N/2点点点点DFTDFT第37页，共59页，编辑于2022年，星期一对于对于 后后后后N/2N/2点点点点的的DFTDFT显然，可采用显然，可采用蝶式运算图蝶式运算

17、图蝶式运算图蝶式运算图来表示上述前来表示上述前N/2N/2和后和后N/2N/2两式两式 ，如下图，如下图所示：所示：第38页，共59页，编辑于2022年，星期一vX(n)X(n)的的DFTDFT最后结果最后结果根据奇偶对分，最后一定能得到根据奇偶对分，最后一定能得到N个单项序列（序列长度为个单项序列（序列长度为1），），而单项序列的而单项序列的DFT就是其本身。计算就是其本身。计算N项序列的项序列的DFT，只需要按，只需要按照碟形算法逐次合成，由照碟形算法逐次合成，由N个个1点长序列的点长序列的DFT合成合成N/2个个2点长序点长序列的列的DFT，再由，再由N/2个个2点长序列的点长序列的DF

18、T合成合成N/4个个4点长序列的点长序列的DFT，依次进行，最后得到，依次进行，最后得到N点长序列的点长序列的DFT。第39页，共59页，编辑于2022年，星期一第40页，共59页，编辑于2022年，星期一第41页，共59页，编辑于2022年，星期一第42页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换2.2.算法的具体实现算法的具体实现 第43页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换3.3.流程图规律流程图规律1)1)蝶群序号蝶距（序号差）蝶群宽（点数）蝶群数第一级（2点DFT）第i级（点DFT)2点组成一个基本的运算单

19、元，称为蝶形单元，相互交叠的蝶点组成一个基本的运算单元，称为蝶形单元，相互交叠的蝶形单元构成一个蝶群，每级由一系列的蝶群组成。蝶形单元的形单元构成一个蝶群，每级由一系列的蝶群组成。蝶形单元的宽度为蝶距，蝶群的宽度为蝶群宽。宽度为蝶距，蝶群的宽度为蝶群宽。第44页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换2 2）L L级蝶形运算，每一级都是级蝶形运算，每一级都是“同址运算同址运算”，就，就是每级计算结果都占用同一地址单元，无需要是每级计算结果都占用同一地址单元，无需要另开存储空间。另开存储空间。3 3）每个蝶形单元的运算，都包括乘）每个蝶形单元的运算，都包括乘

20、 ，并，并与相应的与相应的DFTDFT结果加减各一次结果加减各一次 4 4）同一级中，）同一级中，的分布规律相同的分布规律相同第第i i级级(点点DFT):;.;DFT):;.;第45页，共59页，编辑于2022年，星期一v5）时间序列是按时间先后顺序排列的，称为自然顺序，但FFT计算时，需要符合快速算法的要求，需要一种乱序输入，才能获得X(K)按自然顺序的输出，也就是需要对输入进行相应处理，即所谓的码位倒置或输入重排。第46页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换序列输入的自然顺序十进制二进制码码位倒置结果（二进制码）乱序十进制序列乱序的输入顺序4 输

21、入重排（输入重排（输入序列不再为原序列的自然顺序，需要重排）输入序列不再为原序列的自然顺序，需要重排）第47页，共59页，编辑于2022年，星期一第五节第五节 快速傅里叶变换快速傅里叶变换5.5.运算量比较运算量比较N N（）点的）点的FFTFFT总运算量为总运算量为复数乘复数乘复数加复数加 利用基利用基2 2时析型时析型FFTFFT求序列的求序列的DFTDFT同直接计算序同直接计算序列的列的DFTDFT的复数乘运算次数之比为的复数乘运算次数之比为第48页，共59页，编辑于2022年，星期一DFT有快速算法有快速算法FFT，IDFT是否有快速算法呢？是否有快速算法呢？IFFT是是IDFT的快速

22、算法。的快速算法。第49页，共59页，编辑于2022年，星期一第六节第六节 IDFT IDFT的快速算法（的快速算法（IFFTIFFT）一、一、IFFTIFFT算法算法在在FFTFFT的时间抽取算法中，第一次分解的结果是的时间抽取算法中，第一次分解的结果是 第50页，共59页，编辑于2022年，星期一第六节第六节 IDFT IDFT的快速算法（的快速算法（IFFTIFFT）依次类推，可以求出依次类推，可以求出x(n)的各点，下面是整个的各点，下面是整个8点点IFFT的信号流程图。的信号流程图。如果不在每次迭代后增加如果不在每次迭代后增加1/2，可以最后的输出序列中每个元素除以，可以最后的输出序

23、列中每个元素除以N。第51页，共59页，编辑于2022年，星期一二、利用二、利用FFT的程序求的程序求IFFT的方法的方法vIFFT与FFT的信号流图还是存在区别，不能用FFT程序实现IFFT算法。输入序列变输出序列，输入序列变输出序列，WN的不同，输出序列的每个元素除以的不同，输出序列的每个元素除以N，是，是X(k)倒序重排，倒序重排，x(n)自然顺序排列。自然顺序排列。第52页，共59页，编辑于2022年，星期一X(k)的共轭作为输入，结果取共轭，再除以的共轭作为输入，结果取共轭，再除以N就得到了就得到了x(n)。第53页，共59页，编辑于2022年，星期一第七节第七节 实序列的实序列的F

24、FT高效算法高效算法v当输入序列为实数数据时，进一步可以提高当输入序列为实数数据时，进一步可以提高FFTFFT运算运算效率效率v同时计算两组实序列的同时计算两组实序列的DFTDFT（两组同长序列构成新的序列）由于由于x(n)和和y(n)为为实序列，有实序列，有第54页，共59页，编辑于2022年，星期一v用用N N点序列的点序列的DFTDFT结果获得结果获得2N2N点长实序列的点长实序列的DFTDFT结果结果 求出求出z(n)对应的对应的Z(K)，可以得到，可以得到x(n)和和y(n)对应的对应的X(K)和和Y(K).x1(n)和和x2(n）组成一个复序列，利用上面的结果求出）组成一个复序列，

25、利用上面的结果求出X1(K)和和X2(K)第55页，共59页，编辑于2022年，星期一第八节第八节 MATLAB中用于中用于FFT计算的函数计算的函数v一 函数 fftv二 函数ifft 一维快速傅立叶正逆变换v三 应用实例vt=0:0.001:0.6;vx=sin(2*pi*50*t)+sin(2*pi*120*t);vy=x+1.5*randn(1,length(t);正弦信号与随机噪声叠加vY=fft(y,512);求含噪声信号的离散傅立叶变换（数字谱）vP=Y.*conj(Y)/512;计算功率谱vf=1000*(0:255)/512;vplot(f,P(1:256);功率谱中在频率5

26、0HZ，120HZ处存在该频率的成分第56页，共59页，编辑于2022年，星期一第九节第九节 频率域采样理论频率域采样理论v时域采样定理：在一定条件下可以由时域离散采样信号恢复原来的连续信号，其中内插函数是取样函数。vX(K)是怎么样得到的？v序列傅立叶变换的采样值得到，能否由X(K)恢复原来的时域信号或者原来的频谱函数呢？第57页，共59页，编辑于2022年，星期一推导过程见书本，结论是：任意序列推导过程见书本，结论是：任意序列x(n)，对应的，对应的Z变换为变换为X(z)，X(z)在单位圆上的在单位圆上的z变换就是序列的傅立叶变换，具有连续的频谱，变换就是序列的傅立叶变换，具有连续的频谱，将其作将其作N点等间隔采样，得到点等间隔采样，得到X(k),再作再作IDFT，得到的不一定是，得到的不一定是x(n)本身，而是本身，而是x(n)以以N为周期的周期延拓序列的主值序列。为周期的周期延拓序列的主值序列。第58页，共59页，编辑于2022年，星期一第九节第九节 频率域采样理论频率域采样理论v频域采样定理 如果序列x(n)的长度为M,则只有当频域采样点数 时，才有即可由频域采样 X(k)恢复原序列x(n)，否则产生时域混叠现象。上式称为频域采样定理。由X(k)恢复X(z)的内插公式和内插函数分别为书本公式4-38和4-39。作业1，9，10第59页，共59页，编辑于2022年，星期一