北京邮电大学《数字信号处理》课件-第3章 离散傅里叶变换（DFT）

第3章离散傅里叶变换（DFT）北京邮电大学《数字信号处理》2本章主要内容离散傅里叶变换的定义及物理意义离散傅里叶变换的基本性质频率域采样离散傅里叶变换的应用3引言各种形式的傅里叶变换非周期实连续时间信号的傅里叶变换:频谱是一个非周期的连续函数

周期性连续时间信号的傅里叶变换:频谱是非周期性的离散频率函数

非周期离散时间信号的傅里叶变换:频率函数是周期的连续函数离散周期序列的傅里叶变换:具有既是周期又是离散的频谱，即时域和频域都是离散的、周期的4各种形式的傅里叶变换示意图5傅里叶变换的一般规律如果信号频域是离散的，则该信号在时域就表现为周期性的时间函数。相反，在时域上是离散的，则该信号在频域必然表现为周期性的频率函数。如果时域信号离散且是周期的，由于它时域离散，其频谱必是周期的，又由于时域是周期的，相应的频谱必是离散的，离散周期序列一定具有既是周期又是离散的频谱，即时域和频域都是离散周期的。得出一般的规律：一个域的离散就必然造成另一个域的周期延拓。6离散傅里叶变换的导出由于数字计算机只能计算有限长离散的序列，因此有限长序列在数字信号处理中就显得很重要。Z变换和傅里叶变换无法直接利用计算机进行数值计算。针对有限长序列“时域有限”这一特点，导出一种更有用的离散傅里叶变换DFT(DiscreteFourierTransform)。

73.1离散傅里叶变换的定义DFT的定义DFT和z变换、序列的傅里叶变换的关系DFT的隐含周期性83.1.1离散傅里叶变换的定义离散傅里叶正变换(DFT)定义0≤k≤N-1

0≤n≤N-1x(n)长度为M，其x(n)的N点离散傅里叶变换为：离散傅里叶反变换(IDFT)定义N称为DFT变换区间长度，9例3.1：设有限长序列为x(n)=R4(n)，求x(n)的傅里叶变换，以及4点、8点、16点DFT。

解（1）x(n)的傅里叶变换

（2）x(n)的4点DFT例：离散傅里叶变换10（3）x(n)的8点DFTk=0，1，…，7

（4）x(n)的16点DFTk=0，1，…，15

15157711例3.1的图形显示同一序列不同点数的DFT是不相同的。x(n)的N点DFT是x(n)的傅里叶变换X(ejw)在区间[0，2π]上的N点等间隔取样。123.1.2DFT和Z变换、序列的傅里叶变换的关系

设序列x(n)的长度为N，其Z变换、傅里叶变换和DFT分别为，0≤k≤N-113三种变换的关系

0≤k≤N-10≤k≤N-1比较三式可得式(3.3)表明，序列x(n)的N点DFT相当于是x(n)的z变换在单位圆上进行N点等间隔取样，同时第一个取样点应取在z=1处。式(3.4)说明，X(k)是x(n)的傅里叶变换X(ejw)在区间[0，2π]上的N点等间隔取样。(3.3)(3.4)14DFT和Z变换的关系0≤k≤N-1N＝8时，单位圆上的8个等间隔采样点示意图如下：15DFT和序列的傅里叶变换的关系物理意义：X(k)是x(n)的傅里叶变换X(ejω)在区间

[0，2π]上的N点等间隔取样。实现了频域离散化

0≤k≤N-1163.1.3DFT的隐含周期性

DFT变换对中，具有周期性：其中k，m，N均为整数

因此有结论：X(k)具有隐含周期性，且周期均为N。同理可得IDFT也隐含周期性：式中17周期序列与周期延拓序列任何周期为N的周期序列都可以看作长度为N的有限长序列x(n)的周期延拓序列，而x(n)则是的一个周期，称为的主值区序列（简称主值序列），即为了简单，引入运算符((n))N，表示模N

对n求余数，即如果

n=mN+n1，0≤n1≤N-1，m为整数

则((n))N=

((n1+mN))N=n1

18例:序列的周期延拓例如，N=8，，则有

于是19X(k)与x((n))N的离散傅里叶级数系数的关系如果x(n)的长度为N，且，则可写出的离散傅里叶级数表达式

式中结论：有限长序列x(n)的离散傅里叶变换X(k)，正好是x(n)的周期延拓序列x((n))N的离散傅里叶级数系数的主值序列。完全确定了x((n))N

的频谱特性，所以，X(k)

实质上是x((n))N

