第三章 离散傅里叶变换及其快速算法习题答案参考

第三章 离散傅里叶变换及其快速算法习题答案参考

3.1 图P3.1所示的序列x(n)是周期为4的周期性序列。请确定其傅里叶级数的系数X(k)。

N1n0N1n0(N1)解：

X(k)x(n)WnkNx(n)WnkNn0x(n)WNnkX(k)X*(k)

3.2

X(k)X*(k)X(k)x(n)x(n)（1）设为实周期序列，证明的傅里叶级数是共轭对称的，即。

3.3

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

证明：（1）

nkX(k)x(n)WNn0N1X(k)[x(n)W*n0N1nk*Nnk]x(n)WNX(k)n0N1

（2）因x(n)为实函数，故由（1）知有

X(k)X*(k)或

X(k)X*(k)

又因x(n)为偶函数，即x(n)x(n)，所以有

X(k)x(n)WNnkx(n)WNnkn0n0N1N1(N1)n0x(n)WNnkX(k)X*(k)

3.3 图P3.3所示的是一个实数周期信号x(n)。利用DFS的特性及3.2题的结果，不直接计算其傅里叶级数的系数X(k)，确定以下式子是否正确。

（1）X(k)X(k10)，对于所有的k；

（2）X(k)X(k)，对于所有的k；

（3）X(0)0；

25（4）X(k)ejk，对所有的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)在一个周期内正取样值的个数与负取样值的个数相等，所以有

25X(0)x(n)0n0N1

（4）不正确。根据周期序列的移位性质，

X(k)ejk＝

2kX(k)W10对应与周期序列x(n2)，如图P3.3_1

所示，它不是实偶序列。由题3.2中的（2）知道，X(k)ejk25不是实偶序列。

3.4 设

x(n)R3(n)，

x(n)rx(n6r)，求X(k)，并作图表示x(n)和X(k)。

X(k)x(n)W解：

n0N1nkNx(n)Wn05nk6Wn02nk61W63k1ejk1(1)kkjkjk1W61e31e3

X(0)1X(2)X(4)02X(1)1j31(1j3)/22X(3)1j1eX(5)21j31(1j3)

x(n)和X(k)的图形如图3.4_1所示：

3.5 在图P3.5中表示了两个周期序列x1(n)和x2(n)，两者的周期都为6，计算这两个序列的周期卷积x3(n)，并图表示。

解：图P3.5_1所示的是计算这两个序列的周期卷积x3(n)的过程，可以看出，x3(n)是x1(n)延时1的结果，即x3(n)x1(n1)。

3.5 计算下列序列的N点DFT： (1)x(n)(n)

(2)x(n)[(nn0)]N*RN(n),0n0N

nx(n)a,0nN1 (3)

(4)

x(n)cos(2nm),0nN1,omNN

解：（1）

nkX(k)(n)WN(0)1,0kN1n0N1

n0knkX(k)[(nn0)]NRN(n)WNWN,0kN1n0N1（2）

（3）

nkX(k)anWNn0N11aNWNNk1aN,0kN1kk1aWN1aWN

（4）

222N1jnmjnmjnk21X(k)cos(nm)WNnkeNeNeNN2n0n0N1j2(km)j2(km)11e1e22j(km)2jN(km)1eN1eN1N1j(km)j(km)j(km)j(km)j(km)j(km)1eeeeNNeej(km)j(km)2jN(km)jN(km)NNeeeeN1N1sinkmsinkmj(km)j(km)1NNee2sinkm/Nkm/NsinN,km或km20,其他

3.7 图P3.7表示的是一个有限长序列x(n),画出x1(n)和x2(n)的图形。

x1(n)xn24R4(n)（1）

（2）

x2(n)x2n4R4(n)

