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

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计算流图见教材。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库快速傅里叶变换(FFT)试题(2)在线全文阅读。