7 离散傅里叶变换(DFT)

1、4.3.1 离散傅立叶变换(DFT)引言引言DFTDFT的引出的引出 FT:FT: DFS:DFS: DFT: DFT:从从DFSDFS的时域和频域中各取出一个周期，时域成为有限长序的时域和频域中各取出一个周期，时域成为有限长序列列x(nx(n) )，频域即为该有限长序列的离散傅立叶变换，公式如下，频域即为该有限长序列的离散傅立叶变换，公式如下1,.,1 , 0)()()(10NkWnxnxDFTkXNnknNNjNeW2()( )jj nnX ex n eknNjNnenxkX210)()( 设x（n) 是一个长度为M的有限长序列，则定义的N点离散傅立叶变换为其逆变换为：1,.,1 , 0)

2、()()(10NkWnxnxDFTkXNnknN1,.,1 , 0)(1)()(10NnWkXNkXIDFTnxNkknNNjNeW2N为DFT变换区间的长度，且NM。由于x(n)和X(k)分别可以看成是从周期序列和其离散傅立叶级数中各取出来的一个周期，所以离散傅立叶正、反变换的公式与周期序列离散傅立叶级数的正、反变换公式相同，只是此时为有限长序列，离散傅立叶变换也为有限长，即k,n都限制在0-N区间的所有整数。下面证明IDFTX(k)的唯一性。 把(4-79)式代入(4-80)式有 110011()001( )( )1( )NNmkknNNkmNNk m nNmkIDFT X kx m WW

3、Nx mWN 11,()0,01Nm n MN Mk m nNm n MN MkWN M为整数 所以， 在变换区间上满足下式： IDFTX(k)=x(n), 0nN-1 由此可见， (4-80)式定义的离散傅里叶变换是唯一的。 DFT的隐含周期性 前面定义的DFT变换对中， x(n)与X(k)均为有限长序列， 但由于WknN的周期性， 使X(k)具有隐含周期性， 且周期均为N。 这是因为对任意整数m， 总有(),kk mNNNWWk m N均为整数 所以(4-79)式中， X(k)满足同理可证明(4-80)式中 11()00( )NNn mN kknNNkkx nmNX k Wx n Wx n

4、 11()00NNkmN nknNNnnX kmNx n Wx n WX k 实际上， 任何周期为N的周期序列 都可以看作长度为N的有限长序列x(n)的周期延拓序列， 而x(n)则是 的一个周期， 即xxx(n)N既可以表示一个周期序列，又可以表示序列的第n个序列值。表示序列值时 (n)N是取余运算，即(n)Nn/N的余数。 Nnxnx( )( )( )Nx nx nRn rx nx nrN（4-77）也可表示为（4-82）x(n)则是周期序列从0到N-1的一个周期，称为主值区间，表示为（4-83）图 4-11 有限长序列及其周期延拓 rx nx nrN( )( )( )Nx nx nRnx(

5、n)N表示x(n)以N为周期的周期延拓序列， 又可表示周期序列中第n个序列值，(n)N表示n对N求余， 即如果 n=MN+n1， 0n1N-1， M为整数， 则 (n)N=n1 例如， 55, ( )( ) ,Nx nx n 则有55(5)(5)(0)(6)(6)(1)xxxxxx同样可将X(k)表示为 ( )( )NX kX kRk( )( )NX kXk上述分析同样说明：有限长序列 x(n)的离散傅里叶变换X(k)正好是x(n)周期延拓序列 的离散傅立叶级数 的主值序列。 nx( )X k 例 4.14 x(n)=R4(n) ，求x(n)的8点和16点DFT 解:(1)设变换区间N=8，

6、则273880038( )( )sin()2,0,1,7sin()8jknknnNj kX kx n Wekekk(2)设变换区间N=16， 则2315316161600sin()4( )( ),0,1,15sin()16jknkknnNkX kx n Weekk图 4-12 X(k)与X(e j)的关系 可见，x(n)的离散傅里叶变换结果与变换区间长度N的取值有关.从该例可看出离散傅立叶变换DFT是对傅立叶变换DTFT在频域一个周期内的N点等间隔采样，即DFT的物理意义为它是信号的离散频谱。4.3.2 离散傅里叶变换的基本性质离散傅里叶变换的基本性质1 线性性质 如果x1(n)和x2(n)是

7、两个有限长序列， 长度分别为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 其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。 2 循环移位性质 1. 序列的循环移位 设x(n)为有限长序列， 长度为N， 则x(n)的循环移位定义为 y(n)=x(n+m)NRN(N)图 4.13 循环移位过程示意图 2. 时域循环移位定理 设x(n) 是长度为N的有限长序列， y(n)为x(n)的循环移位， 即 y(n)=x(n+m)NRN(n) 则

8、 Y(k)=DFTy(n) =W-km NX(k) (4-87) 其中X(k)=DFTx(n), 0kN-1。 此定理说明，序列在时域进行平移，将引起频域各根谱线有相应的相移。 证明： 1010( ) ( )()( )()NknNNNnNknNNnY kDFT y nx nmRn Wx nmW令n+m=n， 则有1()1( )( )( )Nmk nmNNnmNmknknNNNnmY kx nWWx nW 由于上式中求和项x(n)NWknN以N为周期， 所以对其在任一周期上的求和结果相同。 将上式的求和区间改在主值区则得110( )( )( )( )NkmknNNNnNkmknNNnkmNY k

9、Wx nWWx n WWX k 3. 频域循环移位定理如果 X(k)=DFTx(n), 0kN-1 Y(k)=X(k+l)NRN(k)则 y(n)=IDFTY(k)=WnlNx(n) (4-88)说明：序列频谱平移l，等价于时域调制l的频率。3 循环卷积定理 有限长序列x1(n)和x2(n)， 长度分别为N1和N2， N=max N1, N2 。 x1(n)和x2(n)的N点DFT分别为： X1(k)=DFTx1(n) X2(k)=DFTx2(n) 如果 X(k)=X1(k)X2(k) 则110( )( )( )()( )NNNmx nIDFT X kx mnmRn120( )( )( )()

10、( )NNNmx nIDFT X kx mnmRn(4-90) 一般称(4-90)式所表示的运算为x1(n)与x2(n)的循环卷积。 下面先证明该式， 再说明其计算方法。 证明： 直接对(4.90)式两边进行DFT 111200111200( ) ( )( )()( )( )()NNknNNNnmNNknNNnmX kDFT x nx m xnmRn Wx mxnmW 令n-m=n， 则有 11()12011120( )( )( )( )( )NNmk nmNNmnmNNmkmknNNNmnmX kx mxnWx m WxnW 因为上式中x2(n)NW knN， 以N为周期， 所以对其在任一个

11、周期上求和的结果不变。 因此11012( )( )( )( ),01NknNmX kx m WX k XkkN 循环卷积过程中， 要求对x2(m)循环反转， 循环移位， 特别是两个N长的序列的循环卷积长度仍为N。 显然与一般的线性卷积不同， 故称之为循环卷积， 记为1211201221( )( )( )( )()( )( ) ( )( )( )( )( )NNNmx nx nx nx m xnmRnX kDFT x nX kXkXkX k由于 所以 1221( )( )( )( )( )( )x nIDFT X kx nx nx nx n即循环卷积亦满足交换律。 图3.2.2 循环卷积过程示意

12、图n， m01234567x2(n)n0711x2( m)NRN(m)071x2(1 m)NRN(m)071mmx2(2 m)NRN(m)012345671m01234567n1234x(n)123456123456123456 作为习题请读者证明频域循环卷积定理： 如果 x(n)=x1(n)x2(n) 则1211202112101( ) ( )( )( )1( )()( )1( )( )( )1( )()( )NNNlNNNlX kDFT x nX kXkNX l XklRkNX kXkX kNXl XklRkN(4-92) X1(k)=DFTx1(n)X2(k)=DFTx2(n)0kN-1

13、4 复共轭序列的DFT 设x*(n)是x(n)的复共轭序列， 长度为N X(k)=DFTx(n) 则 DFTx*(n)=X*(N-k), 0kN-1 (4-93) 且 X(N)=X(0) 证明： 根据DFT的唯一性， 只要证明(4-93)式右边等于左边即可。 1()01()010()( )( )( )( )nnNN kNnNN kNnNknNnXNkx n Wx n Wx n WDFT x n 又由X(k)的隐含周期性有X(N)=X(0) 用同样的方法可以证明 DFTx*(N-n)=X*(k)5 DFT的共轭对称性 1. 有限长共轭对称序列和共轭反对称序列 为了区别于傅里叶变换中所定义的共轭对

14、称(或共轭反对称)序列， 下面用xep(n)和xop(n)分别表示有限长共轭对称序列和共轭反对称序列， 则二者满足如下定义式： xep(n)=x*ep(N-n), 0nN-1 (4-95) xop(n)=-x*op(N-n), 0nN-1 (4-96) 当N为偶数时， 将上式中的n换成N/2-n可得到 上式更清楚地说明了有很长序列共轭对称性的含义。 如图4-15所示。 图中*表示对应点为序列取共轭后的值。 ()(),01222()(),01222epepopopNNNxnxnnNNNxnxnn xep(n)=x*ep(N-n),xop(n)=-x*op(N-n), n=0,1,N-1 如同任何

15、实函数都可以分解成偶对称分量和奇对称分量一样， 任何有限长序列x(n)都可以表示成其共轭对称分量和共轭反对称分量之和， 即 x(n)=xep(n)+xop(n), 0nN-1 (4-97) 将上式中的n换成N-n， 并取复共轭， 再将(4-95)式和(4-96)式代入得到 x*(N-n)=x*ep(N-n)+x*op(N-n) =xep(n)-xop(n) (4-98) xep(n)=1/2x(n)+x*(N-n) (4-99) xop(n)=1/2x(n)-x*(N-n) (4-100) 2. DFT的共轭对称性 (1) 如果x(n)=xr(n)+jxi(n) 其中 xr=Rex(n)=1/

16、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) *DFT(),01xnXNkkN（4-93）由于所以DFTjxi(n)=1/2DFTx(n)-x*(n) =1/2X(k)-X*(N-k) =Xop(k) 由DFT的线性性质即可得 X(k)=DFTx(n)=Xep(k)+Xop(k) (4-101) 其中 Xep(k)=DFTxr(n) , X(k)的共轭对称分量 Xop(k)=DFTjxi(n) , X(k)的共轭反对称分量说明：如果序列x(n)的DFT为X(k)