解：x1(n)和x2(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的序列，试证明x[(n)]Nx[(Nn)]N。

证明：因为x[(n)]N是由x(n)周期性重复得到的周期序列，故可表示为x[(n)]Nx[(nrN)]N

取r＝1，上式即为x[(n)]Nx[(Nn)]N。

nx(n)au(n),0a1。现在对其Z变换在单位圆上进行N等分取样，取值为3.10 已知序列

X(k)X(z)|zWkN，求有限长序列的IDFT。

解：在z平面的单位圆上的N个等角点上，对z变换进行取样，将导致相应时间序列的周期延拓，延拓周期为N，即所求有限长序列的IDFT为

xp(n)rx(nrN)arnrNanu(nrN),n0,1,...,N11aN

3.11 若长为N的有限长序列x(n)是矩阵序列x(n)RN(n)。

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

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

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

解：（1）

X(z)nRN(n)znzn0N1N1n1zN1z1kNN1kNN1j2kN(zW)(zW)(zezN1k0N1N1k1N1k1N1z(z1)z(z1)zz)

极点：z00(N1阶)；零点：zpkej2kN,k1,2,...,N1

图P3.11_1(1)是极-零点分布图。

（2）

1ejNe(eeX(e)X(z)|zej111jjj1eje2(e2e2)jjN2jN2jN2NsinN1)2j2esin2

Nsin2,()N1|X(ej)|2sin2

j|X(e)|的函数曲线。 图P3.11_1(2)所示的是频谱幅度

X(k)RN(n)W（3）

n0N1nkN1WNNk1ej2kjN,k0X(e)20,k1,2,...,N12kkjk1WNN1eN

2(k0,1,2,...,N1)N上的取样值。

可见，X(k)等于X(e)在N个等隔频率点

j

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

解：

3.13 有限长序列的离散傅里叶变换相当与其Z变换在单位圆上的取样。例如10点序列x(n)的离散傅里叶变换相当与X(z)在单位圆10个等分点上的取样，如图P3.13（a）所示。为求出图P3.13（b）所示圆周上X(z)的等间隔取样，即X(z)在z0.5ej[(2k/10)(/10)]各点上的取样，试指出如何修改x(n)，才能

得到序列x1(n)，使其傅里叶变换相当于上述Z变换的取样。

9j2nk109j 解：

X1(k)x1(n)en0X(z)z0.5expj2kx(n)(0.5)ne1010n010nje2nk10

由上式得到

x1(n)(0.5)enj10nx(n)

3.14 如果一台通用计算机计算一次复数乘法需要100s，计算一次复数加法需要20s，现在用它来计算N＝1024点的DFT，问直接计算DFT和用FFT计算DFT各需要多少时间？

解：直接计算DFT：

22N10241048576次，1048576100s105s 复数乘法：

复数加法：N(N1)102410231047552次,104755220s21s

总计需要时间：(10521)s126s

用FFT计算DFT：

Nlog2N5120次,5120100s0.512s 复数乘法：2

复数加法：Nlog2N10240次,1024020s0.2048s

总计需要时间：(0.5120.2048)s0.7168s

3.15 仿照本教材中的图3.15，画出通过计算两个8点DFT的办法来完成一个16点DFT计算的流程图。

解：图P3.15_1所示的是用两个8点DFT来计算一个16点DFT的流程图。

3.16 设x(n){0,1,0,1,1,1}，现对x(n)进行频谱分析。画出FFT的流程图，FFT算法任选。并计算出每级蝶形运算的结果。

解：图P3.16_1所示的为时间轴选8点FFT的流程图和每级蝶形运算的结果。

3.17 根据本教材中图3.27所示的流程图，研究基2频率抽选FFT算法。设N为2的任意整数幂，但不等于8。为了给数据全部加上标号，假设数组中的数据被存在依次排列的复数寄存器中，这些寄存器的编号从0到N－1，而数组的编号为0到log2N。具有最初数据的数组是第0列，蝶形的第一级输出是第1列，依次类推。下列问题均与第m列的计算有关，这里1≤m≤log2N，答案应通过m和N表示。

（1）要计算多少个蝶形?每个蝶形有多少次复数乘法和复数加法运算？整个流程图需要多少次复数加法和复数乘法运算？

（2）由第（m－1）列到m列，包含的WN的幂是什么？

（3）蝶形的两个复数输入点的地址之间的间隔是多少？

（4）利用同样系数的各蝶形的数据地址间隔是什么？注意这种算法的蝶形计算的系数相乘是置于蝶形的输出端的。

NNlog2Nlog2N22 解：（1）级，每级个蝶形，共个蝶形。每个蝶形有1次复数乘法和2次复数

Nlog2NNlog2N加法运算，故整个流程图需要次复数加法和2次复数乘法运算；

（2）由第m-1列到m列，包含的

WN

m1m2k,k0,1,...,2N1； 的幂是

m （3）蝶形的两个复数输入点的地址之间的间隔是2N；

（4）利用同样系数的各蝶形的数据地址间隔是

2m1N,2mlog2N。

3.18 使用FFT对一模拟信号作谱分析，已知：①频率分辨率F≤5Hz；②信号最高频率f01.25kHz。试

确定下列参数：

（1）最小记录长度p；

t（2）取样点的最大时间间隔T；

（3）一个记录长度中的最少点数。

115Hz,tps0.2stp5解：（1）

f，最小记录长度

tp0.2s；

（2）

fs112f021.25kHz2.5kHzTs0.4ms3T2.510，取样点的最大时间间隔为；

（3）一个记录长度中的最少点数为

NtpT0.25002.5103。

3.19 已知信号x(n)和FIR数字滤波器的单位取样响应分别为

n15x(n)1,00,其他h(n)an,0n100,其他

（1）使用基2 FFT算法计算x(n)与h(n)的线性卷积，写出计算步骤。

（2）用C语言编写程序，并上机计算。

解：（1）计算步骤：

①在序列尾部补零将h(n)延长成为16点的序列；

②用基－2 FFT算法分别计算x(n)和h(n)的16点DFT，得到X(k)和H(k)；

③计算序列的乘积Y(k)X(k)H(k)；

④用基－2 FFT算法计算Y(k)的16点IDFT，便得到x(n)和h(n)的线性卷积y(n)。

（2）

3.20 已知两个实序列x1(n)和x2(n)的离散傅里叶变换分别为X1(k)和X2(k)。设复序列g(n)为

g(n)x1(n)jx2(n)其离散傅里叶变换为G(k)。令GOR(k),GER(k),GOI(k),GEI(k)分别表示G(k)的实部的奇数部

分，实数的偶数部分，虚数的奇数部分和虚数的偶数部分。试用GOR(k),GER(k),GOI(k),GEI(k)来表示X1(k)和

X2(k)。

11GOR(k)GR(k)GR(k)GER(k)GR(k)GR(k)22 解：因，

故

GR(k)GOR(k)GER(k)

类似有

GI(k)GOI(k)GEI(k)

因此可以用

GOR(k),GER(k),GOI(k),GEI(k)表示G(k)

G(k)GR(k)jGI(k)GOR(k)GER(k)jGOI(k)GEI(k)①

另一方面，由于

g(n)x1(n)jx2(n)，故有

G(k)X1(k)jX2(k) ②

但因x1(n)和x2(n)都是实序列，故X1(k)和X2(k)的实部都是偶对称序列，虚部都是奇对称序列，因此应将①式整理成下列形式

G(k)GER(k)jGOI(k)jGEI(k)jGOR(k) ③

对照式②和式③，便可得到

X1(k)GER(k)jGOI(k)

和

X2(k)GEI(k)jGOR(k)

3.21 线性调频Z变换算法的一个用途是使频谱的谐振峰变尖。一般说来，如果在z平面内靠近极点的一条圆周线上计算序列的Z变换，则可以观察到谐振。在应用线性调频Z变换算法或计算离散傅里叶变换时，被分析的序列必须是有限长的，否则必须先将序列截断。截断序列的变换只能有零点（除z=0或z=∞外），而原始序列的变换却有极点。本题的目的是要证明，在有限长序列的变换中仍可以看到谐振型响应。

（1）令x(n)u(n)，画出它的Z变换X(z)的极－零点略图。

nN1ˆ(n)1,0x0,其他 （2）令略图。

ˆ(n)等于从N点以后截断的x(n)。画出xˆ(n)的Z变换X(z)的极－零点即xˆ（3）画出

ˆ(ej)X随变化的略图。并在你的图中画出N增加时对

ˆ(ej)X的影响。

解：（1）

X(z)znn01z1z1z1

极－零点略图如图3.21_1（1）所示；

2kN2kNˆ(z)zn1zz1X1N11zz(z1)n0（2）

N1NN(zek0N1j)(zek1N1j)zN1(z1)zN1

零点：

zkej2kN,k1,2,...,N1；极点：z=0（N-1阶）。极－零点略图

如图3.21_1（2）所示；

（3）

je1sin(N/2)jˆX(e)j(N1)je(e1)sin(/2)

ˆ(ej)X 如图3.21_1（3）所示为尖，同时增高。

ˆ(ej)X随变化的略图，当N增加时，的谐振峰变