第三章 离散傅里叶变换及其快速算法习题答案参考3.1 图P3.1所示的序列()x n %是周期为4的周期性序列。

请确定其傅里叶级数的系数()Xk %。

解：(1)11*0()()()()()()N N N nk nk nk N N N n n n X k x n W x n W x n W X k X k -----=====-==-=∑∑∑%%%%%%3.2 （1）设()x n %为实周期序列，证明()x n %的傅里叶级数()Xk %是共轭对称的，即*()()X k X k =-%。

（2）证明当()x n %为实偶函数时，()Xk %也是实偶函数。

证明：（1）1011**()()()[()]()()N nk Nn N N nk nkNNn n X k x n W X k x n Wx n WX k --=---==-=-===∑∑∑%%%%%%（2）因()x n %为实函数，故由（1）知有 *()()Xk X k =-%或*()()X k X k -=% 又因()x n %为偶函数，即()()xn x n =-%%，所以有(1)11*0()()()()()()N N N nk nk nk N N N n n n X k x n W x n W x n W X k X k -----=====-==-=∑∑∑%%%%%%3.3 图P3.3所示的是一个实数周期信号()x n %。

利用DFS 的特性及3.2题的结果，不直接计算其傅里叶级数的系数()Xk %，确定以下式子是否正确。

（1）()(10)Xk X k =+%%，对于所有的k ； （2）()()Xk X k =-%%，对于所有的k ； （3）(0)0X=%；（4）25 ()jkX k eπ%，对所有的k是实函数。

解：（1）正确。

因为()x n%一个周期为N＝10的周期序列，故()X k%也是一个周期为N＝10的周期序列。

（2）不正确。

因为()x n%一个实数周期序列，由例3.2中的（1）知，()X k%是共轭对称的，即应有*()()X k X k=-%，这里()X k%不一定是实数序列。

（3）正确。

因为()x n%在一个周期内正取样值的个数与负取样值的个数相等，所以有1(0)()0NnX x n-===∑%%（4）不正确。

根据周期序列的移位性质，25()jkX k eπ%＝210()kX k W-%对应与周期序列(2)x n+%，如图P3.3_1所示，它不是实偶序列。

由题3.2中的（2）知道，25()jkX k eπ%不是实偶序列。

3.4设3()()x n R n=，()(6)rx n x n r∞=-∞=+∑%，求()X k%，并作图表示()x n%和()X k%。

解：3152666000633111(1) ()()()111k j k k Nnk nk nkN kj k j k n n nW eX k x n W x n W WWe eπππ----===----======---∑∑∑%%%(0)1(2)(4)0(1)131(13)/22(3)11(5)131(13)j XXX X j j X e Xj j π-=====---==-==+-+%%%%%% ()x n %和()Xk %的图形如图3.4_1所示：3.5 在图P3.5中表示了两个周期序列1()x n %和2()x n %，两者的周期都为6，计算这两个序列的周期卷积3()x n %，并图表示。

解：图P3.5_1所示的是计算这两个序列的周期卷积3()x n %的过程，可以看出，3()x n %是1()x n %延时1的结果，即31()(1)x n x n =-%%。

