离散傅里叶变换(DFT)

1一、DFT的定义设x(n)是一个长度为M的有限长序列，则定义x(n)的N点离散傅里叶变换为X(k)的离散傅里叶逆变换为式中，，N称为DFT变换区间长度，10()[()](),k=0,1,,N-1(3.1.1)NknNnXkDFTxnxnW101()[()](),0,1,,-1(3.1.2)NknNkxnIDFTXkXkWnNN7.3离散傅里叶变换（DFT）2jNNWeNM2二、DFT和Z变换的关系设序列x(n)的长度为N，其Z变换和DFT分别为：1010()[()]()()[()]()0kN-1NnnNknNnXzZTxnxnzXkDFTxnxnW比较上面二式可得关系式22()(),0-1(3.1.3)()(),0-1(3.1.4)jkNzejkNXkXzkNXkXekN（3.1.3）式表明序列x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样；（3.1.4）式则说明X(k)为x(n)的傅里叶变换X(ejω)在区间[0，2π]上的N点等间隔采样。3实际上，任何周期为N的周期序列都可以看作长度为N的有限长序列x(n)的周期延拓序列，即()()(3.1.5)()()()(3.1.6)mNxnxnmNxnxnRn为了以后叙述方便，将(3.1.5)式用如下形式表示：()(())Nxnxn三、DFT的隐含周期性(),,,kkmNNNWWkmN均为整数()xnX(k)X(k)(k)(3.1.10)NR有限长序列x(n)的离散傅里叶变换X(k)，正好是x(n)的周期延拓序列x((n))N的离散傅里叶级数系数的主值序列，即X(k)4图3.1.2有限长序列及其周期延拓57.3离散傅里叶变换（DFT）定义DFT：用类似于例7.9中的方法，可把（7.3）式写成矩阵乘法运算。Xk=xn*Wnk其中，xn为序列行向量，Wnk是一N×N阶方阵，而称为旋转因子。Wnk的MATLAB表示：Wnk=WN.^([0:N-1]’*[0:N-1])10()DFT[()](),0,,1NknNnXkxnxnWkNnk00010(1)10111(1)(1)0(1)1(1)(1)NNNNNNNNNNNNNNN2jNNWe6用矩阵乘法计算N点DFT的程序如下:MATLAB程序q73a.m%用矩阵乘法计算N点DFTclear;closeallxn=input('请输入序列x=');N=length(xn);%n=0:N-1;k=n;nk=n'*k;%生成N×N方阵WN=exp(-j*2*pi/N);%旋转因子Wnk=WN.^nk;%产生旋转因子矩阵Xk=xn*Wnk;%计算N点DFT这种方法计算DFT概念清楚、编程简单，但占用内存大、运行速度低，所以不实用。MATLAB基础部分提供了fft、ifft、fft2、ifft2等等快速计算傅里叶变换的函数，使DFT的运算速度量提高了若干数量级，在后面的例题中均直接调用这些函数。7例7.15序列的离散傅立叶变换求复正弦序列余弦序列正弦序列的离散傅立叶变换，分别按N=16和N=8进行计算。绘出幅频特性曲线，进行比较讨论。解：直接产生序列x1n、x2n和x3n，调用fft函数求解j81()e()nNxnRn2()cos()8NxnnRn3()sin()8NxnnRn8•%第七章例7.15程序q715%DFT计算•clear;closeall•N=16;N1=8;•%产生序列x1(n),计算DFT[x1(n)]•n=0:N-1;•x1n=exp(j*pi*n/8);%产生x1(n)•X1k=fft(x1n,N);%计算N点DFT[x1(n)]•Xk1=fft(x1n,N1);%计算N1点DFT[x1(n)]•%产生序列x2(n),计算DFT[x2(n)]•x2n=cos(pi*n/8);•X2k=fft(x2n,N);%计算N点DFT[x2(n)]•Xk2=fft(x2n,N1);%计算N1点DFT[x1(n)]•%产生序列x3(n),计算DFT[x3(n)]•x3n=sin(pi*n/8);•X3k=fft(x3n,N);%计算N点DFT[x3(n)]•Xk3=fft(x3n,N1);%计算N1点DFT[x1(n)]9•%绘图•subplot(2,3,1);stem(n,abs(X1k),'.');•title('16点DFT[x1(n)]');•xlabel('k');ylabel('|X1(k)|')•subplot(2,3,2);stem(n,abs(X2k),'.');•title('16点DFT[x2(n)]');•xlabel('k');ylabel('|X2(k)|')•subplot(2,3,3);stem(n,abs(X3k),'.');•title('16点DFT[x3(n)]');•xlabel('k');ylabel('|X3(k)|')•k=0:N1-1;•subplot(2,3,4);stem(k,abs(Xk1),'.');•title('8点DFT[x1(n)]');•xlabel('k');ylabel('|X1(k)|')•subplot(2,3,5);stem(k,abs(Xk2),'.');•title('8点DFT[x2(n)]');•xlabel('k');ylabel('|X2(k)|')•subplot(2,3,6);stem(k,abs(Xk3),'.');•title('8点DFT[x3(n)]');•xlabel('k');ylabel('|X3(k)|')10在截取16点时，得到的是完整的余弦波形；而截取8点时，得到的是半截的余弦波形，当然有大量的谐波成分。11例7.16验证N点DFT的物理意义（1）绘出幅频曲线和相频曲线。（2）计算并图示x(n)的8点DFT。（3）计算并图示x(n)的16点DFT。解:序列x(n)的Ｎ点DFT的物理意义是在[0，2]上进行Ｎ点等间隔采样。程序先密集采样，绘制出幅频曲线图。然后再分别做8点和16点DFT来验证这个采样关系。程序略。441()(),()[()]1jjjexnRnXeFTxne求得，()jXe12图7.16离散傅里叶变换与傅里叶变换的采样关系13频域采样定理频域采样是指对有限长序列的傅氏变换在频域离散化得到X(k)的过程。本节讨论两个基本问题：a：频域采样（DFT）不失真的条件，即由X(k)不失真地恢复x(n)的条件b：用X(k)表示X(z)和的插值公式(内插公式)()jXe14图3-3-1时域恢复示意图结论：若序列长度为L，频域采样点数（DFT的长度）为N，且L≤N，则频域采样后可不失真地恢复原序列；但若LN，则频域采样后不能不失真地恢复原序列。()xn()xn15例7.17频域与时域采样对偶性（1）产生三角波序列（2）对M=40，计算x(n)的64点DFT，并图示x(n)和X(k)=DFT[x(n)]，k=0,1,…,63。（3）对（2）中所得X(k)在[0，2]上进行32点抽样得（4）求的32点IDFT，即（5）绘出的波形图，评述它与x(n)的关系。0/2()/2nnMxnMnMnM1()(2)0131XkXkk，，，，1()Xk11()IDFT[()]n=01xnXk，，，，31132(())xn16%第七章例7.17程序q717%时域与频域采样的对偶性验证clear;closeallM=40;N=64;n=0:M;%产生M长三角波序列x(n)xa=0:floor(M/2);xb=ceil(M/2)-1:-1:0;xn=[xa,xb];Xk=fft(xn,64);%64点FFT[x(n)]X1k=Xk(1:2:N);%隔点抽取Xk得到X1(K)x1n=ifft(X1k,N/2);%32点IFFT[X1(k)]得到x1(n)nc=0:3*N/2;%取97点为观察区xc=x1n(mod(nc,N/2)+1);%x1(n)的周期延拓序列subplot(3,2,1);stem(n,xn,'.')title('40点三角波序列x(n)');xlabel('n');ylabel('x(n)')17k=0:N-1;subplot(3,2,3);stem(k,abs(Xk),'.')title('64点DFT[x(n)]');xlabel('k');ylabel('|X(k)|')k=0:N/2-1;subplot(3,2,4);stem(k,abs(X1k),'.')title('X(k)的隔点抽取');xlabel('k');ylabel('|X1(k)|')n1=0:N/2-1;subplot(3,2,2);stem(n1,x1n,'.')title('32点IDFT[X1(k)]');xlabel('n');ylabel('x1(n)')subplot(3,1,3);stem(nc,xc,'.')title('x1(n)的周期延拓序列');xlabel('n');ylabel('x(mod(n,32))')set(gcf,'color','w')1819由于频域在[0，2]上的采样点数N（N=32）小于x(n)的长度M（M=40），所以，产生时域混叠现象，不能由X1(k)恢复原序列x(n)。只有满足N≥M时，可由频域采样X1(k)得到原序列x(n)。这就是频域采样定理。对N≥M的情况，请读者自己编程验证。1()IDFT[()]xnXk20用DFT计算线性卷积112120()()()()(())()LLLmynxnxnxmxnmRn1122()[()]()[()]XkDFTxnXkDFTxn0≤k≤L-1则由时域循环卷积定理有Y(k)=DFT［y(n)］=X1(k)X2(k),0≤k≤L-1如果21由此可见，循环卷积既可在时域直接计算，也可以按照图3.4.1所示的计算框图，在频域计算。由于DFT有快速算法FFT，当N很大时，在频域计算的速度快得多，因而常用DFT(FFT)计算循环卷积。图3.4.1用DFT计算循环卷积22在实际应用中，需要计算两个序列的线性卷积，与计算循环卷积一样，为了提高运算速度，也希望用DFT(FFT)计算线性卷积。而DFT只能直接用来计算循环卷积，为此导出线卷积和循环卷积之间的关系以及循环卷积与线性卷积相等的条件。假设h(n)和x(n)都是有限长序列，长度分别是N和M。它们的线性卷积和循环卷积分别表示如下：1010()()()()()()()()()(())()NlmLcLLmynhnxnhmxnmynhnxnhmxnmRn(3.4.1)(3.4.2)23其中，L≥max［N,M］，所以1010()()()()()()()NcLmqNLqmynhmxnmqLRnhmxnmqLRn(())(),LqxnxnqL对照式(3.4.1)可以看出，上式中()()()clLqynynqLRn(3.4.3)10()()()NlmhmxnqLMynqL即(3.4.3)式说明，yc(n)等于yl(n)以L为周期的周期延拓序列的主值序列。yl(n)长度为N+M-1，只有当循环卷积长度L≥N+M-1时，yl(n)以L为周期进行周期延拓才无混叠现象。24图3.4.2线性卷积与循环卷积0123451234h(n)x(n)nL＝60123451234nL＝867h(n)x(n)0123451234nL＝1067h(n)x(n)（d）（e）(f)012345123