离散傅里叶变换

第3章离散傅里叶变换(DFT)第3章离散傅里叶变换(DFT)3.1离散傅里叶变换的定义及物理意义3.2离散傅里叶变换的基本性质3.3频率域采样3.4DFT的应用举例习题与上机题第3章离散傅里叶变换(DFT)傅里叶变换和Z变换是数字信号处理中常用的重要数学变换。对于有限长序列，还有一种更为重要的数学变换，即本章要讨论的离散傅里叶变换(DiscreteFourierTransform，DFT)。DFT之所以更为重要，是因为其实质是有限长序列傅里叶变换的有限点离散采样，从而实现了频域离散化，使数字信号处理可以在频域采用数值运算的方法进行，这样就大大增加了数字信号处理的灵活性。更重要的是，DFT有多种快速算法，统称为快速傅里叶变换(FastFourierTransform，FFT)，从而使信号的实时处理和设备的简化得以实现。第3章离散傅里叶变换(DFT)因此，时域离散系统的研究与应用在许多方面取代了传统的连续时间系统。所以说，DFT不仅在理论上有重要意义，而且在各种信号的处理中亦起着核心本章主要讨论DFT的定义、物理意义、基本性质以及频域采样和DFT的应用举例等内容。第3章离散傅里叶变换(DFT)3.13.1.1DFT设x(n)是一个长度为M的有限长序列，则定义x(n)的N点离散傅里叶变换为(3.1.1)1,,1,0)()]([)(10NkWnxnxDFTkXNnknN第3章离散傅里叶变换(DFT)X(k)(InverseDiscreteFourierTransform,IDFT)为式中，，N称为DFT变换区间长度，N≥M。通常称(3.1.1)式和(3.1.2)式为离散傅里叶变换对。为了叙述简洁，常常用DFT[x(n)]N和IDFT[X(k)]N分别表示N点离散傅里叶变换和N点离散傅里叶逆变换。下面证明IDFT[X(k)]2πjeNNW1,,1,0)(1)]([)(10NnWkXNkXIDFTnxNnknN(3.1.2)第3章离散傅里叶变换(DFT)把(3.1.1)式代入(3.1.2)式，有由于为整数为整数iiNnmiiNnmWNWNmxWWmxNkXIDFTNknmkNNmNknmkNnkNNkNmmkNN,,0,,111)(])([1)]([10)(1010)(1010第3章离散傅里叶变换(DFT)IDFT[X(k)]N=x(n)0≤n≤N-1由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯一的。【例3.1.1】x(n)=R4(n),求x(n)的4点和8点DFT。解设变换区间N=4，则2π33j4400j2π2πj4()()e401e01,2,31eknknnnkkXkxnWkk第3章离散傅里叶变换(DFT)设变换区间N=8，则由此例可见，x(n)的离散傅里叶变换结果与变换区间长度N的取值有关。对DFT与Z变换和傅里叶变换的关系及DFT的物理意义进行讨论后，上述问题就会得到解释。7,1,0,8sin2sin)()(837030828kkkeeWnxkXkjnnknjkn第3章离散傅里叶变换(DFT)3.1.2DFT与傅里叶变换和Z设序列x(n)的长度为M，其Z变换和N(N≥M)点DFT分别为比较上面二式可得关系式1010()ZT[()]()()DFT[()]()0,1,,1MnnMknNNnXzxnxnzXkxnxnWkN1,,1,0,)()(1,,1,0,)()(22NkeXkXNkzXkXkNjezkNj(3.1.3)或(3.1.4)第3章离散傅里叶变换(DFT)(3.1.3)式表明序列x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样。(3.1.4)式则说明X(k)为x(n)的傅里叶变换X(ejω)在区间[0,2π]上的N点等间隔采样。这就是DFT的物理意义。由此可见，DFT的变换区间长度N不同，表示对X(ejω)在区间[0,2π]上的采样间隔和采样点数不同，所以DFT的变换结果不同。上例中，x(n)=R4(n)，DFT变换区间长度N分别取8、16时，X(ejω)和X(k)的幅频特性曲线图如图3.1.1所示。由此容易得到x(n)=R4(n)的4点DFT为X(k)=DFT[x(n)]4=4δ(k)，这一特殊的结果在下面将得到进一步解释。第3章离散傅里叶变换(DFT)图3.1.1R4(n)的FT和DFT的幅度特性关系第3章离散傅里叶变换(DFT)knNW3.1.3DFT的隐含周期性前面定义的DFT变换对中，x(n)与X(k)均为有限长序列，但由于的周期性，使(3.1.1)和(3.1.2)式中的X(k)隐含周期性，且周期均为N。对任意整数m，总有所以(3.1.1)式中，X(k)满足：实际上，任何周期为N的周期序列都可以看做长度为N的有限长序列x(n)的周期延拓序列，而x(n)则是的一个周期，即(),kkmNNNNWWkm为整数,为自然数，11()00()()()()NNkmNnknNNnnXkmNxnWxnWXk)(~nx)(~nx第3章离散傅里叶变换(DFT)上述关系如图3.1.2（a）和（b）所示。一般称周期序列中从n=0到N－1的第一个周期为的主值区间，而主值区间上的序列称为的主值序列。因此x(n)与的上述关系可叙述为：是x(n)的周期延拓序列，x(n)是(3.1.5)(3.1.6)()()mxnxnmN()()()NxnxnRn)(~nx)(~nx)(~nx)(~nx)(~nx)(~nx第3章离散傅里叶变换(DFT)为了以后叙述简洁，当N大于等于序列x(n)的长度时，将(3.1.5)(3.1.7)式中x((n))N表示x(n)以N为周期的周期延拓序列，((n))N表示模N对n求余，即如果n=MN+n10≤n1≤N－1,M则((n))N=n1例如，,则有所得结果符合图3.1.2(a)和(b)()(())Nxnxn88,()(())Nxnxn88(8)((8))(0)(9)((9))(1)xxxxxx第3章离散傅里叶变换(DFT)图3.1.2x(n)及其周期延拓序列第3章离散傅里叶变换(DFT))(~nx)(~nx应当说明，若x(n)实际长度为M，延拓周期为N，则当NM时，(3.1.5)式仍表示以N为周期的周期序列，但(3.1.6)和(3.1.7)式仅对N≥M时成立。图3.1.2(a)中x(n)实际长度M=6，当延拓周期N=4时，如图3.1.2(c)所示。如果x(n)的长度为M，且，N≥M，则可写出的离散傅里叶级数表示式Nnxnx))(()(~(3.1.8)(3.1.9)111000()()(())()NNNknknknNNNNnnnXkxnWxnWxnW110011()()()NNknknNNkkxnXkWXkWNN第3章离散傅里叶变换(DFT)式中即X(k)为的主值序列。将(3.1.8)和(3.1.9)式与DFT的定义(3.1.1)和(3.1.2)式相比较可知，有限长序列x(n)的N点离散傅里叶变换X(k)正好是x(n)x((n))N的离散傅里叶级数系数的主值序列，即。后面要讨论的频域采样理论将会加深对这一关系的理解。我们知道，周期延拓序列频谱完全由其离散傅里叶级数系数确定，因此，X(k)实质上是x(n)的周期延拓序列x((n))N的频谱特性，这就是N点DFT()()()NXkXkRk(3.1.10)()Xk()Xk)()(~)(kRkXkXN()Xk第3章离散傅里叶变换(DFT)现在解释DFT[R4(n)]4=4δ(k)。根据DFT第二种物理解释可知，DFT[R4(n)]4表示R4(n)以4为周期的周期延拓序列R4((n))4的频谱特性，因为R4((n))4是一个直流序列，只有直流成分（即零频率成分）。第3章离散傅里叶变换(DFT)3.1.4用MATLAB计算序列的DFTMATLAB提供了用快速傅里叶变换算法FFT(算法见第4章介绍)计算DFT的函数fft，其调用格式如下:Xk=fft(xn,N)调用参数xn为被变换的时域序列向量，N是DFT变换区间长度，当N大于xn的长度时，fft函数自动在xn后面补零。函数返回xn的N点DFT变换结果向量Xk。当N小于xn的长度时，fft函数计算xn的前面N个元素构成的N长序列的N点DFT，忽略xnIfft函数计算IDFT，其调用格式与fft函数相同，可参考help第3章离散傅里叶变换(DFT)【例3.1.2】设x(n)=R4(n)，X(ejω)=FT[x(n)]。分别计算X(ejω)在频率区间［0，2π］上的16点和32点等间隔采样，并绘制X(ejω)解由DFT与傅里叶变换的关系知道，X(ejω)在频率区间［0，2π］上的16点和32点等间隔采样，分别是x(n)的16点和32点DFT。调用fft函数求解本例的程序ep312.m如下:第3章离散傅里叶变换(DFT)%例3.1.2程序ep312.m%DFT的MATLBxn=[1111];%输入时域序列向量xn=R4(n)Xk16=fft(xn,16);%计算xn的16点DFTXk32=fft(xn,32);%计算xn的32点DFT%以下为绘图部分（省略，程序集中有）程序运行结果如图3.1.3第3章离散傅里叶变换(DFT)图3.1.3程序ep312.m运行结果第3章离散傅里叶变换(DFT)3.23.2.1线性性质如果x1(n)和x2(n)是两个有限长序列，长度分别为N1和N2y(n)=ax1(n)+bx2(n)式中，a、b为常数，取N=max[N1,N2],则y(n)的N点DFTY(k)=DFT[y(n)]N=aX1(k)+bX2(k)0≤k≤N－1(3.2.1)其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。第3章离散傅里叶变换(DFT)3.2.2循环移位性质1设x(n)为有限长序列，长度为M，M≤N，则x(n)的循环移位定义为y(n)=x((n+m))NRN(n)(3.2.2)(3.2.2)式表明，将x(n)以N为周期进行周期延拓得到，再将左移m得到，最后取的主值序列则得到有限长序列x(n)的循环移位序列y(n)。M=6,N=8,m=2时，x(n)及其循环移位过程如图3.2.1Nnxnx))(()(~)(~nx)(~mnx)(~mnx第3章离散傅里叶变换(DFT)显然，y(n)是长度为N的有限长序列。观察图3.2.1可见，循环移位的实质是将x(n)左移m位，而移出主值区(0≤n≤N-1)的序列值又依次从右侧进入主值区。“循环移位”就是由此得名的。由循环移位的定义可知，对同一序列x(n)和相同的位移m，当延拓周期N不同时，y(n)=x((n+m))NRn(n)则不同。请读者画出N=M=6，m=2时，x(n)的循环移位序列y(n)第3章离散傅里叶变换(DFT)图3.2.1x(n)及其循环移位过程第3章离散傅里叶变换(DFT)2．时域循环移位定理设x(n)是长度为M(M≤N)的有限长序列，y(n)为x(n)则(3.2.3)其中)()]([)(kXWnyDFTkYkmNN10,)]([)(NknxDFTkXN)())(()(nRmnxnyNN第3章离散傅里叶变换(DFT)nkNNWnx))((证明令n+m=n′，则有由于上式中求和项以N为周期，因此对其在任一周期上的求和结果相同。将上式的求和区间改在主值区，则得1100()DFT[()](())()(())NNknknNNNNNNnnYkynxnmRnWxnmW11()'()(())(())NmNmknmkmknNNNNNnmnmYkxnWWxnW1100()(())()()NNkmknkmknkmNNNNNNnn