3.5 计算下列序列的N 点DFT ：(1)()()x n n δ=(2)00()[()]*(),0N N x n n n R n n N δ=-<< (3)(),01nx n a n N =≤≤- (4)2()cos(),01,x n nm n N o m N Nπ=≤≤-<< 解：（1）10()()(0)1,01N nkN n X k n W k N δδ-====≤≤-∑ （2）0100()[()](),01N n k nkN N N N n X k n n R n W W k N δ-==-=≤≤-∑（3）111(),0111N Nk N N n nkN Nk kn N Na W a X ka W k N aW aW -=--===≤≤---∑ （4）22211002()2()22()()1()()()(()()()21()cos()211121112N N j nm j nm j nk nk NN N N n n j k m j k m j k m j k m N N N j k m j k m j k m j k m j k m N j k m j k m NN X k nm W e e eN e e ee e e e e e ee πππππππππππππππ----==---+---++---+-+-----⎛⎫==+ ⎪⎝⎭⎛⎫-- ⎪=+ ⎪--⎝⎭--=+-∑∑()()()(){1)()()()11()(),20,sin sin 12sin /sin /N j k m N j k m j k m N N N N j k m j k m N N Nk m k m e e e k m k m e e k m N k m N πππππππππ+-++-+++---+==-⎛⎫ ⎪ ⎪-⎝⎭⎧⎫-+⎡⎤⎡⎤⎪⎪⎣⎦⎣⎦=+⎨⎬-+⎡⎤⎡⎤⎪⎪⎣⎦⎣⎦⎩⎭=或其他3.7 图P3.7表示的是一个有限长序列()x n ,画出1()x n 和2()x n 的图形。

（1）()144()2()x n x n R n =-⎡⎤⎣⎦（2）()244()2()x n x n R n =-⎡⎤⎣⎦解：1()x n 和2()x n 的图形如图P3.7_1所示：3.8 图P3.8表示一个4点序列()x n 。

（1）绘出()x n 与()x n 的线性卷积结果的图形。

（2）绘出()x n 与()x n 的4点循环卷积结果的图形。

（3）绘出()x n 与()x n 的8点循环卷积结果的图形，并将结果与（1）比较，说明线性卷积与循环卷积之间的关系。

解：（1）图P3.8_1（1）所示的是()x n 与()x n 的线性卷积结果的图形。

（2）图P3.8_1（2）所示的()x n 与()x n 的4点循环卷积结果的图形。

（3）图P3.8_1（3）所示的()x n 与()x n 的8点循环卷积结果的图形。

可以看出，()x n 与()x n 的8点循环卷积结果的图形与（1）中()x n 与()x n 的线性卷积结果的图形相同。

3.9 ()x n 是一个长度为N 的序列，试证明[()][()]N N x n x N n -=-。

证明：因为[()]N x n -是由()x n 周期性重复得到的周期序列，故可表示为[()][()]N N x n x n rN -=-+ 取r ＝1，上式即为[()][()]N N x n x N n -=-。

3.10 已知序列()(),01nx n a u n a =<<。

现在对其Z 变换在单位圆上进行N 等分取样，取值为()()|k Nz W X k X z -==，求有限长序列的IDFT 。

解：在z 平面的单位圆上的N 个等角点上，对z 变换进行取样，将导致相应时间序列的周期延拓，延拓周期为N ，即所求有限长序列的IDFT 为 ()()(),0,1, (11)n rNp Nr r a x n x n rN au n rN n N a∞∞+=-∞=-∞=+=+==--∑∑ 3.11 若长为N 的有限长序列()x n 是矩阵序列()()N x n R n =。

（1）求[()]x n Z ，并画出及其-零点分布图。

（2）求频谱()j X e ω，并画出幅度|()|j X e ω的函数曲线。

（3）求()x n 的DFT 的闭式表示，并与()j X e ω对照。

解：（1）11021111111111()()1()()()1(1)(1)N N nnNn n N N N j k k k NN NNk k k N N N N z X z Rn zzz z W z W z e z z z z z z zπ-∞----=-∞=-----===-----===-∏-∏-∏--====--∑∑极点：00(1)z N =-阶；零点：2,1,2,...,1j k Npk z e k N π==-图P3.11_1(1)是极-零点分布图。

（2）12222111222sin 1()2()()|1sin()2j N N N jjjN j N j j j z e j j j N e e e eX e X z ee e e e ωωωωωωωωωωωωω------=--⎛⎫⎪--⎝⎭====--sin 12|()|,()2sin 2j N N X e ωωϕωωω⎛⎫⎪-⎝⎭==-图P3.11_1(2)所示的是频谱幅度|()|j X e ω的函数曲线。

（3）{21,020,1,2,...,12011()()()11Nk j k N nk j N k N N Nk N k k j k n NN NW e X k R n WX e W e πωππω--==-=-=--=====--∑可见，()X k 等于()j X e ω在N 个等隔频率点2(0,1,2,...,1)k N Nπω==-上的取样值。

3.12 在图P3.12中画出了有限长序列()x n ，试画出序列4[()]x n -的略图。

解：3.13 有限长序列的离散傅里叶变换相当与其Z 变换在单位圆上的取样。

例如10点序列()x n 的离散傅里叶变换相当与()X z 在单位圆10个等分点上的取样，如图P3.13（a ）所示。

为求出图P3.13（b ）所示圆周上()X z 的等间隔取样，即()X z 在[(2/10)(/10)]0.5j k z eππ+=各点上的取样，试指出如何修改()x n ，才能得到序列1()x n ，使其傅里叶变换相当于上述Z 变换的取样。

解：22991010102110.5exp 101000()()()()(0.5)j nk jn jnk n z j k n n X k x n eX z x n eeπππππ----⎡⎤⎛⎫=+ ⎪⎢⎥⎝⎭⎣⎦=====∑∑由上式得到101()(0.5)()jnnx n ex n π--=3.14 如果一台通用计算机计算一次复数乘法需要100s μ，计算一次复数加法需要20s μ，现在用它来计算N ＝1024点的DFT ，问直接计算DFT 和用FFT 计算DFT 各需要多少时间？ 解：直接计算DFT ：复数乘法：22102410485761048576100105N s s μ==⨯≈次，复数加法：(1)102410231047552,10475522021N N s s μ-=⨯=⨯≈次 总计需要时间：(10521)126s s +=用FFT 计算DFT ： 复数乘法：2log 5120,51201000.5122NN s s μ=⨯≈次 复数加法：2log 10240,10240200.2048N N s s μ=⨯≈次 总计需要时间：(0.5120.2048)0.7168s s +=3.15 仿照本教材中的图3.15，画出通过计算两个8点DFT 的办法来完成一个16点DFT 计算的流程图。