《数字信号处理》课件第3章

第三章离散傅里叶变换(DFT)3.1引言

3.2周期序列的离散傅里叶级数(DFS)表示式

3.3离散傅里叶级数的性质

3.4周期序列以离散傅里叶级数表示时的性质小结

3.5Z变换的采样

3.6有限长序列的傅里叶表示——离散傅里叶变换

3.7离散傅里叶变换的性质

3.8离散傅里叶变换的性质小结

3.9以离散傅里叶变换实现线性卷积

3.1引

言

在具体讨论序列的离散傅里叶变换之前，让我们先复习一下模拟信号傅里叶变换的有关知识。对图3.1所示的连续的非周期信号，其傅里叶变换及傅里叶反变换可以分别由式(3－1a)及(3－1b)表示，即有(3-1a)及

(3-1b)在图3.1中，我们还列出了该信号的频谱示意图。不难看到，一个时域连续的非周期信号的频谱是连续的、非周期的。类似地，对于图3.2所示的时域连续的周期信号，其傅里叶变换对则如式（3-2）所示。

图3.1连续的非周期信号及其非周期的连续频谱

(3-2a)(3-2b）式中 为时域连续的周期性信号，Ta为其周期。式(3-2b)是一种级数表示式，式中各谐波分量的系数就是它的频谱，如图3.2所示。以上讨论表明，连续的周期性信号的频谱是一组非周期、

离散的等间隔谱，其频率间隔 。

图3.2时域连续的周期信号与它的非周期的离散频谱

在第一章的讨论中，我们已经知道序列的傅里叶变换为

（3-3a）

而且在有关的分析中也了解，信号在时间域的离散化，将在频率域形成周期性延拓。所以时间离散信号的傅里叶变换实际上是ω的连续的周期性函数。为此，我们在式（3-3a）中特意在X(ejω)上加了周期性符号“~”。同样，序列的傅里叶反变换也可表示成

(3-3b)

我们在这一章将要研究的离散傅里叶变换（DFT），也是一种有限长序列的傅里叶变换。特别是离散傅里叶变换在频率域也以序列表示，它不再是连续函数。通过讨论，我们将可看到，它实际上相当于该信号的傅里叶变换的等角度间隔的采样。离散傅里叶变换作为序列的一种傅里叶表示方法，除了具有重要的理论意义之外，更因其独特的表示方法及具有相应的快速算法，从而在实现各种数字信号处理算法时起着举足轻重的作用。离散傅里叶变换的快速算法，

将在第五章中另作讨论。

推导及解释有限时宽序列的离散傅里叶变换表示式可以有多种途径。在这里，我们选用在有限长序列与周期序列之间作某种约定，从而推导出离散傅里叶变换的具体表示式。为此，我们先讨论周期序列的傅里叶级数公式。需要说明一下的是，周期序列的傅里叶表示式本身就是一种很重要的傅里叶变换形式，但是在这里，则更是为了用它表征有限长度序列。实际做法是，对于一个有限长序列，我们先构造一个周期序列，周期序列的每一个周期都与该有限长序列的长度一样。于是我们可看到这个周期序列的傅里叶级数表示式与有限长序列的傅里叶变换有着完全对应的特殊关系。

3.2周期序列的离散傅里叶级数（DFS）表示式

假设周期序列的周期为N，那么对于任意整数k，将有

(3-4)这样的序列无法用Z变换表示，因为没有一种z值能使此序列的Z变换收敛。然而，此时的x(n)与时域连续的周期性信号xa(t)一样，也可用相应的傅里叶级数描述，即可用与之相关的复指数序列的加权和表示。这些复指数序列的频率则为周期序列x(n)之基频的整数倍，也就是此时的基频序列~~~而k次谐波序列为

它在形式上与连续周期函数相同。不过需要强调的是，周期为N的周期序列的傅里叶级数的谐波成分只有N个独立分量，这与连续周期函数的傅里叶级数通常具有无限多个谐波分量有着重大的区别。

具体原因是出于

r为任意整数

也就是

（3-5）

之故。即对k而言，也是以N为周期的周期性函数，它对于k与k+rN（r为任意整数）都是一样的。它与相应的N个加权系数相乘后，即可得

（3-6）

式中乘上系数是为了求解 时方便，对问题并无实质性影响。下面我们就着手确定系数 。为此，先将式（3-6）两边都乘上 ，并令n从0到N-1的一个周期内求和：

（3-7）

考虑到

所以当式（3-7）取k=l时,即可得

或

（3-8）

式（3-8）表明X(k)也是周期为N的周期序列，这与式（3-5）的复指数只在k(k=0,1,…,N-1)才存在不同值一样,因而如式(3-6)所示,一个周期序列的傅里叶级数表示式也只有N个不同的系数,而且在频率域构成一个新的周期序列。式（3-6）与式（3-8）也被视为周期序列的傅里叶变换对。为了表示方便，通常还用符号WN来书写这个变换对。此时令

（3-9）

于是离散傅里叶级数的分析与综合式可分别表示为

（3-10a）

和

(3-10b)式中 和都是周期为N的周期序列。至此，我们不同程度地回顾及讨论了四种傅里叶变换的基本内涵，为了便于理解，我们将其主要特征简单列于表3.1中。

表3.1几种傅里叶变换的对比3.3离散傅里叶级数的性质

3.3.1线性关系如果周期为N的两个周期序列组合成

(3-11)则的离散傅里叶级数的系数

式中所有序列均为周期序列，周期同为N。

3.3.2序列的位移如果的傅里叶系数为，则所对应的系数将为，此时设m<N(如m>N，可替换成以m′表示，m′=m（模N），它将小于N)。为了求证这个结果，我们设则

(3-12)如果令n+m=n′，那么

同时，对于 ，也可求得其

3.3.3调制特性 的傅里叶系数为 。为获此结果，我们同样另设

于是有

(3-13)3.3.4对称性与第一章讨论的傅里叶变换相仿，一个周期序列的傅里叶级数表示式同样具有某些对称性质。有关特性的推导与第一章所作的讨论十分类似，例如,

的傅里叶系数为，则的傅里叶系数为。这是因为而的傅里叶系数将为：

3.3.5周期卷积

设是两个周期均为N的周期序列，则其周期卷积

（3-14）

式（3-14）表示的由 进行周期卷积构成 的方式容易联想到第一章中讨论过的序列的卷积。这里应该指出，周期卷积与非周期序列的卷积实际上存在着不小的差别。式（3-14）中的序列 都是变量m的周期同为N的周期函数。由于周期序列的乘积同样是周期为N的周期函数，因此式中的求和也就只需在一个周期上进行，然后按周期延拓其结果即可。对式（3-14）的变量作简单替换，即可得到如式（3-15）所示的周期卷积的另一种表示形式：（3-15）

图3.3中列举了利用式（3-14）进行周期卷积的具体过程。在作此类卷积时，当一个周期中的有关样本移出计算区间时，

下个周期中的相应的样本就移入该区间。

图3.3两个周期序列的周期卷积过程

图3.3两个周期序列的周期卷积过程

图3.3两个周期序列的周期卷积过程

我们还可以看到，如果周期均为N的周期序列的周期卷积为，即

则其傅里叶系数 将满足

这是因为

所以可得

如果将时域与频域的位置对换，

将可得到几乎一样的结果。

也就是说，

若周期序列

则的傅里叶系数将如式（3-16）所示，即此时的

3.4周期序列以离散傅里叶级数表示时的性质小结

表3.2离散傅里叶级数的性质

续表

3.5Z变换的采样

上面我们讨论了周期序列及其离散傅里叶级数的变换关系，它们是

及

(3-18)(3-17)事实上，周期序列也可以理解为取的一个周期作Z变换（周期序列的Z变换，它并不收敛），然后在单位圆上按等角度间隔采样所得。为此，我们令x(n)为的一个周期，如图3.4所示。这意味着0≤n≤N-1时，，而n为其他值时，x(n)=0。此时x(n)的Z变换可写成（3-19）

也可以写作

（3-20）

图3-4有限长序列x(n),它在时等于x(n)，而在n为其他值时均为零~

对照式（3-17）与式（3-19），不难发现与X(z)有着下列关系，即

（3-21）

它相当于在单位圆的N个等角度分点上对X(z)采样，而第一个采样点应选在z=1处。图3.5列出了单位圆上的采样点的位置。

图3.5为了得到，在单位圆上对X(z)采样的各等角度间隔点

因此，可以理解成仅取与之对应的的一个周期这样的有限长序列的Z变换在单位圆上作的等角度间隔采样所得的各个样本值。图3.6画出了它们之间的相应关系。

图3.6有限长序列与相应的周期序列间的关系图

我们再从数学角度看一下与x(n)之间的具体关系。因为

若将式（3-21）的代入上式，即有

考虑到

因此

(3-22)即此时的也可理解成由非周期序列x(n)按周期N逐次重复构成的。当然，如果非周期序列的长度大于N，同样会在时域发生混叠。我们还可以看到，只要x(n)的持续时间不大于N，此时仅需抽取中的一个周期，就可以精确地将x(n)恢复出来，即（3-23）

另外，既然从单位圆上的X(z)的N个样本可以恢复x(n)，那么也有可能由这N个样本恢复X(z)，即由经“内插”求得相应的X(z)。为此，我们设n≥N时，x(n)=0，则(3-24)式中的

（3-25）

可视作此时的插值函数。式（3-24）表明，对于长度为N的有限时宽序列，其Z变换X(z)可用它在单位圆上的N个“频率采样”来表示。图3.7列出了它们之间的相应关系。

图3.7与图3.6相当的反过来表示的关系图

正如下一章将要指出的那样，式（3-24）可以视为有限时宽的单位采样响应系统的一种可能实现的依据。通过z=ejω的代换，它将具有更加直观和更为有用的表示方式。令z=ejω，则式（3-24）可表示成

(3-26)而插值函数

图3.8列出了N=8的|Φk(ejω)|的部分函数值。

图3.8N=8的|Φ0(ejω)|、|Φ1(ejω)|的函数值

同样，从式（3-26）不难看到，

此时的

(3-28)讨论至此，我们可以看到，所谓Z变换的采样，实际上代表了Z变换与DFS之间的某种对应关系，其中之一是采样，反过来则为内插。我们先讨论了采样，一个周期序列的离散傅里叶级数的系数，实际上可如图3.6所示那样取的一个周期构成有限长序列并确定其Z变换，然后在Z平面的单位圆上按等角度间隔(即 ，k=0,1,…,N-1)对X(z)采样后求得。3.6有限长序列的傅里叶表示——离散傅里叶变换

上一节我们讨论了周期序列的离散傅里叶级数表示式，而且还讨论了这种表示式在某种约定条件下也可以运用于有限长序列。应该特别重视的是，在此基础之上还可以进而得到有限长序列的离散傅里叶变换。当然，此时所指的有限长序列，并不是一般的非周期序列，因为一般的非周期序列的傅里叶变换在第一章中已经讨论过，它是一种连续的、周期性函数。这种连续的周期性频谱实际上难以用计算机或数字信号处理器作具体运算。这里所说的有限长序列，是针对周期序列中的一个周期而言的。此时的

(3-29)

为了表示方便，我们可利用矩形序列RN(n)，

(3-30)于是有

(3-31)从3.2节的讨论知道，周期序列的离散傅里叶级数的系数本身也是以N为周期的周期序列，即如式（3-10a）及式（3-10b）所示那样，分别为

周期序列的离散傅里叶级数的系数与第一章讨论的序列的傅里叶表示一样，也有明显的对偶关系。为了保持这种时域与频域间的对偶关系，我们选取此时的有限长序列的离散傅里叶系数同样仅为的一个周期，即

(3-32)这里的

(3-33)式（3-32）及式（3-31）可以表示成

(3-34a)

及

(3-34b)这就是序列的离散傅里叶变换对。

由上面的论述可知，这里讨论的序列在时域显然是离散的。诚如表3.1中所示那样，它的傅里叶变换将是周期性的。但是这个序列实际上是将其作周期性延拓以后考虑的，或者说，这个有限长序列是隐含着周期性的，它的傅里叶表示还应该是离散的。而且在相关讨论中，我们又仅在这种离散的、周期性的离散傅里叶级数的系数表示中选取一个周期作为此类序列的离散傅里叶变换，所以它在频域也将是一个离散的、有限长的（隐含周期性的）序列。这就是式（3-34a）所示的离散傅里叶变换分析式。反过来也一样，也有与之对应的由式（3-34b）所示的离散傅里叶变换综合式。根据3.5节所作的介绍及上述讨论，我们可以看到，有限长序列的离散傅里叶变换实际上也相当于其Z变换沿单位圆的等角度间隔的采样，而且两者的长度或者隐含的周期均是N。

图3.9有限长序列有关变换间的对应关系示意图

3.7离散傅里叶变换的性质3.7.1线性关系如由两个有限长序列x1(n)与x2(n)线性组合成的序列

则x3(n)的离散傅里叶变换

显然，如果x1(n)的长度为N1，x2(n)的长度为N2，则x3(n)的长度N3=max［N1,N2］，而离散傅里叶变换将按N=N3计算。例如，若N1<N2，则相应的也即此时的X1(k)将由x1(n)增加N2-N1个零点后确定。

3.7.2序列的循环位移序列的循环位移可以用图3.10加以说明。图3.10（a）所示的是长度为N的有限长序列x(n)，图3.10（b）则是与之对应的周期序列移位m个样本间隔后所得的如图3.10（c）所示（图中只画了m=1的情况）。按图3.10（d）那样，在区间0≤n≤N-1内截取的一个周期，所得的x1(n)就是x(n)的m为+1的循环位移序列。对比图3.10（a）和图3.10（d），x1(n)与x(n)虽然都限于区间0～N-1之间，但二者并不相等。实际上，从图3.10（b）及图3.10（c）不难看到，若将周期序列移位，并只观测和截取0～N-1这个区间，则当一个样本移出该区间时，与之相同的另一个样本将从另一端移入此区间，因而在0~N-1内截取其一个周期时，将得到图3.10（d）所示的序列，即我们把这种位移称作序列的循环位移。

图3.10序列的循环位移

图3.10序列的循环位移

为了将x(n)的离散傅里叶变换与x1(n)的离散傅里叶变换联系在一起，我们先看周期序列的情况。由于和分别代表与的离散傅里叶系数，并有因此对于x1(n)=x((n+m))RN(n)，从式（3-32）的定义式，即可推得

(3-35)考虑到时域与频域间的对偶性，当离散傅里叶变换的系数作循环位移时，也将有与之对应的结果。假设X(k)和X1(k)分别代表x(n)与x1(n)的离散傅里叶变换，如果

(3-36)则

(3-37)3.7.3对称性讨论有限长序列的离散傅里叶变换的对称性质时，通常不能采用1.7节所给的共轭对称和共轭反对称定义，因为对于时宽为N的有限长序列x(n)，其共轭对称分量xe(n)与共轭反对称分量xo(n)的时宽均为2N-1。前面已经多次强调，我们这里的x(n)，实际上隐含着周期性，而且十分明显，周期为N的周期序列的共轭对称分量与共轭反对称分量仍是周期为N的周期序列。这启示我们应将x(n)分解成两个时宽为N的有限长序列，并令它们分别对应于的共轭对称分量与共轭反对称分量中的一个周期，并记作xep(n)与xop(n)。于是，由于（３－３８）以及

(3-39a)和

(3-39b)我们将xep(n)与xop(n)定义为(3-40a)(3-40b)或

(3-41a)(3-41b)显然，xep(n)与xop(n)与以前介绍的xe(n)与xo(n)有别，不过通过试做本章的习题3.17可以证明(3-42a)(3-42b)

和

可利用xe(n)与xo(n)在0≤n≤N-1的混叠来产生相应的xep(n)与xop(n)。序列xep(n)与xop(n)分别称为x(n)的周期性共轭对称分量与周期性共轭反对称分量。当xep(n)与xop(n)为实序列时，也被称作周期性偶分量与周期性奇分量。当然，xep(n)与xop(n)并不是周期序列，它们只是隐含了周期性，两者本身则各为周期序列与的一个周期，这一点请勿混淆。式（3-41a）与式（3-41b）是用定义xep(n)和xop(n)的，而其逆关系式则可由式(3-39a）与式（3-39b）推得。因为由式（3－39a）和式（3-39b），可得因此

合并式（3-40）和式（3-43），就可得到

(3-44)利用3.3节离散傅里叶级数的对称性的思路及结果，即可直接推出离散傅里叶变换的对称性质。我们假设长度为N的一个有限长序列x(n)的离散傅里叶变换为X(k)，于是可以得到x*(n)的离散傅里叶变换为X*((-k))NRN(k)，x*((-n))NRN(n)的离散傅里叶变换为X*(k)。Re［x(n)］的离散傅里叶变换为Xep(k)，Im［x(n)］的离散傅里叶变换为Xop(k)。与此相似，xep(n)的离散傅里叶变换为Re［X(k)］，xop(n)的离散傅里叶变换为Im［X(k)］。而且，当x(n)为实序列时，还可推得Re［X(k)］与|X(k)|为周期偶序列，而Im［X(k)］与arg［X(k)］将是周期奇序列。同时，Re［X(k)］为xep(n)的离散傅里叶变换及Im［X(k)］为xop(n)的离散傅里叶变换。3.7.4循环卷积在3.2节的讨论中，我们知道，两个周期序列的离散傅里叶级数的系数之积相当于该序列间的周期性卷积。在这里，我们讨论两个时宽为N的有限长序列x1(n)与x2(n)。它们的离散傅里叶变换分别为X1(k)与X2(k)，希望确定另一个序列x3(n)，其离散傅里叶变换X3(k)应满足X3(k)=X1(k)X2(k)。为了求得x3(n)，我们可以利用3.3节中的周期卷积的结果，即此时的x3(n)将可视为的一个周期，也即(3-45)当然也可以表示成

上式就是两个序列x1(n)和x2(n)的N点的循环卷积，通常还表示成

Ｎ(3-46)(3-47)循环卷积显然与我们以前讨论的线性卷积不同。由式（1-20）所示的线性卷积可以理解为将一个序列先作卷折及线性位移，并与另一个序列相乘，然后再将乘积求和;所得的新序列的长度则为两序列的长度之和减去一，用在这里则为2N-1。基于周期卷积基础之上的循环卷积当然与之有别，它所得的序列长度应为N而非2N-1。为了进一步熟悉循环卷积的具体运算，我们仍从式（3-47）和式（3-46）开始，

即此时的

(3-48)计算循环卷积时，显然可以将两序列都先周期化，并按周期卷积定义计算周期卷积，然后取一个周期确定。但在实际计算时，有时考虑到它最终只取一个周期，即m只取到0～N-1，而且其中的x1((m))N又是不作移动的，所以也可以只将x2(n)周期化。因此式（3-48）可以写成(3-49)于是，在对式（3-49）作具体计算时，它与一般的线性卷积在形式上已无重大区别，因而也可直接表示成

(3-50)

图3.11循环卷积的具体计算

图3.11循环卷积的具体计算

此后，我们只需将x2(m)卷折及周期化成由图3.11（c）所示的x2(－m)N的形式，并将其按不同的n作相应的位移，以构成不同的x2((n-m))N，图（d）列出了n=1的x2((n-m))N的情形。接着，再如式（3-49）所示那样，令其与x1(m)相乘并且求和，进而确定由图3.11（e）所示的x3(n)的最终结果。当然，计算式（3-48）时，不按式（3-49）那样将x2(n)周期化，而是仅把x1(n)周期化，结果也是一样的，此时的循环卷积形式为(3-51)为了对循环卷积与线性卷积的实质及异同有更好的理解，我们将式（3-51）所示的用以计算循环卷积的表示式以图3.12的框图代替。

图3.12实现式(3-51)运算的原理框图

图中所示的PN(n)及x2(n)分别代表各单元的单位采样响应。PN(n)可表示成图3.13所示的形式，它完成输入信号周期化的作用。图3.13周期序列PN(n)示意图

我们知道，改变线性级联系统中有关单元的顺序，其系统函数并不改变。所以图3.14与图3.12应该等效。

图3.14图3.12的另一种表示

图中的表示x1(n)与x2(n)的线性卷积，

即

经PN(n)周期化后再由RN(n)取其一个周期得到x1(n)与x2(n)的循环卷积x3(n)。讨论至此，难免会有这样的疑问，就是先将线性卷积的结果以N为周期实现周期化，然后又以N为长度截取其一个周期，这多不多余？如果多余，该步骤应该可以省掉。不过，真的省掉以后，它将表明两个序列的循环卷积与线性卷积完全一样，这当然又有问题了。为了使进一步的讨论更加直观和简便，我们设此时的x1(n)与x2(n)完全一样，它们如图3.15(a)所示。图3.15实现循环卷积计算的图3.14的具体过程

图3.15实现循环卷积计算的图3.14的具体过程

图3.15表明，由x1(n)与x2(n)完成的线性卷积的长度为2N-1，它显然比N要长，用实现周期为N的周期化时，将如图3.15（c）所示那样发生信号的“混叠”，而我们所求的循环卷积x3(n)就是在此基础上截取一个周期得到的，它与无疑有别。这表明图3.14中所作的周期化后再截取一个周期的步骤并非多余。那么，到底在什么情况下序列的循环卷积会与线性卷积相同呢？通过上述讨论，我们不难发现，如果在实现线性卷积的周期化时，适当增加周期长度，并使混叠现象不再出现，这时所得的循环卷积就与线性卷积一样。图3.16中我们选用2N作周期化的周期(即以P2N(n)完成周期化功能)，此时不会出现信号混叠（事实上只需将周期增长至2N-1即可），截取以2N为长度的一个周期所得的循环卷积x1(n)○x2(n)将与x1(n)*x2(n)相同。或者说在周期化时不发生信号混叠的前提下，可用序列的循环卷积实现它们的线性卷积。Ｎ图3.16以循环卷积实现线性卷积的具体过程

图3.16以循环卷积实现线性卷积的具体过程

3.8离散傅里叶变换的性质小结

表3.3离散傅里叶变换的一些主要性质

表3.3离散傅里叶变换的一些主要性质

3.9以离散傅里叶变换实现线性卷积

我们知道，线性卷积相当关键,它是在时域研究和求解一系列问题的重要手段。图3.17

就是最普通的利用线性卷积确定信号经过一个线性移不变系统的响应的实例。

图3.17线性移不变系统输入输出的卷积关系

当然，在工程实践中，信号与系统有时会相当复杂，它会给卷积的具体计算带来许多麻烦。利用循环卷积，特别是有了离散傅里叶变换的快速算法（FFT）以后，就可以利用循环卷积实现线性卷积的高效计算。

为了计算长度分别为N1与N2的序列x(n)和h(n)的线性卷积，此时可以像图3.18所示那样先