的频谱特性。这样就容易理解R4(n)的4点DFT只有零频率成分了。（因为R4((n))N正是一个直流序列）203.2离散傅里叶变换的基本性质

线性性质循环移位性质循环卷积定理复共轭序列的DFTDFT的共轭对称性213.2.1线性性质设x1(n)和x2(n)长度分别为N1和N2，且取N≥max[N1，N2]，则y(n)的N点DFT为

0≤k≤N－1

注意：如果N1和N2不相等，则以N为DFT变换长度时，其中相对较短的序列就通过补零增加到长度为N。

223.2.2循环移位性质1、序列的循环移位设x(n)长度为N，则x(n)的循环移位定义为将x(n)以N为周期进行周期延拓得到再将左移m得到，最后取的主值序列则得到有限长序列x(n)的循环移位序列y(n)。可见，循环移位的本质是周期移位。232、时域循环移位定理设x(n)是长度为N的有限长序列，y(n)为x(n)的循环移位，即

则其中，0≤k≤N-1时域循环移位定理24时域循环移位定理证明证明令n+m=n'，则有25频域循环移位定理3、频域循环移位定理如果X(k)=DFT[x(n)]N，0≤k≤N-1，Y(k)=X((k+l))NRN(k)，则证明方法与时域循环移位定理类似。26式中，L称为循环卷积区间长度，L≥max［N，M］。上式显然与第1章介绍的线性卷积不同，为了区别线性卷积，用表示循环卷积，用表示L点循环卷积，即yc(n)=h(n)

x(n)。观察上式，x((n－m))L是以L为周期的周期信号，n和m的变化区间均是［0,L－1］，1、两个有限长序列的循环卷积设序列h(n)和x(n)的长度分别为N和M。h(n)与x(n)的L点循环卷积定义为3.2.3循环卷积定理h0h7h6h5h4h3h2h1x0x7x5x6x4x3x2x127【例3.2.1】计算下面给出的两个长度为4的序列h(n)与x(n)的4点和8点循环卷积。解h(n)与x(n)的4点循环卷积矩阵形式为h(n)与x(n)的8点循环卷积矩阵形式为h(n)和x(n)及其4点和8点循环卷积结果分别如图(a)、(b)、(c)和(d)所示。请计算验证本例的8点循环卷积结果等于h(n)与x(n)的线性卷积结果。后面将证明，当循环卷积区间长度L大于等于y(n)=h(n)*x(n)的长度时，循环卷积结果就等于线性卷积。

28

图3.2.2序列及其循环卷积波形29例1.3线性卷积首先将h(n)用h(m)表示，并将波形翻转，得到h(－m)，然后将h(－m)移位n，得到h(n－m)，n>0,序列右移；n<0，序列左移。如n=1，得到h(1-m)，接着将

x(m)和h(n－m)相乘后，再相加,得到y(n)的一个值。对所有的n重复这种计算,最后得到卷积结果，如图1.3.2(f)所示,y(n)表达式为y(n)={1,2,3,4,3,2,1}30画出h(m)与x(m)将x(m)周期化得到x((m))N再反转形成x((-m))N取主值序列得到x((-m))NRN(m)对x

(m)循环反转序列循环移位n,得到x((n-m))NRN(m)当n=0,1,…N-1时，分别将h(m)与x((n-m))NRN(m)相乘，并对m在0~(N-1)区间上求和，得到的h(n)与x(n)循环卷积31有限长序列x1(n)和x2(n)的长度分别为N1和N2，N=max［N1,N2］，x1(n)和x2(n)的N点循环卷积为

则x(n)的N点DFT为N

（3.2.9）2、循环卷积定理

（3.2.8）其中32循环卷积定理证明令n－m=n'，则有证明33

因为上式中以N为周期，所以对其在任一周期上的求和结果不变，因此0≤k≤N-1时域循环移位定理讨论34频域循环移位定理讨论x(n)=x1(n)∙x2(n)则或如果N

N

353.2.4复共轭序列的DFT复共轭序列的DFT设x*(n)是x(n)的复共轭序列，长度为N，0≤k≤N-1(3.17)则且又由X(k)的隐含周期性，有X(N)=X(0)用同样的方法可以证明证明36

3.2.5DFT的共轭对称性1、有限长共轭对称序列和共轭反对称序列xep(n)

表示有限长共轭对称序列xop(n)

表示有限长共轭反对称序列01234567xep(n)***01234xop(n)567***注意：

