快速傅里叶变换(FFT)试题

x(0)x(2)G(0)x(4)x(6)x(1)x(3)x(5)4点DFTG(1)X(0)X(1)G(2)G(3)H(0)W80X(2)X(3)?1?14点H(2)W82DFT3H(3)W8H(1)W81x(7)2.

?1?1X(4)X(5)X(6)X(7)

X[k]是N点序列x(n)的DFT，N为偶数。两个

N2点序列定义为

x1[n]?1(x[2n]?x[2n?1]) 21N(x[2n]?x[2n?1]),0?n??1 22NX1[k]和X2[k]分别表示序列x1[n]和x2[n]的点DFT，试由X1[k]和X2[k]确定x[n]N

2x2[n]?N?12k?0N?1l?0ml2N2点DFT。

解：DFT

?x[2k]???x[2k]W??x[l]L?0N?1mkN2??x[l]W （l为偶数）

1?W1NmlWN?(X[m]?X[m?]) 222N?1l?0m（l?1）2（lN2lN2N DFT

?x[2k?1]???x[2k?1]WNmk??x[l]Wk?02lN2NN?12为奇数）

??x[l]l?0N?1(1?W2)ml?mWNWN?1N?m (X[m]?X[m?]WN22X1[m]?X2[m]?11NN?m?m(1?WN)X[m]?(1?WN)X[m?],0?m??1 442211NN?m?m(1?WN)X[m]?(1?WN)X[m?],0?m??1 4422解上述方程可得

mmX[m]?(1?WN)X1[m]?(1?WN)X2[m],0?m?N?1 2X[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计算流图见教材。