第3章 离散傅里叶变换(DFT).ppt

引言3.1离散傅里叶变换(DFT)的定义3.2离散傅里叶变换的基本性质3.3频域采样3.4DFT快速算法FFT3.5DFT的应用举例,第3章离散傅里叶变换(DFT)及其快速算法（FFT）,引言,DFT与FT区别FT:序列的付里叶变换,时频对应关系DFT:序列的FT的有限点采样.也可以直接定义即DFT是FT的N点等间隔采样-频域采样定理频域采样时域周期重复-N越大,DFT包络线越逼近FTDFT变换的意义:FT是连续谱,采样离散化后便于计算机处理DFT的定义、性质及频域采样定理、FFT及其应用,3.1离散傅里叶变换的定义,DFT定义DFT与Z变换及FT的关系:DFT的物理意义DFT的周期性:-DFT与DFS的关系DFT是DFS的主值区间DFT的矩阵表示,3.1离散傅里叶变换的定义,3.1.1DFT的定义设x(n)是一个长度为M的有限长序列，则定义x(n)的N点离散傅里叶正变换为,离散傅里叶逆变换为,离散傅里叶变换对,式中，N称为DFT变换区间长度NM，可见：DFT使有限长时域离散序列与有限长频域离散序列建立起对应关系,例1,已知，分别求和时的。,解：,由该例可知：频率采样点数不同，DFT的长度不同，DFT的结果也不同。,图3.1.1X(k)与X(ej)的关系,例2：，分别计算x(n)的8点、16点DFT。解:x(n)的8点DFT为x(n)的16点DFT为,返回,是在频率区间上的等间隔采样,返回,可见:对于同一序列x(n)DFT变换区间长度N不同,DFT变换结果X(k)不同,当N确定后,X(k)与x(n)一一对应的.N越大,DFT的包络线越接近FT,当N足够大,可用DFT进行谱分析,DFT的物理意义:DFT与FT的关系:X(k)是x(n)的频谱X(ej)在0,2上的N点等间隔采样,采样间隔2/N.即对序列频谱的离散化.DFT与ZT的关系:X(k)是x(n)的Z变换X(Z)在单位圆上N点等间隔采样.对序列的傅里叶变换进行频域抽样时,自然可以看作是对单位圆上的Z变换进行抽样.表达式如下,设序列x(n)的长度为N，其Z变换和DFT分别为：,比较上面二式可得关系式,离散频率、数字频率和模拟频率间的关系,模拟频率,离散频率,或，分别表示模拟频率与模拟角频率。单位分别为赫兹（Hz）和弧度/秒（rad/s）。两者关系为：,离散频率、数字频率和模拟频率间的关系,数字频率,它是将离散（信号数字）频率离散化后的结果，用表示。，因此可得出离散频率、数字频率和模拟频率之间的对应关系为：,以上所讨论的三种频率变量之间的关系，在对模拟信号进行数字处理以及利用模拟滤波器设计数字滤波器乃至整个数字信号处理中十分重要，望同学们高度重视。,3.1.2DFT的隐含周期性-DFT与DFS的关系DFT变换对中，x(n)与X(k)均为有限长序列,但由于WknN的周期性，都隐含周期性，且周期均为N。有限长序列是取周期序列的一个周期来表示.周期序列与有限长序列x(n)的转化:x(n),周期延拓,为了以后叙述方便，将(3.1.5)式用如下形式表示：,N(n)=x(n)N，,N(k)=X(k)N，,文字说明,图3.1.2有限长序列及其周期延拓,对任意整数m，总有均为整数因此:X(k)x(n)隐含周期性X(k)满足同理可证明x(n+mN)=x(n)DFT是DFS的主值区间,x(n),X(k),DFS,DFT,公式说明,如果x(n)的长度为N，且(n)=x(n)N，则可写出(n)的离散傅里叶级数表示为,取主值区间,DFS对,DFT对,公式说明,式(3.1.5)(3.1.8)说明了DFT和DFS之间的关系。这些关系式成立的条件是NM，即DFT的变换区间N不能小于x(n)的长度M。如果该条件不满足，按照式(3.1.5)将x(n)进行延拓时，中将发生时域混叠，由式(3.1.8)得到的X(k)不再是x(n)的DFT，这时以上讲的DFS和DFT之间的关系不再成立,M为整数,M为整数,重要公式,(n)=x(n)N，,式中x(n)N表示x(n)以N为周期的周期延拓序列，(n)N表示n对N求余，即如果n=MN+n1，0n1N-1，M为整数，则(n)N=n1例如,则有,3.1.3DFT的矩阵表示,周期序列的DFS以及有限长序列x(n)的DFT如下可以发现它们右边的函数形式一样，当然k的定义域不同，X(k)只是的主值区序列，或者说X(k)以N为周期进行周期延拓即是,返回,也可以表示成矩阵形式式中，X是N点DFT频域序列向量:x是时域序列向量:DN称为N点DFT矩阵，定义为,(3.1.12),返回,回到本节,也可以表示为矩阵形式:称为N点IDFT矩阵，定义为从式(3.1.12)和式(3.1.14)，我们可以发现,(3.1.14),返回,回到本节,3.2离散傅里叶变换的基本性质,1线性性质如果x1(n)和x2(n)是两个有限长序列，长度分别为N1和N2。y(n)=ax1(n)+bx2(n)式中a、b为常数，即N=maxN1,N2，则y(n)的N点DFT为Y(k)=DFTy(n)=aX1(k)+bX2k,0kN-1(3.2.1)其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。若N1频域相乘频域卷积-时域相乘(自已证),(2)循环卷积定理,时域卷积-频域相乘证明：直接对上式两边进行DFT,令n-m=n，则有,因为上式中x2(n)NWknN，以N为周期，所以对其在任一个周期上求和的结果不变。因此,用时域循环卷积定理计算两个序列循环卷积运算的方框图如下图所示,图3.2.3用DFT计算两个有限长序列L点循环卷积运算的方框图,5离散巴塞伐尔定理,设长度为N的序列x(n)的N点DFT为X(k)，则,6复共轭序列的DFT设x*(n)是x(n)的复共轭序列，长度为N且X(k)=DFTx(n)则DFTx*(n)=X*(N-k),0mN-1(3.2.6)且X(N)=X(0)类似的(3.2.7),证明：根据DFT的唯一性，只要证明(3.2.6)式右边等于左边即可，将DFT定义式中的K用N-K代替，并取共轭,又由X(K)的隐含周期性有X(N)=X(0)用同样的方法可以证明,7DFT的共轭对称性,回顾:(1)序列的对称性a.奇对称(序列)和偶对称(序列)xe(n)=xe(-n)x0(n)=-x0(-n)b.(DFT有限长)圆周奇对称(序列)和圆周偶对称(序列)xep(n)=xep(N-n)xop(n)=-xop(N-n)c.共轭对称(序列)和共轭反对称(序列)xe(n)=x*e(-n)xo(n)=-x*o(-n)d.(DFT有限长)圆周共轭对称(序列)和圆周共轭反对称(序列)xep(n)=xep*(N-n)xop(n)=-xop*(N-n),复,可见：a,c一般序列的对称指对坐标原点的对称，而b,d圆周或DFT变换对有限长序列的对称是对变称区间的中心的对称,(2)序列的对称分量x(n)=xo(n)+xe(n).a.奇对称分量和偶对称分量b.(DFT有限长)圆周奇对称分量和圆周偶对称分量c.共轭对称分量和共轭反对称分量d.(DFT有限长)圆周共轭对称分量和圆周共轭反对称分量,（1）.有限长共轭对称序列和共轭反对称序列分别满足下式的称为有限长共轭对称序列和共轭反对称序列xep(n)=x*ep(N-n),0nN-1(3.2.9)xop(n)=-x*op(N-n),0nN-1(3.2.10),当N为偶数时，将上式中的n换成N/2-n可得到,图3.2.3共轭对称与共轭反对称序列示意图,图中*表示对应点为序列取共轭后的值。,任何有限长序列x(n)都可以表示成其共轭对称分量和共轭反对称分量之和，即x(n)=xep(n)+xop(n),0nN-1将上式中的n换成N-n，并取复共轭，得到x*(N-n)=x*ep(N-n)+x*op(N-n)=xep(n)-xop(n)xep(n)=1/2x(n)+x*(N-n)(3.2.13)xop(n)=1/2x(n)-x*(N-n)(3.2.14),(2)DFT的共轭对称性(奇偶虚实),(a),(b),复,(c)实信号的DFT共轭对称性,证明,证明,说明,设x(n)=xr(n)+jxi(n)其中xr=Rex(n)=1/2x(n)+x*(n)jxi(n)=jImx(n)=1/2x(n)-x*(n)可得DFTxr(n)=1/2DFTx(n)+x*(n)=1/2X(k)+X*(N-k)=Xep(k)DFTjxi(n)=1/2DFTx(n)-x*(n)=1/2X(k)-X*(N-k)=Xop(k),由DFT的线性性质即可得X(k)=DFTx(n)=Xep(k)+Xop(k)其中Xep(k)=DFTxr(n),X(k)的共轭对称分量Xop(k)=DFTjxi(n),X(k)的共轭反对称分量,设x(n)=xep(n)+xop(n)，0nN-1其中xep(n)=1/2x(n)+x*(N-n),x(n)的共轭对称分量xop(n)=1/2x(n)-x*(N-n),x(n)的共轭反对称分量可得DFTxep(n)=1/2DFTx(n)+x*(N-n)=1/2X(k)+X*(k)=ReX(k)DFTxop(n)=1/2DFTx(n)-x*(N-n)=1/2X(k)-X*(k)=jImX(k)因此X(k)=DFTx(n)=XR(k)+jXI(k)其中XR(k)=ReX(k)=DFTxep(n)jXI(k)=jImX(k)=DFTxop(n),设x(n)是长度为N的实序列，且X(k)=DFTx(n)，则(a)X(k)=X*(N-k),0kN-1(3.2.19)(b)如果x(n)实偶对称,即x(n)=x(N-n)则X(k)实偶对称,即X(k)=X(N-k)(3.2.20)(c)如果x(n)实奇对称,即x(n)=-x(N-n)，则X(k)纯虚奇对称，即X(k)=-X(N-k)(3.2.21),利用DFT的共轭对称性，通过计算一个N点DFT，可以得到两个不同实序列的N点DFT，设x1(n)和x2(n)为两个实序列，构成新序列x(n)如下：x(n)=x1(n)+jx2(n)对x(n)进行DFT，得到X(k)=DFTx(n)=Xep(k)+Xop(k)Xep(k)=DFTx1(n)=1/2X(k)+X*(N-k)Xop(k)=DFTjx2(n)=1/2X(k)-X*(N-k)所以X1(k)=DFTx1(n)=1/2X(k)+X*(N-k)X2(k)=DFTx2(n)=-j1/2X(k)-X*(N-k),应用:,例：已知实序列x(n),y(n)的DFT分别为X(k),Y(k),试给出一种计算IDFT就可得到x(n),y(n)的计算方法。,解：令w(n)=x(n)+jy(n),W(k)=DFT(w(n)w(n)=IDFT(W(k)所以，分别取Re(w(n),Im(w(n),3.3频域采样定理,将阐明：（1）FT变换、z变换与DFT的关系，在此基础上引出频域采样的概念，（2）频域采样理论（频域采样不失真条件）（3)频域内插公式,X(z)X(ejw),x(n),X(k),xN(n),采样,?,IDFT,分析频域采样,时域如何变换,(n),关系如下:,?,在单位圆上对X(z)等间隔采样N点得到,设任意序列x(n),在区间0,2对X(ejw)等间隔N点采样或,xN(n)=IDFTX(k)，0nN-1,实质上，是对x(n)的频谱函数的等间隔采样。因为以2为周期，所以是以N为周期的频域序列,即,推导,由DFT与DFS的关系可知，X(k)是xN(n)以N为周期的周期延拓序列(n)的离散傅里叶级数系数的主值序列，即,而,代入上3.3.1式得,式中,为整数,其它k,所以,结论:将x(n)的频域函数X(ejw)，按每周期N点抽样，得到一周期序列,而时域,得到变换结果,是原序列x(n)周期延拓的序列.如下关系即频域按每周期N点抽样,时域便按N点周期延拓.,由该式可知：是原序列的周期延拓，周期为N，然后取主值。,频域抽样不失真条件结论：如果序列x(n)的长度为L，则只有当频域采样点数NL时，才有xN(n)=IDFTX(k)=x(n)可由频域采样X(k)恢复原序列，否则产生时域混叠现象。这就是所谓的频域采样+定理。,返回,用频域采样X(k)表示X(z)的内插公式和内插函数,频域内插公式,（1）内插公式,（2）内插函数,所谓频域内插公式，就是用频域采样表示X(z)和。频域内插公式是FIR数字滤波器的频率采样结构和频率采样设计法的理论依据。,推导,恢复原序列:时域上恢复x(n),频域上恢复X(z)X(ejw)从频域抽样不失真条件可以知道：N个频域抽样X(k)能不失真的还原出长度为N的有限长序列x(n)。那么用N个X(k)也一定能完整地表示出X(z)以及频率响应即单位圆上的X(z).其过程:先由N个X(k)作IDFT得到x(n),再把x(n)作Z变换便得到X(z).,设序列x(n)长度为M，在频域02之间等间隔采样N点，NM，则有,序列,，所以,的z变换为,由于,将上式代入X(z)的表示式中得,上式中W-kNN=1，因此,内插函数,用X(k)表示X(z)的内插公式,当z=ej时，就成为x(n)的傅里叶变换X(ej)的内插函数和内插公式，即,进一步化简可得,(3.3.7),(3.3.8),内插函数零极点与（）的幅频特性示意图,内插公式,内插函数零极点与（）的幅频特性示意图,解：,例：已知序列x(n)=-1,-1,4,3,n=0,1,2,3,对其频谱采样，采样频率点的取样值为X（k），求IDFT(X(k),解：x(n)=,-1,4,2，-1,4,2,-1,-1,4,3,-1,-1,4,3,-1,-1,4,3,2,-1,4,2，-1,4,2,3.5DFT的应用举例,DFT的快速算法FFT的出现，使DFT在数字通信、语言信号处理、图像处理、功率谱估计、仿真、系统分析、雷达理论、光学、医学、地震以及数值分析等各个领域都得到广泛应用。以下面两点为基础卷积和相关系数运算作连续傅里叶变换的近似,仅介绍DFT在线性卷积和频谱分析两方面的应用。本节主要论述：,3.5.1用DFT（FFT）计算两个有限长序列的线性卷积,3.5.2用DFT计算有限长序列与无限长序列的线性卷积,3.5.3用DFT对序列进行谱分析,3.5.1用DFT计算两个有限长序列线性卷积,时域循环卷积,频域是两序列的DFT相乘.时频两域的转换(即DFT及IDFT)有快速傅里叶变换(FFT)算法.所以利用循环卷积定理计算循环卷积比计算卷积的计算速度快得多.实际问题中:即信号通过线性时不变系统h(n)后的响应y(n)是线性卷积运算.思考：若做卷积的两序列都是有限长序列,能否用它们的圆周卷积结果代替它们的线性卷积结果呢?即圆周卷积与线性卷积的关系是什么?,圆周卷积,循环卷积定理:Y(k)=DFTy(n)=X1(k)X2(k),0kL-1,0kL-1,用DFT计算循环卷积框图,圆周卷积与线性卷积相同的条件:LN+M-1,:假设h(n)和x(n)都是有很长序列，长度分别是N和M。其线性卷积和循环卷积分别表示如下：,推导,圆周卷积与线性卷积的关系:,其中，LmaxN,M,对照线性卷积式可以看出，上式中,(3.4.3),周期延拓,线性卷积,x1(n)与x2(n)的L点圆周卷积结果是其线性卷积结果yL(n)以L点周期延拓后再取主值序列.如L取适当值LN+M-1,则线性卷积结果yL(n)被L点周期延拓后无混叠。即其主值序列=线性卷积结果,从而实现圆周卷积代替线性卷积.即当LN1+N2-1时，圆周卷积可以代替线性卷积即：,从,看出,图3.4.2线性卷积与循环卷积,图3.4.3用DFT计算线性卷积框图,线性卷积,3.5.2用DFT计算有限长序列与无限长序列的线性卷积,用FFT计算有限长序列与无限长序列的线性卷积问题：h(n)为某滤波器的单位脉冲响应,长度有限输入信号x(n)很长，h(n)要补许多零再进行计算,计算量有很大的浪费解决方法：重叠相加法重叠保留法重叠相加法：将x(n)分段，每段长度为M，然后依次计算各段与h(n)的卷积，再由各段的卷积结果得到y(n)。,返回,回到本节,设序列h(n)长度为N，x(n)为无限长序列。将x(n)均匀分段，每段长度取M，则,于是，h(n)与x(n)的线性卷积可表示为,(3.4.4),图3.4.4重叠相加法卷积示