17、，则x(n)的实部和虚部(包括j)的DFT分别为X(k)的共轭对称分量和共轭反对称分量 (2) 如果x(n)=xep(n)+rop(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) *DFT( ),01xNnXkkN)()(21)(*nNxnxDFTnxDFTop)(Im)()(21*kXjkXkX说明：x(n)的共轭对称分量和共轭反对称分量的DFT分别为X(k)的

18、实部和虚部乘以j。 设x(n)是长度为N的实序列， 且X(k)=DFTx(n)， 则 (1) X(k)=X*(N-k),0kN-1 (2) 如果 x(n)=x(N-n)【x(n )实偶对称】 则X(k)实偶对称， 即 X(k)=X(N-k) (3) 如果x(n)=-x(N-n) 【x(n )实奇对称】， 则X(k)纯虚奇对称， 即 X(k)=-X(N-k)利用实序列DFT的对称性，可以减少计算实序列DFT的运算量。(1)计算实序列N点DFT时，N为偶数时，只需计算前N/2+1点；N为奇数时，只需计算前(N+1)/2点，其他点按X(k)=X*(N-k)求得。 （2） 利用DFT的共轭对称性， 通

19、过计算一个N点DFT， 可以得到两个不同实序列的N点DFT， 设x1(n)和x2(n)为两个实序列， 构成新序列x(n)如下 ： x(n)=x1(n)+jx2(n), 对x(n)进行DFT， 得 X(k)=DFTx(n)= DFTx1(n)+DFTjx2(n)=X1(k)+ jX2(k) 而由DFT的共轭对称性质可知，序列实部与虚部乘以j对应的DFT分别是序列DFT的共轭对称分量与共轭反对称分量，则 X1(k) =Xep(k)=DFTx1(n)=1/2X(k)+X*(N-k) jX2(k) =Xop(k)=DFTjx2(n)=1/2X(k)-X*(N-k) 所以 X1(k)=DFTx1(n)=

20、1/2X(k)+X*(N-k) X2(k)=DFTx2(n)=-j1/2X(k)-X*(N-k)4.3.3 DFT的应用的应用 DFT的快速算法FFT的出现， 使DFT在数字通信、 语言信号处理、 图像处理、 功率谱估计、 仿真、 系统分析、 雷达理论、 光学、 医学、 地震以及数值分析等各个领域都得到广泛应用。本节介绍如何用DFT计算线性卷积以及用DFT对信号进行谱分析的方法。 1. 用DFT计算线性卷积 如果y(n)是x1(n)与x2(n)的L点循环卷积，即112120( )( )( )( )()( )LLLmy nx nx nx m xnmR n1122( )( )( )( )X kDF

21、T x nXkDFT x n0kL-1则由时域循环卷积定理有 Y(k)=DFTy(n)=X1(k)X2(k), 0kL-1 由此可见， 循环卷积既可在时域直接计算， 也可以按照图4-16所示的计算框图， 在频域计算。 由于DFT有快速算法FFT， 当N很大时， 在频域计算的速度快得多， 因而常用DFT(FFT)计算循环卷积。 图 4-16 用DFT计算循环卷积 在实际应用中， 为了分析时域离散线性非移变系统或者对序列进行滤波处理等， 需要计算两个序列的线性卷积， 与计算循环卷积一样， 为了提高运算速度， 也希望用DFT(FFT)计算线性卷积。 而DFT只能直接用来计算循环卷积， 为此导出线卷积

22、和循环卷积之间的关系以及循环卷积与线性卷积相等的条件。 假设h(n)和x(n)都是有很长序列， 长度分别是N和M。 它们的线性卷积和L点循环卷积分别表示如下： 1010( )( )( )( ) ()( )( )( )( ) ()( )NlmLcLLmy nh nx nh m x nmy nh nx nh m x nmR n其中， LmaxN, M 1010( )( )()( )( ) ()( )NcLmqNLqmy nh mx nmqL R nh m x nmqL R n ( )(),Lqx nx nqL对照线性卷积公式可以看出， 上式中 10( ) ()()( )()( )NlmclLqh

23、m x nqLMy nqLy ny nqL R n(4-104) 10Lmmlmnxmhmnxmhnxnhny所以有图4-17 线性卷积与循环卷积 0123451234h(n) x(n)nL 60123451234nL 867h(n) x(n)0123451234nL 1067h(n) x(n)（ d ）（ e ）( f )0123451234nN M1 867h(n) x(n)*nM 5012341x(n)nN 401231h(n)（ a ）（ b ）（ c ）89* * 189 10图4-18 用DFT计算线性卷积框图 补L N个零点L点DFT补L M个零点L点DFTL点IDFTy(n)h

24、(n)x(n) 设序列h(n)长度为N， x(n)为无限长序列。 将x(n)均匀分段， 每段长度取M， 则0( )( )( )( )()kikMx nx nx nx nRnkM于是， h(n)与x(n)的线性卷积可表示为000( )( )( )( )( )( )( )( )kkkkkkky nh nx nh nx nh nx ny n(4-105) 图 4-19 重叠相加法卷积示意图 M0NMMx1(n)x0(n)x2(n)N M 1N M 1y0(n)y1(n)N M 1y2(n)2MM3M N 10N 1y(n) y0(n) y1(n) y2(n) nnnnnnh(n) 2. 用DFT对信

25、号进行谱分析 所谓信号的谱分析就是计算信号的傅里叶变换。 连续信号与系统的傅里叶分析显然不便于直接用计算机进行计算， 使其应用受到限制， 而DFT是一种时域和频域均离散化的变换， 适合数值运算， 成分分析离散信号和系统的有力工具。 1. 用DFT对连续信号进行谱分析 工程实际中， 经常遇到的连续信号xa(t)， 其频谱函数Xa(j)也是连续函数。 设连续信号xa(t)持续时间和Tp， 最高频率为fc， 如图4-20所示。 xa(t)的傅里叶变换为 对xa(t)以采样间隔T1/2fc(即fs=1/T2fc)采样得 xa(t)= xa(nT)。 设共采样N点， 并对Xa(jf)作零阶近似(t=nT

26、, dt=T)得2()( )( )jfaaaXifFT x tx t etdt120()()NjfnTanX ifTx nT e 显然， Xa(jf)仍是f的连续周期函数， xa(t)和X (jf) 对 X(jf)在区间0, fs上等间隔采样N点， 采样间隔为F， 如图4-20(c)所示。 参数fs 、 Tp、 N和F满足如下关系式： 11spfFNNTFT由于NT=Tp， 所以 (4-106) (3.4.6) 将f=kF和式(3.4.5)代入X(jf)中可得Xa(jf)的采样210()()NjknNanX jkFTx nT e 0kN-1 ( )(), ( )()aaXkX jkfx nx

27、nT令 则 21010210( )( ) ( )2( )()( )1( )1( )NjknNanNnNejknNanaXkTx n eT DFT x nx nXa nTFXa k ejknNFNXkNIDFT XkT(3.4.8) TpTp=NTfs=1/TF=fs/N=1/NT=1/Tpfs2fc对连续信号进行谱分析时，给出最低谱分辨率Fmax及信号截止频率fc，确定Nmin,Tpmin,Tmax.N=fs/Ffsmin/Fmax=2fc/FmaxTp=1/F 1/FmaxT=1/fsfsmin= 1/2fc(1)混叠效应从上面的讨论可知，连续信号频谱进行数字处理时，x(n)、X(k)均为有

28、限长序列。而傅里叶变换理论指出，一般时宽有限的信号，其频谱无限长，例如单个矩形脉冲信号的频谱，反之亦然。即从理论上说，没有有限时宽的限带信号。而由处理技术的可实现性，实际上只能处理有限时宽信号。因此对频带无限的时域信号采样后，在频域中会出现混叠，形成频谱失真，不能反映原信号的全部信息，这就是混叠效应。所以用DFT作频谱分析是近似分析，当然，对不同的场合要求，可以有不同的逼近程度，从工程角度讲这是允许的。为了减小频谱混叠效应，可以采用预滤波方法滤除一定的高频成分，使待处理信号的有效带宽小于折叠频率。为了进一步减小混叠效应，除了采用预滤波技术，通常采样频率是有效带宽的35倍。 （2）栅栏效应N点DFT是频率区间 0,2上对信号的频谱进行N点等间隔采样，而采样点之间的频谱函数值是不知道的。这就好像从(N+1)个栅栏缝隙中观看信号的频谱情况，仅得到N个缝隙中看到的频谱函数值。因此称这种现象为栅栏效应。由于栅栏效应，有可能漏掉(挡住)大的频谱分量。为了把原来被“栅栏”