(精品)第4章 离散傅里叶变换1.ppt
测试信号分析与处理测试信号分析与处理课程课程 第四章第四章 离散傅里叶变换及其离散傅里叶变换及其快速算法快速算法 数字谱分析是数字信号处理的基本内容，通过对信号的频谱数字谱分析是数字信号处理的基本内容，通过对信号的频谱分析，掌握信号特征，以便对信号作进一步处理，达到提分析，掌握信号特征，以便对信号作进一步处理，达到提取有用信息的目的。包括序列的傅立叶变换、离散傅立叶取有用信息的目的。包括序列的傅立叶变换、离散傅立叶级数、离散傅立叶变换和快速傅立叶变换级数、离散傅立叶变换和快速傅立叶变换第一节第一节 序列的傅里叶变换序列的傅里叶变换 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFSDFS）第三节第三节 离散傅里叶变换（离散傅里叶变换（DFTDFT）第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质 测试信号分析与处理测试信号分析与处理课程课程第五节第五节 快速傅里叶变换快速傅里叶变换第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）第七节第七节 实序列的实序列的FFTFFT高效算法高效算法第八节第八节 频率域采样理论频率域采样理论第一节第一节 序列的傅里叶变换序列的傅里叶变换 v已知序列x(n)的Z变换为：v如X(Z)在单位圆上是收敛的，则将在单位圆上的Z变换定义为序列的傅里叶变换，即 v序列的傅立叶变换定义为单位圆上的Z变换，因此其同Z变换具有相同的性质一、定义一、定义v二、物理意义与存在条件 x(t)x(n)正变换 反变换 分析 综合连续非周期连续周期序列傅立叶变换存序列傅立叶变换存在条件在条件序列必须绝对可和序列必须绝对可和比较这两个反变换比较这两个反变换三、特点与应用三、特点与应用v非周期序列的傅里叶变换（频谱）的特点在于它是 周期为 的连续周期函数，其周期为 。是连续周期函数，因此也可以进行傅立叶级数展开是连续周期函数，因此也可以进行傅立叶级数展开v序列可以表示为复指数序列分量的叠加，而对复指数序列的响应完全由系统的频率响应 确定，既可以推出输出的傅立叶变换为：三、特点与应用三、特点与应用第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）一、傅里叶变换在时域和频域中的对称规律一、傅里叶变换在时域和频域中的对称规律v 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v一个域中（时域或频域）是连续的，对应另一个域中（频域或时域）是非周期的。v一个域中（时域或频域）是离散的，对应另一个域中（频域或时域）是周期的。第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）二、离散傅里叶级数（二、离散傅里叶级数（定量表达周期序列的傅立叶级数展开式定量表达周期序列的傅立叶级数展开式）v离散周期信号的频谱，即离散傅里叶级数(DFS)。v非周期序列的频谱v一个非周期序列x(n)可以分解为一系列连续的不同频率的复指数序列 的叠加积分，其频谱 表示了这些不同频率分量的复幅度，频率是周期性的，独立分量在 到 之间。v周期序列的频谱是非周期序列频谱的离散化，根据频谱的含义，意味着一个周期序列可以分解成一系列 为离散（）的指数序列分量 的叠加，其频率间隔：v设任意k次频率的复指数序列分量 的复幅度用 表示，则可以推出周期序列的傅立叶级数变换对。v离散傅里叶级数的变换对表达式 v离散傅立叶级数的正反变换，为数字信号分析和处理做好了理论准备，因为时域和频域都是离散化；v但是他们都是周期序列，需要在理论上对序列的有限化进一步研究，以解决离散信号分析处理或系统设计以及实现等实用化方面的问题。第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）一、离散傅里叶变换一、离散傅里叶变换DFT定义式定义式v离散傅里叶变换就是对有限长序列进行傅里叶变换的表示式。定义一个周期序列在第一个周期内的有限长序列值为此周期序列的主值区间，表示为：正变换反变换 第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）v矩阵形式或 第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）二、二、DFT的物理意义的物理意义 1 非周期序列的频谱，即它的傅立叶变换，是一个连续的周期性频谱；2 有限长序列的DFT却是离散的序列，两者虽然不同，但存在着重要的联系。可以证明：有限长序列的傅立叶变换DFT是该序列频谱的抽样值。v有限长序列的DFT就是序列在单位圆上的Z变换（即有限长序列的傅里叶变换或频谱）以 为间隔的抽样值 第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v线性特性线性特性 v时移特性时移特性 1）圆周移位序列2）时移定理v频移特性频移特性 过程、圆移位过程、圆移位序列在时域中圆周移位，频域上将产生附加相移序列在时域中圆周移位，频域上将产生附加相移序列在时域上乘于复指数序列，则在频域上将发生圆周移位序列在时域上乘于复指数序列，则在频域上将发生圆周移位第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v圆周卷积特性 1）时域圆周卷积 2）频域圆卷积 若v实数序列奇偶性（对称性）v 帕斯瓦尔定理：变换过程中能量是守恒的。顺时针顺时针,左移左移,逆时针转动逆时针转动,再顺时针读数再顺时针读数.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直接运算的工作量直接运算的工作量计算机运算时（编程实现）：计算机运算时（编程实现）：N N次复乘，次复乘，次复乘，次复乘，N-1N-1次复加次复加次复加次复加 N N个点个点个点个点 复数乘法复数乘法复数加法复数加法一个一个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)第五节第五节 快速傅里叶变换快速傅里叶变换按定义计算，需要按定义计算，需要 次复数乘和次复数乘和(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.1.算法原理算法原理 对长度为对长度为 （L L为正整数，若原序列的长度不为正整数，若原序列的长度不满足此条件，则可用零补足）的序列满足此条件，则可用零补足）的序列x(nx(n),),按序列各项按序列各项序号的奇偶将序列分成两个子序列（大点数化为小点数）序号的奇偶将序列分成两个子序列（大点数化为小点数），有，有偶序号序列偶序号序列 奇序号序列奇序号序列上式中上式中 分别为分别为 的的N/2N/2点点DFTDFT，即：，即：这是这是 前前前前N/2N/2点点点点DFTDFT对于对于 后后后后N/2N/2点点点点的的DFTDFT显然，可采用显然，可采用蝶式运算图蝶式运算图蝶式运算图蝶式运算图来表示上述前来表示上述前N/2N/2和后和后N/2N/2两式两式 ，如下图所示：如下图所示：vX(nX(n)的的DFTDFT最后结果最后结果根据奇偶对分，最后一定能得到根据奇偶对分，最后一定能得到N个单项序列（序列长度为个单项序列（序列长度为1），），而单项序列的而单项序列的DFT就是其本身。计算就是其本身。计算N项序列的项序列的DFT，只需要，只需要按照碟形算法逐次合成，由按照碟形算法逐次合成，由N个个1点长序列的点长序列的DFT合成合成N/2个个2点点长序列的长序列的DFT，再由，再由N/2个个2点长序列的点长序列的DFT合成合成N/4个个4点长序点长序列的列的DFT，依次进行，最后得到，依次进行，最后得到N点长序列的点长序列的DFT。第五节第五节 快速傅里叶变换快速傅里叶变换2.2.算法的具体实现算法的具体实现 第五节第五节 快速傅里叶变换快速傅里叶变换3.3.流程图规律流程图规律1)1)蝶群序号蝶群序号蝶距（序号蝶距（序号差）差）蝶群宽（点蝶群宽（点数）数）蝶群数蝶群数第一级（第一级（2点点DFT）第第i级（级（点点DFT)2点组成一个基本的运算单元，称为蝶形单元，相互交叠点组成一个基本的运算单元，称为蝶形单元，相互交叠的蝶形单元构成一个蝶群，每级由一系列的蝶群组成。蝶的蝶形单元构成一个蝶群，每级由一系列的蝶群组成。蝶形单元的宽度为蝶距，蝶群的宽度为蝶群宽。形单元的宽度为蝶距，蝶群的宽度为蝶群宽。第五节第五节 快速傅里叶变换快速傅里叶变换2 2）L L级蝶形运算，每一级都是级蝶形运算，每一级都是“同址运算同址运算”，就，就是每级计算结果都占用同一地址单元，无需要是每级计算结果都占用同一地址单元，无需要另开存储空间。另开存储空间。3 3）每个蝶形单元的运算，都包括乘）每个蝶形单元的运算，都包括乘 ，并，并与相应的与相应的DFTDFT结果加减各一次结果加减各一次 4 4）同一级中，）同一级中，的分布规律相同的分布规律相同第第i i级级(点点DFT):;.;DFT):;.;v5）时间序列是按时间先后顺序排列的，称为自然顺序，但FFT计算时，需要符合快速算法的要求，需要一种乱序输入，才能获得X(K)按自然顺序的输出，也就是需要对输入进行相应处理，即所谓的码位倒置或输入重排。第五节第五节 快速傅里叶变换快速傅里叶变换序列输入的自然顺序十进制二进制码码位倒置结果（二进制码）乱序十进制序列乱序的输入顺序4 输入重排（输入重排（输入序列不再为原序列的自然顺序，需要重排）输入序列不再为原序列的自然顺序，需要重排）第五节第五节 快速傅里叶变换快速傅里叶变换5.5.运算量比较运算量比较N N（）点的）点的FFTFFT总运算量为总运算量为复数乘复数乘复数加复数加 利用基利用基2 2时析型时析型FFTFFT求序列的求序列的DFTDFT同直接计算同直接计算序列的序列的DFTDFT的复数乘运算次数之比为的复数乘运算次数之比为DFT有快速算法有快速算法FFT，IDFT是否有快速算法呢？是否有快速算法呢？IFFT是是IDFT的快速算法。的快速算法。第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）一、一、IFFTIFFT算法算法在在FFTFFT的时间抽取算法中，第一次分解的结果是的时间抽取算法中，第一次分解的结果是 第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）依次类推，可以求出依次类推，可以求出x(n)的各点，下面是整个的各点，下面是整个8点点IFFT的信号流的信号流程图。程图。如果不在每次迭代后增加如果不在每次迭代后增加1/2，可以最后的输出序列中每个元素除，可以最后的输出序列中每个元素除以以N。二、利用二、利用FFT的程序求的程序求IFFT的方法的方法vIFFT与FFT的信号流图还是存在区别，不能用FFT程序实现IFFT算法。输入序列变输出序列，输入序列变输出序列，WN的不同，输出序列的每个元素除以的不同，输出序列的每个元素除以N，是，是X(k)倒序重排，倒序重排，x(n)自然顺序排列。自然顺序排列。X(k)的共轭作为输入，结果取共轭，再除以的共轭作为输入，结果取共轭，再除以N就得到了就得到了x(n)。第七节第七节 实序列的实序列的FFT高效算法高效算法v当输入序列为实数数据时，进一步可以提高当输入序列为实数数据时，进一步可以提高FFTFFT运算运算效率效率v同时计算两组实序列的同时计算两组实序列的DFTDFT（两组同长序列构成新的序列）由于由于x(n)和和y(n)为为实序列，有实序列，有v用用N N点序列的点序列的DFTDFT结果获得结果获得2N2N点长实序列的点长实序列的DFTDFT结果结果 求出求出z(n)对应的对应的Z(K)，可以得到，可以得到x(n)和和y(n)对应的对应的X(K)和和Y(K).x1(n)和和x2(n）组成一个复序列，利用上面的结果求出）组成一个复序列，利用上面的结果求出X1(K)和和X2(K)第八节第八节 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);功率谱中在频率50HZ，120HZ处存在该频率的成分第九节第九节 频率域采样理论频率域采样理论v时域采样定理：在一定条件下可以由时域离散采样信号恢复原来的连续信号，其中内插函数是取样函数。vX(K)是怎么样得到的？v序列傅立叶变换的采样值得到，能否由X(K)恢复原来的时域信号或者原来的频谱函数呢？推导过程见书本，结论是：任意序列推导过程见书本，结论是：任意序列x(n)，对应的，对应的Z变换为变换为X(z)，X(z)在单位圆上的在单位圆上的z变换就是序列的傅立叶变换，具变换就是序列的傅立叶变换，具有连续的频谱，将其作有连续的频谱，将其作N点等间隔采样，得到点等间隔采样，得到X(k),再作再作IDFT，得到的不一定是，得到的不一定是x(n)本身，而是本身，而是x(n)以以N为周期的为周期的周期延拓序列的主值序列。周期延拓序列的主值序列。第九节第九节 频率域采样理论频率域采样理论v频域采样定理 如果序列x(n)的长度为M,则只有当频域采样点数 时，才有即可由频域采样 X(k)恢复原序列x(n)，否则产生时域混叠现象。上式称为频域采样定理。由X(k)恢复X(z)的内插公式和内插函数分别为书本公式4-38和4-39。作业1，9，10
