X[m?NNmm]?(1?WN)X1[m]?(1?WN)X2[m],0?m??1 22现在需要由X(k)X(k)的各个数值(k?0,1,...,2N?1)，
3.已知长度为2N的实序列x(n)的DFT
计算x(n)，为了提高效率，请设计用一次N点IFFT来完成。 解：如果将x(n)按奇偶分为两组，即令
u(n)?x(2n)??v(n)?x(2n?1)?那么就有
n?0,1,2,?,N?1
X(k)?U(k)?W2kNV(k)??X(k?N)?U(k)?W2kNV(k)?
k?0,1,2,?,N?1
其中U(k)、V(k)分别是实序列u(n)、v(n)的N点DFT，U(k)、V(k)可以由上式解出
1?X(k)?X(k?N)???2?1?kV(k)?W2N?X(k)?X(k?N)??2?U(k)?由于
就得到了U(k)和V(k)。令
k?0,1,2,?,N?1
X(k)(k?0,1,...,2N?1)是已知的，因此可以将X(k)前后分半按上式那样组合起来，于是
y(n)?u(n)?jv(n)
根据U(k)、V(k)，做一次N点IFFT运算，就可以同时得到u(n)和v(n)(n?0,1,...,N?1)
它们分别是x(n)的偶数点和奇数点序列，于是序列x(n)(n?0,1,...,2N?1)也就求出了。
4-7 采用FFT算法，可用快速卷积完成线性卷积。现预计算线性卷积x(n)?h(n)，试写采用快速卷积的计算步骤（注意说明点数）。
答：如果x(n)，h(n)的长度分别为N1,N2,那么用长度N?N1?N2??1的圆周卷积可计算线性卷
积。用FFT运算来求x(n)?h(n)值（快速卷积）的步骤如下：
（1） 对序列x(n)，h(n)补零至长为N，使N整数)，即
?N1?N2??1，并且N?2M(M为
n?0,1,...N1?1?x(n)x(n)??
n?N1,N1?1,...N?1?0n?0,1,...,N2?1?h(n)h(n)??
0n?N,N?1,...,N?122?（2） 用FFT计算x(n)，h(n)的离散傅立叶变换
x(n)?FFT???X(k) （N点） h(n)?FFT???H(k) （N点）
（3） 计算Y(k)?X(k)H(k)
（4） 用IFFT计算Y(k)的离散傅立叶变换得：
x(n)?h(n)?IFFT[Y(k)] （N点）
4-8试推导时域抽取基-2 FFT算法，并画出8点的FFT计算流图。 解：
nkX?k???x?n?WNn?0N?1
N2?1??x?2r?Wr?0N2?12rkN??x?2r?1?W?r?0N2?1kN2r?1?kN
N2?1??x?2r??W?r?0rkN22rkN?W?x?2r?1??W?r?0rkN22rkN
N2?1??x?2r?Wr?0N2?1?WkN?x?2r?1?Wr?0
k?G?k??WNH?k?
其中
N2?1?rk?G?k???x?2r?WN2?r?0 ?N2?1?H?k??x?2r?1?WNrk2??r?0?G?k?和H?k?分别是x?2r?和x?2r?1?的
所以：
N2点的DFT，周期为
N2。
?N??N?G??k??G?k?，H??k??H?k? ?2??2??WNN2?k?又因为：
?e?j2??N???k?N?2?k ??WNNk?N?N?N????kX?k???G?k???WN2H?k???G?k??WNH?k?
222??????所以
????X?X?k??G?k??WNkH?k?N?N?N????kk??Gk??WHk?N???2?2?2???????，k?0,1,?,N?1 28点的FFT计算流图见教材。