数字信号处理课后答案+第3章DFT+FFTVIP

教材第3章习题与上机题解答1计算以下序列的N点DFT，在变换区间0nN1内，序列定义为(1)x(n)=1(2)x(n)=(n)(3)x(n)=(nn0)0n0N(4)x(n)=Rm(n)0mN(5)(6),(7)x(n)=ej0nRN(n)(8)x(n)=sin(0n)RN(n)(9)x(n)=cos(0n)RN(N)(10)x(n)=nRN(n)解：,(1),（2）,（3）,(4),(5),0kN1,(6),0kN1,(7),或,（8）解法一直接计算：,解法二由DFT的共轭对称性求解。因为,所以,所以,即,结果与解法一所得结果相同。此题验证了共轭对称性。(9)解法一直接计算:,解法二由DFT共轭对称性可得同样结果。因为,（10）解法一,上式直接计算较难，可根据循环移位性质来求解X(k)。因为x(n)=nRN(n)，所以x(n)x(n1)NRN(n)+N(n)=RN(n)等式两边进行DFT，得到X(k)X(k)WkN+N=N(k),故,当k=0时，可直接计算得出X(0)为,这样，X(k)可写成如下形式：,解法二k=0时，,k0时，,所以，,，即,2已知下列X(k)，求x(n)=IDFTX(k),(1),(2),其中，m为正整数，0mN/2,N为变换区间长度。,解:（1）,n=0,1,N1,(2),n=0,1,N1,3已知长度为N=10的两个有限长序列：,做图表示x1(n)、x2(n)和y(n)=x1(n)*x2(n)，循环卷积区间长度L=10。解:x1(n)、x2(n)和y(n)=x1(n)*x2(n)分别如题3解图（a）、（b）、（c）所示。,题3解图,4证明DFT的对称定理，即假设X(k)=DFTx(n)，证明DFTX(n)=Nx(Nk)证：因为,所以,由于,所以DFTX(n)=Nx(Nk)k=0,1,N15如果X(k)=DFTx(n)，证明DFT的初值定理,证:由IDFT定义式,可知,6设x(n)的长度为N，且X(k)=DFTx(n)0kN1令h(n)=x(n)NRmN(n)m为自然数H(k)=DFTh(n)mN0kmN1求H(k)与X(k)的关系式。解:H(k)=DFTh(n)0kmN1令n=n+lN,l=0,1,m1,n=0,1,N1,则,因为,所以,7证明:若x(n)为实序列，X(k)=DFTx(n)N，则X(k)为共轭对称序列，即X(k)=X*（Nk)；若x(n)实偶对称，即x(n)=x(Nn)，则X(k)也实偶对称；若x(n)实奇对称，即x(n)=x(Nn)，则X(k)为纯虚函数并奇对称。,证:(1)由教材(3.2.17)(3.2.20)式知道，如果将x(n)表示为x(n)=xr(n)+jxi(n)则X(k)=DFTx(n)=Xep(k)+Xop(k)其中，Xep(k)=DFTxr(n)，是X(k)的共轭对称分量；Xop(k)=DFTjxi(n),是X(k)的共轭反对称分量。所以，如果x(n)为实序列，则Xop(k)=DFTjxi(n)=0，故X(k)=DFTx(n)=Xep(k)，即X(k)=X*(Nk)。,（2）由DFT的共轭对称性可知，如果x(n)=xep(n)+xop(n)且X(k)=ReX(k)+jImX(k)则ReX(k)=DFTxep(n),jImX(k)=DFTxop(n)所以，当x(n)=x(Nn)时，等价于上式中xop(n)=0,x(n)中只有xep(n)成分，所以X(k)只有实部，即X(k)为实函数。又由（1）证明结果知道，实序列的DFT必然为共轭对称函数，即X(k)=X*(Nk)=X(Nk)，所以X(k)实偶对称。,同理，当x(n)=x(Nn)时，等价于x(n)只有xop(n)成分（即xep(n)=0），故X(k)只有纯虚部，且由于x(n)为实序列，即X(k)共轭对称，X(k)=X*(Nk)=X(Nk),为纯虚奇函数。8证明频域循环移位性质：设X(k)=DFTx(n)，Y(k)=DFTy(n)，如果Y(k)=X(k+l)NRN(k)，则,证：,令m=k+l,则,9已知x(n)长度为N，X(k)=DFTx(n)，,求Y(k)与X(k)的关系式。解:,10证明离散相关定理。若X(k)=X1*(k)2(k)则,证：根据DFT的惟一性，只要证明,即可。,令m=l+n，则,所以,当然也可以直接计算X(k)=X1*(k)X2(k)的IDFT。,0nN1,由于,0nN1,所以,11证明离散帕塞瓦尔定理。若X(k)=DFTx(n)，则,证：,12已知f(n)=x(n)+jy(n)，x(n)与y(n)均为长度为N的实序列。设F(k)=DFTf(n)N0kN1,(1),(2)F(k)=1+jN试求X(k)=DFTx(n)N，Y(k)=DFTy(n)N以及x(n)和y(n)。解:由DFT的共轭对称性可知x(n)X(k)=Fep(k)jy(n)jY(k)=Fop(k),方法一（1）,0nN1,由于,0n,mN1,所以x(n)=an0nN1同理y(n)=bn0nN1（2）F(k)=1+jN,，,方法二令,只要证明A(k)为共轭对称的，B(k)为共轭反对称，则就会有A(k)=Fep(k)=X(k),B(k)=Fop(k)=jY(k)因为,，共轭对称,，共轭反对称,所以,由方法一知x(n)=IDFTX(k)=anRN(n)y(n)=IDFTY(k)=bnRN(n)13已知序列x(n)=anu(n)，0a1,对x(n)的Z变换X(z)在单位圆上等间隔采样N点，采样序列为,求有限长序列IDFTX(k)N。解:我们知道，,是以2为周期的周期函数，所以,以N为周期，将看作一周期序列的DFS系数，则,由式知为,将式代入式得到,由于,所以,由题意知,所以根据有关X(k)与xN(n)的周期延拓序列的DFS系数的关系有,由于0nN1，所以,因此,说明：平时解题时，本题推导,的过程可省去，直接引用频域采样理论给出的结论（教材中式（3.3.2）和(3.3.3)）即可。14两个有限长序列x(n)和y(n)的零值区间为x(n)=0n0,8ny(n)=0n0,20n对每个序列作20点DFT，即X(k)=DFTx(n)k=0,1,19Y(k)=DFTy(n)k=0,1,19试问在哪些点上f(n)与x(n)*y(n)值相等,为什么？,解:如前所述，记fl(n)=x(n)*y(n)，而f(n)=IDFTF(k)=x(n)20y(n)。fl(n)长度为27，f(n)长度为20。由教材中式（3.4.3）知道f(n)与fl(n)的关系为,只有在如上周期延拓序列中无混叠的点上，才满足f(n)=fl(n),所以f(n)=fl(n)=x(n)*y(n)7n19,15已知实序列x(n)的8点DFT的前5个值为0.25,0.125-j0.3018,0,0.125-j0.0518,0。（1）求X(k)的其余3点的值；,（2）,求X1(k)=DFTx1(n)8；,（3）,，求,。,解：（1）因为x(n)是实序列，由第7题证明结果有X(k)=X*(Nk)，即X(Nk)=X*(k),所以，X（k）的其余3点值为X(5),X(6),X(7)=0.125+j0.0518,0,0.125+j0.3018（2）根据DFT的时域循环移位性质，,(3),16x(n)、x1(n)和x2(n)分别如题16图(a)、(b)和(c)所示，已知X(k)=DFTx(n)8。求,和,注:用X(k)表示X1(k)和X2(k)。,解：因为x1(n)=x(n+3)8R8(n),x2(n)=x(n2)8R8(n)，所以根据DFT的时域循环移位性质得到,17设x(n)是长度为N的因果序列，且,试确定Y(k)与X(ej)的关系式。,解：y(n)是x(n)以M为周期的周期延拓序列的主值序列，根据频域采样理论得到,18用微处理机对实数序列作谱分析，要求谱分辨率F50Hz，信号最高频率为1kHz，试确定以下各参数：(1)最小记录时间Tpmin；(2)最大取样间隔Tmax；(3)最少采样点数Nmin；(4)在频带宽度不变的情况下，使频率分辨率提高1倍（即F缩小一半）的N值。,解:（1）已知F=50Hz，因而,（2）,（3）,（4）频带宽度不变就意味着采样间隔T不变，应该使记录时间扩大1倍，即为0.04s，实现频率分辨率提高1倍（F变为原来的1/2）。,19已知调幅信号的载波频率fc=1kHz，调制信号频率fm=100Hz，用FFT对其进行谱分析，试求：(1)最小记录时间Tpmin;(2)最低采样频率fsmin;(3)最少采样点数Nmin。,解：调制信号为单一频率正弦波时，已调AM信号为x(t)=cos(2fct+jc)1+cos(2fmt+jm)所以，已调AM信号x(t)只有3个频率：fc、fc+fm、fcfm。x(t)的最高频率fmax=1.1kHz，频率分辨率F100Hz（对本题所给单频AM调制信号应满足100/F=整数，以便能采样到这三个频率成分）。故,(1),(2),(3),（注意，对窄带已调信号可以采用亚奈奎斯特采样速率采样，压缩码率。而在本题的解答中，我们仅按基带信号的采样定理来求解。）20在下列说法中选择正确的结论。线性调频Z变换可以用来计算一个有限长序列h(n)在z平面实轴上诸点zk的Z变换H(zk)，使,(1)zk=ak,k=0,1,N1,a为实数，a1;(2)zk=ak,k=0,1,N1,a为实数，a1;(3)(1)和(2)都不行，即线性调频Z变换不能计算H(z)在z平面实轴上的取样值。解：在chirp-Z变换中，在z平面上分析的N点为zk=AWkk=0,1,N1其中所以当A0=1,0=0,W0=a1,j=0时，zk=ak故说法（1）正确,说法（2）、（3）不正确。,21我们希望利用h(n)长度为N=50的FIR滤波器对一段很长的数据序列进行滤波处理，要求采用重叠保留法通过DFT(即FFT)来实现。所谓重叠保留法，就是对输入序列进行分段(本题设每段长度为M=100个采样点)，但相邻两段必须重叠V个点，然后计算各段与h(n)的L点(本题取L=128)循环卷积，得到输出序列ym(n)，m表示第m段循环卷积计算输出。最后，从ym(n)中选取B个样值，使每段选取的B个样值连接得到滤波输出y(n)。,(1)求V；(2)求B；(3)确定取出的B个采样应为ym(n)中的哪些样点。解:为了便于叙述，规定循环卷积的输出序列ym(n)的序列标号为n=0,1,2,127。先以h(n)与各段输入的线性卷积ylm(n)分析问题，因为当h(n)的50个样值点完全与第m段输入序列xm(n)重叠后，ylm(n)才与真正的滤波输出y(n)相等，所以，ylm(n)中第0点到第48点（共49个点）不正确，不能作为滤波输出，第49点到第99点（共51个点）为正确的滤波输出序列y(n)的第m段，即B=51。,所以，为了去除前面49个不正确点，取出51个正确的点连接,得到不间断又无多余点的y(n)，必须重叠10051=49个点，即V=49。下面说明，对128点的循环卷积ym(n)，上述结果也是正确的。我们知道,因为ylm(n)长度为,N+M1=50+1001=149,所以n从21到127区域无时域混叠，ym(n)=ylm(n)，当然，第49点到第99点二者亦相等，所以，所取出的51点为从第49点到第99点的ym(n)。综上所述，总结所得结论：V=49,B=51选取ym(n)中第4999点作为滤波输出。读者可以通过作图来理解重叠保留法的原理和本题的解答。,22证明DFT的频域循环卷积定理。证：DFT的频域循环卷积定理重写如下:设h(n)和x(n)的长度分别为N和M，ym(n)=h(n)x(n)H(k)=DFTh(n)L,X(k)=DFTX(n)L则,LX(k),其中，LmaxN，M。,根据DFT的惟一性，只要证明ym(n)=IDFTYm(k)=h(n)x(n)，就证明了DFT的频域循环卷积定理。,23*已知序列x(n)=1,2,3,3,2,1。（1）求出x(n)的傅里叶变换X(ej)，画出幅频特性和相频特性曲线(提示：用1024点FFT近似X(ej)；（2）计算x(n)的N（N6）点离散傅里叶变换X(k)，画出幅频特性和相频特性曲线；（3）将X(ej)和X(k)的幅频特性和相频特性曲线分别画在同一幅图中，验证X(k)是X(ej)的等间隔采样，采样间隔为2/N；（4）计算X(k)的N点IDFT，验证DFT和IDFT的惟一性。,解：该题求解程序为ex323.m，程序运行结果如题23*解图所示。第（1）小题用1024点DFT近似x(n)的傅里叶变换；第（2）小题用32点DFT。题23*解图(e)和(f)验证了X(k)是X(ej)的等间隔采样，采样间隔为2/N。题23*解图(g)验证了IDFT的惟一性。,题23*解图,24*给定两个序列:x1(n)=2,1,1,2,x2(n)=1,1,1,1。（1）直接在时域计算x1(n)与x2(n)的卷积；（2）用DFT计算x1(n)与x2(n)的卷积，总结出DFT的时域卷积定理。解：设x1(n)和x2(n)的长度分别为M1和M2，X1(k)=DFTx1(n)N,X2(k)=DFTx2(n)NYc(k)=X1(k)X2(k),yc(n)=IDFTYc(k)N所谓DFT的时域卷积定理，就是当NM1+M21时，yc(n)=x1(n)*x2(n)。,本题中，M1=M2=4，所以，程序中取N=7。本题的求解程序ex324.m如下：%程序ex324.mx1n=2112；x2n=1111；%时域直接计算卷积yn：yn=conv(x1n，x2n)%用DFT计算卷积ycn：M1=length(x1n)；M2=length(x2n)；N=M1+M21；X1k=fft(x1n，N)；%计算x1n的N点DFTX2k=fft(x2n，N)；%计算x2n的N点DFTYck=X1k.*X2k；ycn=ifft(Yck，N),程序运行结果：直接在时域计算x1(n)与x2(n)的卷积yn和用DFT计算x1(n)与x2(n)的卷积ycn如下：yn=2122212ycn=2.00001.00002.00002.00002.00001.00002.0000,25*已知序列h(n)=R6(n),x(n)=nR8(n)。（1）计算yc(n)=h(n)8x(n)；（2）计算yc(n)=h(n)16x(n)和y(n)=h(n)*x(n)；（3）画出h(n)、x(n)、yc(n)和y(n)的波形图，观察总结循环卷积与线性卷积的关系。解：本题的求解程序为ex325.m。程序运行结果如题25*解图所示。由图可见，循环卷积为线性卷积的周期延拓序列的主值序列；当循环卷积区间长度大于等于线性卷积序列长度时，二者相等，见图（b）和图(c)。,题25*解图,程序ex325.m如下：%程序ex325.mhn=1111；xn=0123；%用DFT计算4点循环卷积yc4n：H4k=fft(hn，4)；%计算h(n)的4点DFTX4k=fft(xn，4)；%计算x(n)的4点DFTYc4k=H4k.*X4k；yc4n=ifft(Yc4k，4)；%用DFT计算8点循环卷积yc8n：H8k=fft(hn，8)；%计算h(n)的8点DFTX8k=fft(xn，8)；%计算x(n)的8点DFTYc8k=H8k.*X8k；yc8n=ifft(Yc8k，8)；yn=conv(hn，xn)；%时域计算线性卷积yn：,26*验证频域采样定理。设时域离散信号为,其中a=0.9，L=10。（1）计算并绘制信号x(n)的波形。,（2）证明：,（3）按照N=30对X(ej)采样得到,（4）计算并图示周期序列,试根据频域采样定理解释序列与x(n)的关系。,（5）计算并图示周期序列,，比较,与验证（4）中的解释。（6）对N=15，重复（3）（5）。解：求解本题（1）、（3）、（4）、（5）、（6）的程序为ex326.m。下面证明（2）。,N=30和N=15时，对频域采样Ck进行离散傅里叶级数展开得到的序列分别如题26*解图(b)和(c)所示。由图显而易见，如果Ck表示对X(ej)在0，2上的N点等间隔采样，则,简言述之：xN(n)是x(n)以N为周期的周期延拓序列的主值序列。,程序ex326.m如下：程序中直接对（2）中证明得到的结果采样得到Ck。%程序ex326.m%频域采样理论验证clearall；closeall；a=0.9；L=10；n=-L：L；%=N=30=N=30；xn=a.abs(n)；%计算产生序列x(n)subplot(3，2，1)；stem(n，xn，.)；axis(15，15，0，1.2)；%(1)显示序列x(n)title(a)x(n)的波形)；xlabel(n)；ylabel(x(n)；boxon,%对X(jw)采样30点：fork=0：N1，Ck(k+1)=1；form=1：L，Ck(k+1)=Ck(k+1)+2*xn(m+L+1)*cos(2*pi*k*m/N);%(3)计算30点%采样Ckendendx30n=ifft(Ck，N)；%(4)30点IDFT得到所要求的周期序列的主值序列%以下为绘图部分n=0：N1；,subplot(3，2，2)；stem(n，x30n，.)；axis(0，30，0，1.2)；boxontitle(b)N=30由Ck展开的的周期序列的主值序列)；xlabel(n)；ylabel(x30(n)%=N=15=N=15；%对X(jw)采样15点：fork=0：N1，Ck(k+1)=1；form=1：L，Ck(k+1)=Ck(k+1)+2*xn(m+L+1)*cos(2*pi*k*m/N);%(3)计算30点%采样Ckendend,x15n=ifft(Ck，N)；%(4)15点IDFT得到所要求的周期序列的主值序列%以下为绘图部分n=0：N1；subplot(3，2，3)；stem(n，x15n，.)；axis(0，30，0，1.2)；boxontitle(c)N=15由Ck展开的的周期序列的主值序列)；xlabel(n)；ylabel(x15(n)程序运行结果如题26*解图所示。,题26*解图,27*选择合适的变换区间长度N，用DFT对下列信号进行谱分析，画出幅频特性和相频特性曲线。（1）x1(n)=2cos(0.2n)（2）x2(n)=sin(0.45n)sin(0.55n)（3）x3(n)=2|n|R21(n+10)解：求解本题的程序为ex327.m，程序运行结果如题27*解图所示。本题选择变换区间长度N的方法如下：,对x1(n)，其周期为10，所以取N1=10；因为x2(n)=sin(0.45n)sin(0.55n)=0.5cos(0.1n)cos(n)，其周期为20，所以取N2=20；x3(n)不是因果序列，所以先构造其周期延拓序列（延拓周期为N3），再对其主值序列进行N3点DFT。x1(n)和x2(n)是周期序列，所以截取1个周期，用DFT进行谱分析，得出精确的离散谱。x3(n)是非因果、非周期序列，通过试验选取合适的DFT变换区间长度N3进行谱分析。,题27*解图,x1(n)的频谱如题27*解图(a)和(b)所示，x2(n)的频谱如题27*解图(c)和(d)所示。用32点DFT对x3(n)的谱分析结果见题27*解图(e)、(f)和(g)，用64点DFT对x3(n)的谱分析结果见题27*解图(h)、(i)和(j)。比较可知，仅用32点分析结果就可以了。请注意，x3(n)的相频特性曲线的幅度很小，这是计算误差引起的。实质上，x3(n)是一个实偶对称序列，所以其理论频谱应当是一个实偶函数，其相位应当是零。,程序ex327.m如下：%程序ex327.m%用DFT对序列谱分析n1=0：9；n2=0：50；n3=-10：10；N1=10；N2=20；N3a=32；N3b=64；x1n=2*cos(0.2*pi*n1)；%计算序列x1nx2n=2*sin(0.45*pi*n2).*sin(0.55*pi*n2)；%计算序列x2nx3n=0.5.abs(n3)；%计算序列x3nx3anp=zeros(1，N3a)；%构造x3n的周期延拓序列，周期为N3aform=1：10，,x3anp(m)=x3n(m+10)；x3anp(N3a+1-m)=x3n(11m)；endx3bnp=zeros(1，N3b)；%构造x3n的周期延拓序列，周期为N3bform=1：10，x3bnp(m)=x3n(m+10)；x3bnp(N3b+1m)=x3n(11m)；endX1k=fft(x1n，N1)；%计算序列x1n的N1点DFTX2k=fft(x2n，N2)；%计算序列x2n的N2点DFTX3ak=fft(x3anp，N3a)；%计算序列x3n的N3a点DFTX3bk=fft(x3bnp，N3b)；%计算序列x3n的N3b点DFT%以下为绘图部分（省略）,3.6教材第4章习题与上机题解答快速傅里叶变换（FFT）是DFT的快速算法，没有新的物理概念。FFT的基本思想和方法教材中都有详细的叙述，所以只给出教材第4章的习题与上机题解答。1如果某通用单片计算机的速度为平均每次复数乘需要4s，每次复数加需要1s，用来计算N=1024点DFT，问直接计算需要多少时间。用FFT计算呢？照这样计算，用FFT进行快速卷积对信号进行处理时，估计可实现实时处理的信号最高频率。,解:当N=1024=210时，直接计算DFT的复数乘法运算次数为N2=10241024=1048576次复数加法运算次数为N（N1）=10241023=1047552次直接计算所用计算时间TD为TD=410610242+1047552106=5.241856s用FFT计算1024点DFT所需计算时间TF为,快速卷积时，需要计算一次N点FFT（考虑到H(k)=DFTh(n)已计算好存入内存）、N次频域复数乘法和一次N点IFFT。所以，计算1024点快速卷积的计算时间Tc约为,所以，每秒钟处理的采样点数（即采样速率）,由采样定理知，可实时处理的信号最高频率为,应当说明，实际实现时，fmax还要小一些。这是由于实际中要求采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分要计算两次。重叠部分长度与h(n)长度有关，而且还有存取数据和指令周期等消耗的时间。2如果将通用单片机换成数字信号处理专用单片机TMS320系列，计算复数乘和复数加各需要10ns。请重复做上题。解:与第1题同理。直接计算1024点DFT所需计算时间TD为TD=1010910242+101091047552=20.96128ms,用FFT计算1024点DFT所需计算时间TF为,快速卷积计算时间Tc约为,可实时处理的信号最高频率fmax为,由此可见，用DSP专用单片机可大大提高信号处理速度。所以，DSP在数字信号处理领域得到广泛应用。机器周期小于1ns的DSP产品已上市，其处理速度更高。,3已知X(k)和Y(k)是两个N点实序列x(n)和y(n)的DFT，希望从X(k)和Y(k)求x(n)和y(n)，为提高运算效率，试设计用一次N点IFFT来完成的算法。解:因为x(n)和y(n)均为实序列，所以，X(k)和Y(n)为共轭对称序列，jY(k)为共轭反对称序列。可令X(k)和jY(k)分别作为复序列F(k)的共轭对称分量和共轭反对称分量，即F(k)=X(k)+jY(k)=Fep(k)+Fop(k)计算一次N点IFFT得到f(n)=IFFTF(k)=Ref(n)+jImf(n),由DFT的共轭对称性可知Ref(n)=IDFTFep(k)=IDFTX(k)=x(n)jImf(n)=IDFTFop(k)=IDFTjY(k)=jy(n)故,4设x(n)是长度为2N的有限长实序列，X(k)为x(n)的2N点DFT。(1)试设计用一次N点FFT完成计算X(k)的高效算法。(2)若已知X(k)，试设计用一次N点IFFT实现求X(k)的2N点IDFT运算。,解:本题的解题思路就是DIT-FFT思想。（1）在时域分别抽取偶数和奇数点x(n)，得到两个N点实序列x1(n)和x2(n)：x1(n)=x(2n)n=0,1,N1x2(n)=x(2n+1)n=0,1,N1根据DIT-FFT的思想，只要求得x1(n)和x2(n)的N点DFT，再经过简单的一级蝶形运算就可得到x(n)的2N点DFT。因为x1(n)和x2(n)均为实序列，所以根据DFT的共轭对称性，可用一次N点FFT求得X1(k)和X2(k)。具体方法如下：,令y(n)=x1(n)+jx2(n)Y(k)=DFTy(n)k=0,1,N1则,2N点DFTx（n）=X（k）可由X1(k)和X2(k)得到,这样，通过一次N点IFFT计算就完成了计算2N点DFT。当然还要进行由Y(k)求X1(k)、X2(k)和X(k)的运算(运算量相对很少)。（2）与（1）相同，设x1(n)=x(2n)n=0,1,N1x2(n)=x(2n+1)n=0,1,N1X1(k)=DFTx1(