数字信号处理参考试题4

第四章 快速傅里叶变换

1． 如果一台通用计算机的速度为平均每次复乘5μs，每次复加0.5μs，用它来计算512

点的的DFT［x(n)］，问直接计算需要多少时间，用FFT运算需要多少时间。

解：

（1）直接计算 复乘所需时间

T1?5?10?6?N2?5?10?6?5122?1.31072s 复加所需时间

T2?0.5?10?6?N?(N?1)?0.5?10?6?512?(512?1)?0.130816s

所以 T?T1?T2?1.441536s （2）用FFT计算 复乘所需时间 T1?5?10复加所需时间

?6?N512log2N?5?10?6??log2512?0.01152s 22T2?0.5?10?6?Nlog2N?0.5?10?6?512?log2512?0.002304s

所以 T?T1?T2?0.013824s

Y(k)是两个N点实序列x(n)，y(n)的DFT值，Y(k)2． 已知X(k)，仅需要从X(k)，

求x(n)，y(n)的值，为了提高运算效率，试用一个N点IFFT运算一次完成。

解：

依据题意 x(n)?X(k)，y(n)?Y(k) 取序列 Z(k)?X(k)?jY(k) 对Z(k)作N点IFFT可得序列z(n)。 又根据DFT性质

IDFT[X(k)?jY(k)]?IDFT[X(k)]?jIDFT[Y(k)]?x(n)?jy(n)

由原题可知，x(n)，y(n)都是实序列。再根据z(n)?x(n)?jy(n)，可得

x(n)?Re[z(n)]

y(n)?Im[z(n)]3． N＝16时，画出基-2按时间抽取法及按频率抽取法的FFT流图（时间抽取采用输入

倒位序，输出自然数顺序，频率抽取采用输入自然顺序，输出倒位序）。

解：

（1）按时间抽取，见图P4-3(a)。

图 P4-3（a）

（2）按频率抽取，见图P4-3(b)。

图 P4-3（b）

4． N=16时，导出基-4FFT公式、画出流图，并就运算量与基-2的FFT相比较（不计

乘±1及乘±j的运算量）。

解：

依题意 N＝4×4＝r1r2 对于n

?n?0,1,2,3n?n1r2?n0,?1

n?0,1,2,3?2 同样令N=r1r2，对于频率变量k(k

?k?0,1,2,3 k?k1r1?k0,?1?k0?0,1,2,3可得 x(n)?x(n1r2?n0)?x(4n1?n0)?x(n1,n0)

X(k)?X(k1r1?k0)?X(4k1?k0)?X(k1,k0)

根据上式

X(k)??x(n)Wn?015nk16?n0?0n1?0(4n1?n0)(4k1?k0)x(4n?n)W??101633?n0?0n1?0??x(4n3314n1k04n1k0n0k0?n0)W16W16W16??n0k0???3?4n0k14n1k0?????x(4n1?n0)W16?W16?W16?n0?0????n1?0?3

令 X1(k0,n0)?'n1?0?x(n,n)W103n1k04,k0?0,1,2,3

则 X1(k0,n0)?X1(k0,n0)W1600 而 X2(k0,k1)?nkn1?0?X3'1(k0,n0)W4n0k1,k1?0,1,2,3

所以 X(k)?X(k1,k0)?X2(k0,k1)?X2(4k1?k0) 计算量比较：

基-4：只在乘旋转因子时有复乘，复乘8次；复加64次。 基-2：复乘10次，复加64次。 基-4流图如图P4-4所示。

图 P4-4

5． 试用N的组合数时的FFT算法求N=12的结果（采用基-3×4），并画出流图。 解：依题意 N?3?4?r1r2 对于0?n?N，有

n?r1r2?n0,??n1?0,1,2

?n0?0,1,2,3同样 令N?r1r2，对于频率变量k(0?k?N)有 k?k1r1?k0,?可得

x(n)?x(n1r2?n0)?x(4n1?n0)?x(n1,n0)

?k1?0,1,2,3

?k0?0,1,2,X(k)?X(k1r1?k0)?X(4k1?k0)?X(k1,k0)

根据上式，得

X(k)??x(n)Wn?03211nk12?n0?0n1?0??x(n,n)W10332(4n1?n0)(3k1?k0)12?n0?0n1?04n1k03n1k0n0k0x(n,n)WWW??10121212??n0k0???2?n0k1?????x(n1,n0)W3n1k0?W12?W4?n0?0????n1?0?

流图如图P4-5所示。最后输出为x(k0,k1)，是倒位序的，按k?3k1?k0可算出其相应的k值，在整序后，即可得正常顺序的输出。

图 P4-5

6． 同上题。导出N?30?3?2?5的结果，并画出流图。 解：依题意 N?3?2?5?r1r2r3 对于n

?n2?0,1,2? n?n2r2r3?n1r3?n0?10n2?5n1?n0,?n1?0,1

?n?0,1,2,3,4?0同样，令N?r1r2r3，对于频率变量k(0?k?30)有

?k2?0,1,2,3,4? k?k2r2r1?k1r1?k0?6k2?3k1?k0,?k1?0,1

?k?0,1,2?0可得 x(n)?x(10n2?5n1?n0)?x(n2,n1,n0)

X(k)?X(6k2?3k1?k0)?X(k2,k1,k0)

根据上式得 X(k)??x(n)Wn?021429nk30?n2?0n1?0n0?0???x(n,n,n)W2101010n2k030214(10n2?5n1?n0)(6k2?3k1?k0)30

?n2?0n1?0n0?0???x(n,n,n)W25n1k06n0k23n0k1n0k015n1k1 W30W30?W30W30W30

百度搜索“yundocx”或“云文档网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，云文档网，提供经典综合文库数字信号处理参考试题4在线全文阅读。