设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点实序列x 1 (n)和x 2 (n)：x 1 (n)=x(2n) n=01…N-1 x 2 (n)=x(2n+1) n=01…N-1根据DIT-FFT的思想只要求得x 1 (n)和x 2 (n)的N点DFT再经过简单的一级蝶形运算就可得到x(n)的2N点DFT。因为x 1 (n)和x 2 (n)均为实序列所以根据DFT的共轭对称性可用一次N点FFT求得X 1 (k)和X 2 (k)。具体方法如下： 令 y(n)=x 1 (n)+jx 2 (n) Y(k)=DFT[y(n)] k=01…N-1则X 1 (k)-DFT[x 1 (n)]=Y ep (k)=1/2[Y(k)+Y * (N-k)] jX 2 (k)=DFT[jx 2 (n)]=Y op (k)=1/2[Y(k)-Y * (N-k)] 2N点DFT[x(n)]=X(k)可由X 1 (k)和X 2 (k)得到 这样通过一次N点IFFT计算就完成了计算2N点DFT。当然还要进行由Y(k)求X 1 (k)、X 2 (k)和X(k)的运算(运算量相对很少)。 (2)与(1)相同设 解：本题的解题思路就是DIT-FFT思想。(1)在时域分别抽取偶数和奇数点x(n),得到两个N点实序列x1(n)和x2(n)：x1(n)=x(2n)n=0,1,…,N-1x2(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则X1(k)-DFT[x1(n)]=Yep(k)=1/2[Y(k)+Y*(N-k)]jX2(k)=DFT[jx2(n)]=Yop(k)=1/2[Y(k)-Y*(N-k)]2N点DFT[x(n)]=X(k)可由X1(k)和X2(k)得到这样,通过一次N点IFFT计算就完成了计算2N点DFT。当然还要进行由Y(k)求X1(k)、X2(k)和X(k)的运算(运算量相对很少)。(2)与(1)相同,设