课后习题及答案-第4章快速傅里叶变换--习题答案

1第4章快速傅里叶变换（FFT）习题答案1.解解解解:当N=1024=210时，直接计算DFT的复数乘法运算次数为N2=1024×1024=1048576次复数加法运算次数为N（N－1）=1024×1023=1047552次直接计算所用计算时间TD为TD=4×10－6×10242+1047552×10－6=5.241856s用FFT计算1024点DFT所需计算时间TF为快速卷积时，需要计算一次N点FFT（考虑到H(k)=DFT［h(n)］已计算好存入内存）、N次频域复数乘法和一次N点IFFT。所以，计算1024点快速卷积的计算时间Tc约为所以，每秒钟处理的采样点数（即采样速率）由采样定理知，可实时处理的信号最高频率为应当说明，实际实现时，fmax还要小一些。这是由于实际中要求采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分要计算两次。重叠部分长度与h(n)长度有关，而且还有存取数据和指令周期等消耗的时间。2.解解解解:与第1题同理。直接计算1024点DFT所需计算时间TD为66F66510lblb10210245101010241010230.72msNTNNN----=××+×=×××+××=cF2102471680μs41024μs65536μsTT=+=+×=次复数乘计算时间s6102415625/6553610F-=×次秒smax156257.8125kHz22Ff==2TD=10×10－9×10242+10×10－9×1047552=20.96128ms用FFT计算1024点DFT所需计算时间TF为快速卷积计算时间Tc约为可实时处理的信号最高频率fmax为≤··由此可见，用DSP专用单片机可大大提高信号处理速度。所以，DSP在数字信号处理领域得到广泛应用。机器周期小于1ns的DSP产品已上市，其处理速度更高。3.解解解解:因为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)=IFFT［F(k)］=Re［f(n)］+jIm［f(n)］由DFT的共轭对称性可知Re［f(n)］=IDFT［Fep(k)］=IDFT［X(k)］=x(n)jIm［f(n)］=IDFT［Fop(k)］=IDFT［jY(k)］=jy(n)故4.解解解解:本题的解题思路就是DIT-FFT思想。（1）在时域分别抽取偶数和奇数点x(n)，得到两个N点实序列x1(n)和x2(n)：x1(n)=x(2n)n=0,1,…,N－1x2(n)=x(2n+1)n=0,1,…,N－199F881010lb1010lb2102410101010241020.1536msNTNNN----=××+××=××+××=cF392102420.153610101010240.31744msTT--=+=××+××=次复数乘计算时间maxsc1110241=3.1158MHz=1.6129MHz222fFT=1()[()()]2xnfnfn*=+1()[()()]2jynfnfn*=-3根据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)=DFT［y(n)］k=0,1,…,N－1则2N点DFT［x（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,…,N－1x2(n)=x(2n+1)n=0,1,…,N－1X1(k)=DFT［x1(n)］k=0,1,…,N－1X2(k)=DFT［x2(n)］k=0,1,…,N－1则应满足关系式由上式可解出由以上分析可得出运算过程如下：（1）由X(k)计算出X1(k)和X2(k):*11ep*22ep1()DFT[()]()[()()]21j()DFT[j()]()[()()]2XkxnYkYkYNkXkxnYkYkYNk===+-===--122122()()()0,1,,1()()()kNkNXkXkWXkkNXkNXkWXk=+=-+=-L122122()()()0,1,,1()()()kNkNXkXkWXkkNXkNXkWXk=+=-+=-L1221()[()()]20,1,2,,11()[()()]2kNXkXkXkNkNXkXkXkNW-=++=-=++L4②由X1(k)和X2(k)构成N点频域序列Y(k):Y(k)=X1(k)+jX2(k)=Yep(k)+Yop(k)其中，Yep(k)=X1(k),Yop(k)=jX2(k)，进行N点IFFT，得到y(n)=IFFT［Y(k)］=Re［y(n)］+jIm［y(n)］n=0,1,…,N－1由DFT的共轭对称性知③由x1(n)和x2(n)合成x(n):，0≤n≤2N－1在编程序实现时，只要将存放x1(n)和x2(n)的两个数组的元素分别依次放入存放x(n)的数组的偶数和奇数数组元素中即可。5.解解解解：本题比较简单，仿照教材中的8点基2DIT-FFT和DIF-FFT运算流图很容易画出16点基2DIT-FFT和DIF-FFT运算流图。但画图占篇幅较大，这里省略本题解答，请读者自己完成。6.解解解解：为了使用灵活方便，将本题所给算法公式作为函数编写ifft46.m如下：%函数ifft46.m%按照所给算法公式计算IFETfunctionxn=ifft46(Xk，N)Xk=conj(Xk)；%对Xk取复共轭xn=conj(fft(Xk，N))/N；%按照所给算法公式计算IFFT分别对单位脉冲序列、长度为8的矩形序列和三角序列进行FFT，并调用函数ifft46计算IFFT变换，验证函数ifft46的程序ex406.m如下：%程序ex406.m1221()[()()]21()[()()]2kNXkXkXkNXkXkXkNW-=++=++*ep1*op21Re[()][()()]DFT[()]()21jIm[()][()()]DFT[()]j()2ynynynYkxnynynynYkxn=+===+==122()12nxnxnnxn==-=偶数奇数5%调用fft函数计算IDFTx1n=1；%输入单位脉冲序列x1nx2n=［11111111］；%输入矩形序列向量x2nx3n=［12344321］；%输入三角序列序列向量x3nN=8；X1k=fft(x1n，N)；%计算x1n的N点DFTX2k=fft(x2n，N)；%计算x2n的N点DFTX3k=fft(x3n，N)；%计算x3n的N点DFTx1n=ifft46(X1k，N)%调用ifft46函数计算X1k的IDFTx2n=ifft46(X2k，N)%调用ifft46函数计算X2k的IDFTx3n=ifft46(X3k，N)%调用ifft46函数计算X3k的IDFT运行程序输出时域序列如下所示，正是原序列x1n、x2n和x3n。x1n=10000000x2n=11111111x3n=12344321