(整理)离散傅里叶变换

精品文档精品文档第三章离散傅立叶变换(DFT)3．1引言有限长序列在数字信号处理是很重要的一种序列，当然可以用Z变换和傅里叶变换来研究它，但是，可以导出反映它的有限长特点的一种有用工具是离散傅里叶变换(DFT)。离散傅里叶变换除了作为有限长序列的一种傅里叶表示法在理论上相当重要之外，而且由于存在着计算离散傅里叶变换的有效快速算法，因而离散傅里叶变换在各种数字信号处理的算法中起着核心的作用。有限长序列的离散傅里叶变换(DFT)和周期序列的离散傅里叶级数(DFS)本质上是一样的。为了更好地理解DFT，需要先讨论周期序列的离散傅里叶级数DFS。而为了讨论离散傅里叶级数及离散傅里叶变换，我们首先来回顾并讨论傅里叶变换的几种可能形式。(连续时间信号：如果在讨论的时间间隔内，除若干不连续点之外，对于任意时间值都可给出确定的函数值，此信号就称为连续时间信号。)一、连续时间、连续频率——连续傅立叶变换（FT）设x(t)为连续时间非周期信号，傅里叶变换关系如下图所示：可以看出时域连续函数造成频域是非周期的谱，而时域的非连续，非周期非周期，连续精品文档精品文档周期造成频域是连续的谱。二、连续时间，离散频率------傅里叶级数设f(t)代表一个周期为T1的周期性连续时间函数，f(t)可展成傅里叶级数，其傅里叶级数的系数为nF，f(t)和nF组成变换对，表示为:tjnnneFtf1)(（112T）dtetfTFTTtjnn221111)(1注意符号：如果是周期性的采样脉冲信号p(t)，周期用T表示（采样间隔）。采样脉冲信号的频率为Ts2可以看出时域连续函数造成频域是非周期的谱，而时域的周期造成频域是离散的谱三、离散时间，连续频率------序列的傅里叶变换连续，周期（时域周期为T1）非周期，离散（离散间隔为1）精品文档精品文档正变换：DTFT[x(n)]=()()jnjnXexne反变换：DTFT-11[()]()()2jnjjXexnXeed)(jeX级数收敛条件为|()jnnxne|=nnx)(可以看出时域离散函数造成频域是周期的谱，而时域的非周期造成频域是连续的谱四、离散时间，离散频率------离散傅里叶变换上面讨论的三种傅里叶变换对，都不适用在计算机上运算，因为至少在一个域(时域或频域)中，函数是连续的。因为从数字计算角度，我们感兴趣的是时域及频域都是离散的情况，这就是我们这里要谈到的离散傅里叶变换。时域抽样间隔T，频域周期s=2/T，时域周期T1，频域抽样间隔1=2/T1离散，非周期（离散时间间隔为T）周期，连续（频域周期为2=sT）精品文档精品文档周期序列的离散傅里叶级数（DFS）设)(~nx是周期为N的一个周期序列，即)(~)(~rNnxnx，r为任意整数。和连续时间周期信号一样，周期序列可用离散傅里叶级数来表示。离散傅里叶级数（DFS）对：正变换)(~kX=DFS[)(~nx]=210()NjknNnxne=nkNNnWnx10)(~k反变换)(~nx=IDFS[)(~kX]=102)(~1NkknNjekXN=10)(~1NknkNWkXNn式中，NjNeW2，k和n均为整数。观察)(~kX=knNjNnenx210)(~。)(~kX是一个周期序列吗？如是，周期为多少？10)(2)(~)(~NnnmNkNjenxmNkXknNjNnenx210)(~=)(~kX。所以。)(~kX是一个周期序列，周期为N。)(~nx，周期为N)(~kX，周期也为N。精品文档精品文档观察)(~nx=102)(~1NkknNjekXN，与连续时间信号与系统中的傅里叶级数对应，表明将周期序列分解成N个独立谐波分量。第0次谐波序列20jnNe，基波序列21jnNe，…，第k次谐波序列knNje2，第N-1次谐波序列2(1)jNnNe。谐波频率kNk)/2(，k=0，1，2，…，N-1，幅度为)/1(N)(~kX。例如：基波分量的频率为2/N，幅度是)/1(N)1(~X。一个周期序列可以用其DFS表示它的频谱分布规律。例题：)(~nx如图所示，求)(~nx的DFS解：)(~kX=DFS[)(~nx]=210()NjknNnxne=nkNNnWnx10)(~k)(~kX=2780()jknnxne=2380jknne=2482811jkjkee=411jkjkee=222888()()jkjkjkjkjkjkeeeeee=38sin2sin8jkkek，k|)(~kX|如下图所示。精品文档精品文档离散傅立叶变换（DFT）周期序列实际上只有有限个序列值才有意义，因而它的离散傅里叶级数表示式也适用于有限长序列，这就可以得到有限长序列的傅里叶变换(DFT)。设x(n)是一个长度为M的有限长序列，正变换)(kX=DFT[)(nx]=nkNjNnenx210)(=nkNNnWnx10)(k=0，1，2，…，N-1（3.1.1）反变换)(nx=IDFT[)(kX]=102)(1NkknNjekXN=10)(1NknkNWkXNn=0，1，2，…，N-1（3.1.2）式中NjNeW2，N称为DFT变换区间长度，N≥M。例3．1．1：)(nx=R4(n)，求)(nx的8点和16点DFT。解：（1）DFT变换区间N=8，则：()Xk=2780()jknnxne=2380jknne=2482811jkjkee=411jkjkee=38sin2sin8jkkek，k=0，1，…，7（2）DFT变换区间N=16，则：()Xk=215160()jknnxne=23160jknne精品文档精品文档=316sin4sin16jkkek，k=0，1，…，15DFS与DFT的关系1、有限长序列和周期序列的关系设x(n)是一个长度为M的有限长序列，以N（N≥M）为周期进行周期延拓得)(~nx。)(~nx是x(n)的周期延拓。如下图所示：M=4，N=8，以N=8进行周期延拓。)(~nx的周期为8。用式子表示：)(~nx＝rrNnx)(或)(~nx＝x(n模N)＝x((n))N，(n模N)表示n对N取余数例：设)(~nx是以N=8周期对有限长序列x(n)（长度M=4）进行周期延拓得到的。)5(~x＝x(3)，(10)x=x(2)。有限长序列进行周期延拓得到周期序列。定义：周期序列)(~nx中从n=0到N-1的第一个周期为)(~nx的主值区间，而主值区间上的序列称为)(~nx的主值序列周期序列的主值序列是有限长序列利用前面的矩形序列符号RN(n)精品文档精品文档RN(n)=1，0≤n≤N-10，其他nx(n)=)(~nxRN(n)x(n)的周期延拓序列是)(~nx；)(~nx＝x((n))N)(~nx的主值序列是x(n)；x(n)=)(~nxRN(n)同理把频域周期序列)(~kX也看作是有限长序列X(k)的周期延拓。X(k)是)(~kX的主值序列X(k)的周期延拓序列是)(~kX；)(~kX＝X((k))N)(~kX的主值序列是X(k)；X(k)=)(~kXRN(n)具体而言，我们把时域周期序列)(~nx看作是有限长序列x(n)的周期延拓；同理把频域周期序列)(~kX也看作是有限长序列X(k)的周期延拓。这样我们只要把DFS的定义式两边取主值区间，就得到了一个关于有限长序列的时频域对应的变换对。这就是数字信号处理课程里最重要的变换-------离散傅里叶变换(DFT)。离散傅立叶级数（DFS）对：正变换)(~kX=DFS[)(~nx]=210()NjknNnxne=nkNNnWnx10)(~k反变换)(~nx=IDFS[)(~kX]=102)(~1NkknNjekXN=10)(~1NknkNWkXNn式中，NjNeW2，k和n均为整数。离散傅里叶变换(DFT)正变换：)(kX＝DFT[x(n)]=nkNNnWnx10)(，0≤k≤N-1精品文档精品文档反变换：x(n)=IDFT[)(kX]=10)(1NknkNWkXN，0≤n≤N-1或：)(kX＝nkNNnWnx10)(RN(k)＝)(~kXRN(k)x(n)=10)(1NknkNWkXNRN(n)=)(~nxRN(n)DFT隐含有周期性。DFT和Z变换的关系设序列x(n)的长度为N，其Z变换和DFT分别为：nnznxzX)()(0z)(kX＝DFT[x(n)]=nkNNnWnx10)(，0≤k≤N-1比较上面两式可以得到：)(kX＝()Xz|2jkNze，0≤k≤N-1（3.1.3）或)(kX=)(jeX|2kN，0≤k≤N-1（3.1.4）（3.1.3）表明序列x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样。（3.1.4）表明)(kX是x(n)的傅立叶变换)(jeX在区间[0，2π]上的N点等间隔采样。这就是DFT的物理意义。由此可见，DFT的变换区间长度N不同，表示对)(jeX在[0，2π]区间上的采样间隔和采样点数不同，所以DFT的变换结果不同。例3．1．1中，)(nx=R4(n)，DFT变换区间长度N分别取8点和16点，)(kX结果不同。下图为R4(n)的傅立叶变换)(jeX和R4(n)的8点、16点)(kX的对应图。精品文档精品文档精品文档精品文档3．2离散傅立叶变换的性质一、线性设x1(n)、x2(n)是两个有限长序列，长度分别为N1，N2，且y(n)=ax1(n)+bx2(n)，a，b为常数。N=max[N1，N2]。x1(n)有限长序列，长度为N；x2(n)有限长序列，长度为N；y(n)有限长序列，长度为N；x1(n)的N点DFT为：X1(k)=DFT[x1(n)]=nkNNnWnx101)(0≤k≤N-1x2(n)的N点DFT为：X2(k)=DFT[x2(n)]=nkNNnWnx102)(0≤k≤N-1y(n)的N点DFT为：Y(k)=DFT[y(n)]=nkNNnWny10)(=nkNNnWnbxnax1021))()((=aX1(k)+bX2(k)0≤k≤N-1二、循环移位定理1、序列的循环移位设x(n)为有限长序列，长度为N，则x(n)的循环移位定义为)())(()(nRmnxnyNN（3.2.2）（3.2.2）表明先将x(n)以N为周期进行周期延拓得到序列)(~nx=x((n))N，再将)(~nx左移得到()xnm，最后取()xnm主值区间（n=0到N-1）上的序列值，则得到有限长序列x(n)的循环移位序列()yn。过程如下图所示：)())(()(nRmnxnyNN精品文档精品文档2、时域循环移位定理设x(n)为有限长序列，长度为N，()yn为x(n)的循环移位序列，即)())(()(nRmnxnyNN，则)]([)(nyDFTkYDFT[)())((nRmnxNN]=)(kXWmkN其中)(kX=DFT[x(n)]，0≤k≤N-1证明：)]([)(nyDFTkY10(())()NknNNNnxnmRnW=10(())NknNNnxnmW令n+m=n’，则有()Yk=''1'()(())NmknmNNnmxnW精品文档精品文档=''1'(())NmkmknNNNnmWxnW由于上式中求和项以N为周期，所以对其在任一周期上的求和结果相同。将上式的求和区间改在主值区间，则得：()Yk=''1'0(())N