DFT的共轭对称性是关于N/2点的对称性37可得将上式中的n换成N－n，并取复共轭，得到：N为偶数时，将上式中的n换成N/2－n任何序列可表示为：38如果将x(n)表示为x(n)=xr(n)+jxi(n)其中2．DFT的共轭对称性分别对实部和虚部DFT得：Xep(k)=DFT［xr(n)］是X(k)的共轭对称分量Xop(k)=DFT［jxi(n)］是X(k)的共轭反对称分量由DFT的线性性质即可得39

(2)如果将x(n)表示为x(n)的共轭对称分量x(n)的共轭反对称分量因此其中40如果序列x(n)的DFT为X(k)，则x(n)的实部和虚部（包括j）的DFT分别为X(k)的共轭对称分量和共轭反对称分量；x(n)的共轭对称分量和共轭反对称分量的DFT分别为X(k)的实部和虚部乘以j。DFT的共轭对称性质41例题利用DFT的共轭对称性，设计一种高效算法，通过计算一个N点DFT，就可以计算出两个实序列

和的N点DFT。解：构造新序列

对进行N点DFT

42设x(n)是长度为N的实序列，且X(k)=DFT［x(n)］，则X(k)满足如下对称性：(1)X(k)共轭对称，即X(k)=X*(N-k)k=0,1,…,N-1(2)如果x(n)是偶对称序列，即x(n)=x(N－n)，则X(k)实偶对称，即

X(k)=X(N－k)(3)如果是奇对称序列，即x(n)=－x(N－n)，则X(k)纯虚奇对称，即X(k)=－X(N－k)433.3频率域采样

频域采样指对序列的傅里叶变换进行取样。由时域取样定理，在一定的条件下，可以通过时域离散取样信号恢复原来的连续信号。对有限长序列而言，由DFT的讨论可知，N点DFT就是在频域对序列傅里叶变换X(jω)在[0,2π]上的N点等间隔取样，即实现了频域取样。44对于任意序列x(n)，假设存在Z变换，且收敛域包括单位圆在单位圆上对X(z)进行N点等间隔取样，得到

问题：能否利用取样值X(k)恢复原始的时域信号x(n)？

3.3频率域采样

该式表示在区间[0,2π]上对x(n)的傅里叶变换的N点等间隔采样X(k)看做长度为N的有限长序列xN(n)的DFTxN(n)=IDFT[X(k)]推导xN(n)与原序列x(n)之间的关系，即可得到频率采样定理

45将X(k)看成是长度为N的有限长序列的DFT，即0≤n≤N-1定义由于所以46代入频率取样值，得由于所以47

的意义

是原序列x(n)以N为周期的周期延拓序列。时域的取样造成频域的周期延拓，频域上的取样，同样也造成时域的周期延拓，这正是傅里叶变换时域和频域之间对偶关系的反映。如果序列x(n)的长度为M，当N<M

，产生时域混叠现象。只有当频域取样点数N≥M时这就是频域采样定理。483.4离散傅里叶变换的应用

用DFT计算线性卷积用DFT对连续信号进行谱分析用DFT对序列进行谱分析493.4.1用DFT计算线性卷积

设h(n)和x(n)都是长度为L的有限长因果序列，它们的L点循环卷积为且由时域循环卷积定理有0≤k≤L-1L50用DFT计算循环卷积方框图用DFT计算循环卷积方框图理由：DFT运算存在快速算法（FFT）。51循环卷积与线性卷积相等的条件条件：两个长度分别为N和M的序列，其线性卷积可用L点循环卷积来代替，但必满足条件

L≥N+M-1下面证明该条件。52卷积相等条件的讨论假设h(n)长度为N，x(n)长度为M，则线性卷积为L点循环卷积为其中，L≥max[N，M]，53由上可得上式中因此54yc(n)是yl(n)以L为周期的周期延拓序列的主值序列。

由于卷积yl(n)的长度为N+M-1，因此当循环卷积的长度L≥N+M-1时，以L为周期的周期延拓才不会出现混叠现象，此时取主值序列显然满足yc(n)＝yl(n)

。说明：用DFT计算线性卷积的原理框图（L≥N+M-1)55h(n)与x(n)的线性卷积可表示为设序列h(n)长度为N，x(n)为无限长序列。将x(n)等长分段，每段长度取M，则，两个序列的长度相差很大的情况（M>>N）式中说明：计算h(n)与x(n)的线性卷积时，可先计算分段线性卷积yk(n)=h(n)*xk(n)，然后把分段卷积结果叠加起来即可，每一段卷积yk(n)的长度为N＋M－1，因此相邻分段卷积yk(n)与yk＋1(n)有N－1个点重叠，必须把重叠部分的yk(n)与yk＋1(n)相加，才能得到正确的卷积序列y(n)。所以，称之为重叠相加法。56图3.4.3用重叠相