搜索
教材第4444章习题与上机题解答 快速傅里叶变换（FFT）是DFT的快速算法，没有新的物理概念。FFT的基本思想和方法教材中都有详细的叙述，所以只给出教材第4章的习题与上机题解答。 1．如果某通用单片计算机的速度为平均每次复数乘需要4μs，每次复数加需要1μs，用来计算N=1024点DFT，问直接计算需要多少时间。用FFT计算呢？照这样计算，用FFT进行快速卷积对信号进行处理时，估计可实现实时处理的信号最高频率。 解:当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为66F66510lblb10210245101010241010230.72msNTNNN−−−−=××+×=×××+××= 快速卷积时，需要计算一次N点FFT（考虑到H(k)=DFT［h(n)］已计算好存入内存）、N次频域复数乘法和一次N点IFFT。所以，计算1024点快速卷积的计算时间Tc约为cF2102471680μs41024μs65536μsTT=+=+×=次复数乘计算时间所以，每秒钟处理的采样点数（即采样速率）s6102415625/6553610F−=×次秒由采样定理知，可实时处理的信号最高频率为smax156257.8125kHz22Ff== 应当说明，实际实现时，fmax还要小一些。这是由于实际中要求采样频率高于奈奎斯特速率，而且在采用重叠相加法时，重叠部分要计算两次。重叠部分长度与h(n)长度有关，而且还有存取数据和指令周期等消耗的时间。 2．如果将通用单片机换成数字信号处理专用单片机TMS320系列，计算复数乘和复数加各需要10ns。请重复做上题。 解:与第1题同理。 直接计算1024点DFT所需计算时间TD为TD=10×10－9×10242+10×10－9×1047552=20.96128ms用FFT计算1024点DFT所需计算时间TF为99F881010lb1010lb2102410101010241020.1536msNTNNN−−−−=××+××=××+××=快速卷积计算时间Tc约为cF392102420.153610101010240.31744msTT−−=+=××+××=次复数乘计算时间可实时处理的信号最高频率fmax为maxsc1110241=3.1158MHz=1.6129MHz222fFT=≤··由此可见，用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)=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)故1()[()()]2xnfnfn∗=+1()[()()]2jynfnfn∗=− 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,…,N－1 x2(n)=x(2n+1)n=0,1,…,N－1 根据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则*11ep*22ep1()DFT[()]()[()()]21j()DFT[j()]()[()()]2XkxnYkYkYNkXkxnYkYkYNk===+−===−−2N点DFT［x（n）］=X（k）可由X1(k)和X2(k)得到122122()()()0,1,,1()()()kNkNXkXkWXkkNXkNXkWXk⎫=+⎪=−⎬+=−⎪⎭L 这样，通过一次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则应满足关系式122122()()()0,1,,1()()()kNkNXkXkWXkkNXkNXkWXk⎫=+⎪=−⎬+=−⎪⎭L由上式可解出1221()[()()]20,1,2,,11()[()()]2kNXkXkXkNkNXkXkXkNW−⎫=++⎪⎪=−⎬⎪=++⎪⎭L由以上分析可得出运算过程如下： ①由X(k)计算出X1(k)和X2(k):1221()[()()]21()[()()]2kNXkXkXkNXkXkXkNW−=++=++ ②由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的共轭对称性知*ep1*op21Re[()][()()]DFT[()]()21jIm[()][()()]DFT[()]j()2ynynynYkxnynynynYkxn=+===+== ③由x1(n)和x2(n)合成x(n):122()12nxnxnnxn⎧⎛⎞=⎜⎟⎪⎪⎝⎠=⎨−⎛⎞⎪=⎜⎟⎪⎝⎠⎩偶数奇数，0≤n≤2N－1在编程序实现时，只要将存放x1(n)和x2(n)的两个数组的元素分别依次放入存放x(n)的数组的偶数和奇数数组元素中即可。 5．分别画出16点基2DIT-FFT和DIF-FFT运算流图，并计算其复数乘次数，如果考虑三类碟形的乘法计算， 试计算复乘次数。 解：本题比较简单，仿照教材中的8点基2DIT-FFT和DIF-FFT运算流图很容易画出16点基2DIT-FFT和DIF-FFT运算流图。但画图占篇幅较大，这里省略本题解答，请读者自己完成。 6*．按照下面的IDFT算法编写MATLAB语言IFFT程序，其中的FFT部分不用写出清单，可调用fft函数。并分别对单位脉冲序列、矩形序列、三角序列和正弦序列进行FFT和IFFT变换，验证所编程序。**1()IDFT[()][DFT[()]]xnXkXkN== 解：为了使用灵活方便，将本题所给算法公式作为函数编写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 %调用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