复旦大学：《数字信号处理》课程教学资源_第六章 FFT习题解答

第四章习题 1.N=16时,画出基2时间抽取的FFT流图 X(2 x12 X3] 0 ] 4 如一 X[8] x9) X[LO x[13] +o X[ll] x(3 X12] x —04 →。15 2.设有一个离散信号x(n)=[2,-1,1,1] (1)直接计算4点DFT (2)利用基2频率抽选信号流图,计算X[k]=DFT{x(n)}与DFTX[k]}, 并在每个节点上标注每一级计算结果 解: (1)由DFT的定义有: x(k)=∑x(nW 而W4=eN=e-2 H W4=jW4=W。=1

1 第四章习题 1. N=16 时，画出基 2 时间抽取的 FFT 流图 2.设有一个离散信号 x(n)=[2,-1,1,1] (1) 直接计算 4 点 DFT (2) 利用基2 频率抽选信号流图，计算X[k]=DFT{x(n)}与 DFT{X* [k]}, 并在每个节点上标注每一级计算结果

X(0)=∑x(m川4 (n)=x(0)+x(1)+x(2)+x(3)=2-1+1+1=3 X(1)=∑x(m形4=∑xny-n)=2+j-1+j=1+2j x(2)=∑x(n)=∑x(n)(-1)=2+1+1-1=3 X(3)=∑xn)=∑x(n))=2-1-1-j=1-2j 故X(k)=[3,1+2j,3,1-2j 3.已经Xk]={10,-2-2j,2,-2+2j},利用基2FFT算法流图计算x(n) 例:已知Xm]={10,-2-2j,-2,-2+2j} 利用基2FFT算法流图计算闪 X[m]={0-2-2,-2,-2+2j} 8 x[0 X0] 2-2j x[1] x2] w A2…···…·相 2+2x[3]● ·X13]16 x[k]=DFT{X[m]}={1,2,3,4} 4 s人墨 4.设x(n)是长度为2N的有限长实序列,(k)为x(m)的2N点DFT (1)试设计用一次M点FFT完成计算X(A)的高效算法。 (2)若已知K(k),试设计用一次N点IFFT实现求K(k)的2N点IDFT 运算

2 3.已经 X[k]={10,-2-2j,-2,-2+2j}，利用基 2FFT 算法流图计算 x(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 运算

解:本题的解题思路就是DⅠI-FFT思想。 (1)在时域分别抽取偶数和奇数点x(m),得到两个N点 实序列x(n)和x2(m) (m)=x(2n) n=0,1,…,-1 (n)=x(2n+1)n=0,1,,N-1 根据DIFT的思想,只要求得x1(m)和x2(n)的N点DFT 再经过简单的一级蝶形运算就可得到x(n)的2N点DFT。因为 x1(m)和x2(m)均为实序列,所以根据DFT的共轭对称性,可用 一次N点FT求得X1(k)和x2(k)。具体方法如下: yn)=x1(n)+ⅸx2(n) YK)=DFT[y(m)]k=0,1,…,N-1 =F0(k)=[(k)+Y(N-k Lr, (R)=DFTLjx, (n)]=I(k)==[Y(k)-Y(N-k)] 2N点DFT[x(n)]=X(k)可由X1(k)和X2(k)得到 I(k)=x1(k)+212(k) x(k+N)=x1(k)-2x2(k) 这样,通过一次N点IFT计算就完成了计算2N点DFT 当然还要进行由Y(k)求H1(k)、2(k)和Y(k)的运算(运算量相对 很少)。 (2)与(1)相同,设 x1(n)=x(2 1,…,N x1(k)=DFT[x(m)]k=0.1,…,N-1 X2(k)=DFT[x2(m)]k=0,1,…,N-1 则应满足关系式 (k)=1(k)+数I2(k) k=0,1,…,N-1 (k+N)=X1(k)-2xX2(k)

3

由上式可解出 21(k)=[X(k)+X(k+N) k=0,1,2,…,N-1 2(k)==[X(k)+X(k+N)2x 由以上分析可得出运算过程如下 ①由X(k)计算出X(k)和×2(k) xX1(k)==[X(k)+X(k+N) x2(k)=[(k)+(k+N)2x ②由X1(k)和X2(k)构成N点频域序列Yk) Y(k)=×1(k)+×2(k)=Yep(k)+Yop(k) 其中,Y()=X(,Yp()=(,进行N点FFT,得到 y(n)=IFFT [Y(k)] =Re [yn)]+j Im [y(n)] n=0, 1,,N-1 由DFT的共轭对称性知 Rely(n]=Ly(n)+y(n)]=DFT[Ye (k)]=x(n) jIm[v(n)]=Ly(n)+y(n)=DFTIY(h)=jx2(n) ③由x1(n)和x2(m)合成x(n) n=偶数 x(n) 17 =奇数 在编程序实现时,只要将存放x1(m)和x2(m)的两个数组的元素分别依次放入存 放x(n)的数组的偶数和奇数数组元素中即可

4