离散傅里叶变换的定义

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Shanghai Jiao Tong University,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,Shanghai Jiao Tong University,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Shanghai Jiao Tong University,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,3.1,离散傅里叶变换的定义,3.2,离散傅里叶变换的基本性质,（重点）,3.3,频率域采样,（重点）,3.4 DFT,的应用举例,第,3,章 离散傅里叶变换,(DFT),3.1 离散傅里叶变换的定义,3.1.1 DFT,的定义,设,x,(,n,),是一个长度为,M,的有限长序列， 则定义,x,(,n,),的,N,点,离散傅里叶变换,为,X,(,k,),的,离散傅里叶逆变换,为,式中， ，,N,称为,DFT,变换区间长度，,N,M,， 通常称,(3.1.1),式和,(3.1.2),式为离散傅里叶变换对。 下面证明,IDFT,X,(,k,),的唯一性。,把,(3.1.1),式代入,(3.1.2),式有,为整数,为整数,例,3.1.1,x,(,n,)=,R,4,(,n,),，求,x,(,n,),的,8,点和,16,点,DFT,解,设变换区间,N,=8,， 则,所以， 在变换区间上满足下式：,IDFT,X,(,k,),=,x,(,n,), 0,n,N,-1,由此可见，,(3.1.2),式定义的离散傅里叶变换是唯一的。,设变换区间,N,=16,， 则,3.1.2 DFT,和,Z,变换的关系,设序列,x,(,n,),的长度为,N,，其,Z,变换和,DFT,分别为：,比较上面二式可得关系式,图,3.1.1,X,(,k,),与,X,(,e,j,),的关系,3.1.3 DFT,的隐含周期性,前面定义的,DFT,变换对中，,x,(,n,),与,X,(,k,),均为有限长序列，但由于的周期性，使,(3.1.1),式和,(3.1.2),式中的,X,(,k,),隐含周期性，且周期均为,N,。对任意整数,m,，总有,均为整数,所以,(3.1.1),式中，,X,(,k,),满足,同理可证明,(3.1.2),式中,x,(,n,+,mN,)=,x,(,n,),实际上，任何周期为,N,的周期序列都可以看作长度为,N,的有限长序列,x,(,n,),的周期延拓序列，而,x,(,n,),则是的一个周期， 即,为了以后叙述方便， 将,(3.1.5),式用如下形式表示：,图,3.1.2,有限长序列及其周期延拓,式中,x,(,n,),N,表示,x,(,n,),以,N,为周期的周期延拓序列，,(,n,),N,表示,n,对,N,求余， 即如果,n,=,MN,+,n,1,，,0,n,1,N,-1,，,M,为整数，,则,(,n,),N,=,n,1,例如，,则有,所得结果附合图,3.1.2,所示的周期延拓规律。,如果,x,(,n,),的长度为,N,，且,=,x,(,n,),N,，则可写出的离散傅里叶级数表示为,(3.1.8),(3.1.9),式中,(3.1.10),3.2 离散傅里叶变换的基本性质,3.2.1,线性性质,如果,x,1,(,n,),和,x,2,(,n,),是两个有限长序列，长度分别为,N,1,和,N,2,。,y,(,n,)=,ax,1,(,n,)+,bx,2,(,n,),式中,a,、,b,为常数，即,N,=max,N,1,N,2,，则,y,(,n,),的,N,点,DFT,为,Y,(,k,)=DFT,y,(,n,),=,aX,1,(,k,)+,bX,2,(,k,), 0,k,N,-1 (3.2.1),其中,X,1,(,k,),和,X,2,(,k,),分别为,x,1,(,n,),和,x,2,(,n,),的,N,点,DFT,。,3.2.2,循环移位性质,1.,序列的循环移位,设,x,(,n,),为有限长序列，长度为,N,，则,x,(,n,),的循环移位定义为,y,(,n,)=,x,(,n,+,m,),N,R,N,(,N,) (3.2.2),图,3.2.1,循环移位过程示意图,2.,时域循环移位定理,设,x,(,n,),是长度为,N,的有限长序列，,y,(,n,),为,x,(,n,),的循环移位， 即,y,(,n,)=,x,(,n,+,m,),N,R,N,(,n,),则,Y,(,k,)=DFT,y,(n),=,X,(,k,) (3.2.3),其中,X,(,k,)=DFT,x,(,n,), 0,k,N,-1,。,证明：,令,n,+,m,=,n,， 则有,由于上式中求和项,x,(,n,),N,以,N,为周期， 所以对其在任一周期上的求和结果相同。 将上式的求和区间改在主值区则得,3.,频域循环移位定理,如果,X,(,k,)=DFT,x,(,n,), 0,k,N,-1,Y,(,k,)=,X,(,k,+,l,),N,R,N,(,k,),则,y,(,n,) = IDFT,Y,(,k,),=,x,(,n,) (3.2.4),3.2.3,循环卷积定理*,有限长序列,x,1,(,n,),和,x,2,(,n,),，长度分别为,N,1,和,N,2,，,N,=max,N,1,N,2,。,x,1,(,n,),和,x,2,(,n,),的,N,点,DFT,分别为：,X,1,(,k,)=DFT,x,1,(,n,),X,2,(,k,)=DFT,x,2,(,n,),如果,X,(,k,)=,X,1,(,k,),X,2,(,k,),则,(3.2.5),一般称,(3.2.5),式所表示的运算为,x,1,(,n,),与,x,2,(,n,),的循环卷积。下面先证明,(3.2.5),式， 再说明其计算方法。,证明： 直接对,(3.2.5),式两边进行,DFT,令,n,-,m,=,n,， 则有,因为上式中,x,2,(,n,),以,N,为周期，所以对其在任一个周期上求和的结果不变。 因此,循环卷积过程中，要求对,x,2,(,m,),循环反转，循环移位， 特别是两个,N,长的序理的循环卷积长度仍为,N,。,显然与一般的线性卷积不同，故称之为,循环卷积,， 记为,由于,所以,即,循环卷积亦满足交换律,。,图,3.2.2,循环卷积过程示意图,频域循环卷积定理,：,如果,x,(,n,)=,x,1,(,n,),x,2,(,n,),则,(3.2.6),X,1,(,k,)=DFT,x,1,(,n,),X,2,(,k,)=DFT,x,2,(,n,),0,k,N,-1,3.2.4,复共轭序列的,DFT,设,x,*(,n,),是,x,(,n,),的复共轭序列，长度为,N,X,(,k,)=DFT,x,(,n,),则,DFT,x,*,(,n,),=,X,*,(,N,-,k,), 0,k,N-1 (3.2.7),且,X,(,N,)=,X,(0),证明： 根据,DFT,的唯一性， 只要证明,(3.2.7),式右边等于左边即可。,又由,X,(,k,),的隐含周期性有,X,(,N,)=,X,(0),用同样的方法可以证明,DFT,x,*,(,N,-,n,),=,X,*,(,k,) (3.2.8),3.2.5 DFT,的共轭对称性*,1.,有限长共轭对称序列和共轭反对称序列,为了区别于傅里叶变换中所定义的共轭对称,(,或共轭反对称,),序列，下面用,x,ep,(,n,),和,x,op,(,n,),分别表示有限长共轭对称序列和共轭反对称序列，则二者满足如下定义式：,x,ep,(,n,)=,x,*,ep,(,N,-,n,), 0,n,N,-1 (3.2.9),x,op,(n)=-,x,*,op,(,N,-,n,), 0,n,N,-1 (3.2.10),当,N,为偶数时，将上式中的,n,换成,N,/2-,n,可得到,上式更清楚地说明了有限长序列共轭对称性的含义。如图,3.2.3,所示。图中*表示对应点为序列取共轭后的值。,图,3.2.3,共轭对称与共轭反对称序列示意图,如同任何实函数都可以分解成偶对称分量和奇对称分量一样， 任何有限长序列,x,(,n,),都可以表示成其共轭对称分量和共轭反对称分量之和， 即,x,(,n,)=,x,ep,(,n,)+,x,op,(,n,), 0,n,N,-1 (3.2.11),将上式中的,n,换成,N,-,n,，并取复共轭，再将,(3.2.9),式和,(3.2.10),式代入得到,x,*,(,N,-,n,)=,x,*,ep,(,N,-,n,)+,x,*,op,(,N,-,n,),=,x,ep,(,n,)-,x,op,(,n,) (3.2.12),x,ep,(,n,)=1/2,x,(,n,)+,x,*,(,N,-,n,),(3.2.13),x,op,(,n,)=1/2,x,(,n,)-,x,*,(,N,-,n,),(3.2.14),2. DFT,的共轭对称性,(1),如果,x,(,n,)=,x,r,(,n,)+,jx,i,(,n,),其中,x,r,(,n,)=Re,x,(,n,),=1/2,x,(,n,)+,x,*,(,n,),jx,i,(,n,)=,j,Im,x,(,n,),=1/2,x,(,n,)-,x,*,(,n,),由,(3.2.7),式和,(3.2.13),式可得,DFT,x,r,(,n,),=1/2DFT,x,(,n,)+,x,*,(,n,),=1/2,X,(,k,)+,X,*,(,N,-,k,),=,X,ep,(,k,),由,(3.2.7),式和,(3.2.14),式得,DFT,jx,i,(,n,),=1/2DFT,x,(,n,)-,x,*,(,n,),=1/2,X,(,k,)-,X,*,(,N,-,k,),=,X,op,(,k,),由,DFT,的线性性质即可得,X,(,k,)=DFT,x,(,n,),=,X,ep,(,k,)+,X,op,(,k,),(3.2.16),其中,X,ep,(,k,)=DFT,x,r,(,n,),X,(,k,),的共轭对称分量,X,op,(,k,)=DFT,jx,i,(,n,),X,(,k,),的共轭反对称分量,(2),如果,x,(,n,)=,x,ep,(,n,)+,x,op,(,n,),，,0nN-1 (3.2.17),其中,x,ep,(,n,)=1/2,x,(,n,)+,x,*,(,N,-,n,),x,(,n,),的共轭对称分量,x,op,(,n,)=1/2,x,(,n,)-,x,*,(,N,-,n,),x,(,n,),的共轭反对称分量,由,(3.2.8),式得,DFT,x,ep,(,n,),=1/2DFT,x,(,n,)+,x,*,(,N,-,n,),=1/2,X,(,k,)+,X,*,(,k,),=Re,X,(,k,),DFT,x,op,(,n,),=1/2DFT,x,(,n,)-,x,*,(,N,-,n,),=1/2,X,(,k,)-,X,*,(,k,),=,j,Im,X,(,k,),因此,X,(,k,)=DFT,x,(,n,),=,X,R,(,k,)+,jX,I,(,k,),(3.2.18),其中,X,R,(,k,)=Re,X,(,k,),=DFT,x,ep,(,n,),jX,I,(,k,)=jIm,X,(,k,),=DFT,x,op,(,n,),设,x,(,n,),是长度为,N,的实序列，且,X,(,k,)=DFT,x,(,n,),，则,(1),X,(,k,)=,X,*,(,N,-,k,),，,0,k,N,-1 (3.2.19),(2),如果,x,(,n,)=,x,(,N,-,n,),则,X,(,k,),实偶对称,， 即,X,(,k,)=,X,(,N,-,k,),(3.2.20),(3),如果,x,(,n,)=-,x,(,N,-,n,),，,则,X,(,k,),纯虚奇对称,， 即,X,(,k,)=-,X,(,N,-,k,),(3.2.21),利用,DFT,的共轭对称性，通过计算一个,N,点,DFT,， 可以得到两个不同实序列的,N,点,DFT,，设,x,1,(,n,),和,x,2,(,n,),为两个实序列，构成新序列,x,(,n,),如下 ：,x,(,n,)=,x,1,(,n,)+,jx,2,(,n,),对,x,(,n,),进行,DFT,， 得到,X,(,k,)=DFT,x,(,n,),=,X,ep,(,k,)+,X,op,(,k,),由,(3.2.16),式、,(3.2.13),式和,(3.2.14),式得到,X,ep,(,k,)=DFT,x,1,(,n,),=1/2,X,(,k,)+,X,*,(,N,-,k,),X,op,(,k,)=DFT,jx,2,(,n,),=1/2,X,(,k,)-,X,*,(,N,-,k,),所以,X,1,(,k,)=DFT,x,1,(,n,),=1/2,X,(,k,)+,X,*,(,N,-,k,),X,2,(,k,)=DFT,x,2,(,n,),=-,j,1/2,X,(,k,)-,X,*,(,N,-,k,),3.3 频率域采样*,设任意序列,x,(,n,),的,Z,变换为,且,X,(,z,),收敛域包含单位圆,(,即,x,(,n,),存在傅里叶变换,),。,在单位圆上对,X,(,z,),等间隔采样,N,点得到,x,N,(,n,)=IDFT,X,(,k,),，,0,n,N,-1,由,DFT,与,DFS,的关系可知，,X,(,k,),是,x,N,(,n,),以,N,为周期的周期延拓序列的离散傅里叶级数系数的主值序列， 即,将式,(3.3.1),代入上式得,式中,为整数,其它,m,如果序列,x,(,n,),的长度为,M,，则只有当频域采样点数,N,M,时，才有,x,N,(,n,)=IDFT,X,(,k,),=,x,(,n,),即可由频域采样,X,(,k,),恢复原序列,x,(,n,),， 否则产生时域混叠现象。 这就是所谓的,频域采样定理,。,(3.3.2),(3.3.3),下面推导,用频域采样,X,(,k,),表示,X,(,z,),的内插公式和内插函数,。 设序列,x,(,n,),长度为,M,， 在频域,02,之间等间隔采样,N,点，,N,M,， 则有,式中,将上式代入,X,(,z,),的表示式中得,上式中=1， 因此,(3.3.4),(3.3.5),(3.3.6),式,(3.3.6),称为用,X,(,k,),表示,X,(,z,),的,内插公式,，,k,(,z,),称为,内插函数,。,当,z,=,e,j,时，,(3.3.5),式和,(3.3.6),式就成为,x,(,n,),的傅里叶变换,X,(,e,j,),的内插函数和内插公式,， 即,进一步化简可得,(3.3.7),(3.3.8),3.4 DFT的应用举例,DFT,的快速算法,FFT,的出现，使,DFT,在数字通信、语音信号处理、图像处理、功率谱估计、仿真、系统分析、雷达理论、光学、医学、地震以及数值分析等各个领域都得到广泛应用。,3.4.1,用,DFT,计算线性卷积*,如果,0,k,L,-1,则由时域循环卷积定理有,Y,(,k,)=DFT,y,(,n,),=,X,1,(,k,),X,2,(,k,), 0,k,L,-1,由此可见，循环卷积既可在时域直接计算，也可以按照图,3.4.1,所示的计算框图，在频域计算。由于,DFT,有快速算法,FFT,，当,N,很大时，在频域计算的速度快得多，因而常用,DFT(FFT),计算循环卷积。,图,3.4.1,用,DFT,计算循环卷积,在实际应用中，为了分析时域离散线性非移变系统或者对序列进行滤波处理等，需要计算两个序列的线性卷积，与计算循环卷积一样，,为了提高运算速度， 也希望用,DFT(FFT),计算线性卷积,。而,DFT,只能直接用来计算循环卷积，为此导出线卷积和循环卷积之间的关系以及循环卷积与线性卷积相等的条件。,假设,h,(,n,),和,x,(,n,),都是有限长序列，长度分别是,N,和,M,。 它们的线性卷积和循环卷积分别表示如下：,(3.4.1),(3.4.2),其中， LmaxN, M，,对照式,(3.4.1),可以看出， 上式中,(3.4.3),式,3.4.3,说明，,y,(,n,),等于,y,l,(,n,),以,L,为周期的周期延拓序列的主值序列，即,LN+M-1,时，循环卷积等于线性卷积,。,图,3.4.2,线性卷积与循环卷积,图,3.4.3,用,DFT,计算线性卷积框图,3.4.2,用,DFT,对信号进行谱分析,所谓,信号的谱分析就是计算信号的傅里叶变换,。 连续信号与系统的傅里叶分析显然不便于直接用计算机进行计算，使其应用受到限制，而,DFT,是一种时域和频域均离散化的变换，适合数值运算，成为分析离散信号和系统的有力工具。,1.,用,DFT,对连续信号进行谱分析,工程实际中，经常遇到的连续信号,x,a,(,t,),，其频谱函数,X,a,(,j,),也是连续函数。,设连续信号,x,a,(,t,),持续时间为,T,p,， 最高频率为,f,c,， 如图,2.4.5,所示。,x,a,(,t,),的傅里叶变换为,对,x,a,(,t,),以采样间隔,T,1/2,f,c,(,即,f,s,=1/,T,2,f,c,),采样得,x,(,n,)=,X,a,(,nT,),。设共采样,N,点，并对,X,a,(,jf,),作零阶近似,(,t,=,nT,dt,=,T,),得,显然，,X,a,(,jf,),仍是,f,的连续周期函数，,x,(,n,),和,X,(,jf,),如图,3.4.5(,b,),所示。对,X,(,jf,),在区间,0,f,s,上等间隔采样,N,点，采样间隔为,F,，如图,3.4.5(,c,),所示。参数,f,s,、,T,p,、,N,和,F,满足如下关系式：,由于,NT,=,T,p,， 所以,(3.4.5),(3.4.6),将,f,=,kF,和式,(3.4.5),代入,X,(,jf,),中可得,X,a,(,jf,),的采样,0,k,N,-1,令,则,(3.4.8),理想低通滤波器的单位冲击响应,h,a,(,t,),及其频响函数,H,a,(,jf,),如图,3.4.6(,a,),、,(,b,),所示。,图中,图,3.4.6,用,DFT,计算理想低通滤波器频响曲线,现在用,DFT,来分析,h,a,(,t,),的频率响应特性。由于,h,a,(,t,),的持续时间为无穷长，所以要截取一段,T,p,，假设,T,p,=8s,， 采样间隔,T,=0.25s(,即采样速度,f,s,=4Hz),，采样点数,N,=,T,p,/,T,=32,。此时频域采样间隔,F,=1/,NT,=0.125Hz,，则,H(k)=T,DFT,h(n), 0k31,其中,h,(,n,)=,h,a,(,nT,),R,32,(,n,),在已知信号的最高频率,f,c,(,即谱分析范围时,),，为了避免在,DFT,运算中发生频率混叠现象，要求采样速率,f,s,满足下式,f,s,2,f,c,(3.4.9),按照,(3.4.5),式，谱分辨率,F,=,f,s,/,N,，如果保持采样点数,N,不变，要提高谱的分辨率,(,F,减小,),，必须降低采样速率，采样速率的降低会引起谱分析范围减少。如维持,f,s,不变，为提高分辨率可以增加采样点数,N,，因为,NT,=,T,p,，,T,=1/,f,-,s,，只有增加对信号的观察时间,T,p,，才能增加,N,。,T,p,和,N,可以按照下式进行选择,:,(3.4.10),(3.4.11),3.,用,DFT,进行谱分析的误差问题,DFT(,实际中用,FFT,计算,),可用来对连续信号和数字信号进行谱分析。,(1),混叠现象,。,(2),栅栏效应,。,(3),截断效应,。,根据傅里叶变换的频域卷积定理有,幅度谱,R,N,(,),曲线如图,3.4.11,所示,(,R,N,（,）以,2,为周期，只画低频部分,),。图中，,|,|2/,N,的部分称为,主瓣,， 其余部分称为,旁瓣,。,例如，,x,(,n,)=cos(,0,n,),0,=/4,其频谱为,其中,图,3.4.11,矩形窗函数的幅度谱,图,3.4.12,加矩形窗前后的频谱,泄漏,谱间干扰,