《离散傅里叶变换(DFT).ppt》由会员分享，可在线阅读，更多相关《离散傅里叶变换(DFT).ppt（95页珍藏版）》请在三一办公上搜索。
1、引言3.1 离散傅里叶变换(DFT)的定义 3.2 离散傅里叶变换的基本性质3.3 频域采样3.4 DFT快速算法FFT3.5 DFT的应用举例,第3章 离散傅里叶变换(DFT)及其快速算法（FFT）,引言,DFT与FT区别 FT:序列的付里叶变换,时频对应关系 DFT:序列的FT的有限点采样.也可以直接定义 即DFT 是FT的N点等间隔采样-频域采样定理 频域采样 时域周期重复-N越大,DFT包络线越逼近FT DFT变换的意义:FT是连续谱,采样离散化后便于计算 机处理 DFT的定义、性质及频域采样定理、FFT及其应用,3.1 离散傅里叶变换的定义,DFT定义DFT与Z变换及FT的关系:DF
2、T的物理意义DFT的周期性:-DFT与DFS的关系 DFT是DFS的主值区间 DFT 的矩阵表示,3.1 离散傅里叶变换的定义,3.1.1 DFT的定义 设x(n)是一个长度为M的有限长序列，则定义x(n)的N点 离散傅里叶正变换为,离散傅里叶逆变换为,离散傅里叶变换对,式中，N称为DFT变换区间长度NM，可见：DFT使有限长时域离散序列与有限长频域离散序列建立起对应关系,例 1,已知，分别求 和 时的。,解：,由该例可知：频率采样点数不同，DFT的长度不同，DFT 的结果也不同。,图 3.1.1 X(k)与X(e j)的关系,例2：，分别计算x(n)的8点、16点DFT。解:x(n)的8点D
3、FT为 x(n)的16点DFT为,返回,是 在频率区间上的等间隔采样,返回,可见:对于同一序列x(n)DFT变换区间长度N不同,DFT变换结果X(k)不同,当N确 定后,X(k)与x(n)一一对应的.N越大,DFT的包络线越接近FT,当N足够大,可用DFT 进行谱分析,DFT的物理意义:DFT与FT的关系:X(k)是x(n)的频谱X(e j)在0,2上的 N点等间隔采样,采样间隔2/N.即对序列频谱的离散化.DFT与ZT的关系:X(k)是x(n)的Z变换X(Z)在单位圆上N点等间隔采样.对序列的傅里叶变换进行频域抽样时,自 然可以看作是对单位圆上的 Z变换进行抽样.表达式如下,设序列x(n)的
4、长度为N，其Z变换和DFT分别为：,比较上面二式可得关系式,离散频率、数字频率和模拟频率间的关系,模拟频率,离散频率,或，分别表示模拟频率与模拟角频率。单位分别为赫兹（Hz）和弧度/秒（rad/s）。两者关系为：,离散频率、数字频率和模拟频率间的关系,数字频率,它是将离散（信号数字）频率 离散化后的结果，用 表示。，因此可得出离散频率、数字频率 和模拟频率 之间的对应关系为：,以上所讨论的三种频率变量之间的关系，在对模拟信号进行数字处理以及利用模拟滤波器设计数字滤波器乃至整个数字信号处理中十分重要，望同学们高度重视。,3.1.2 DFT的隐含周期性-DFT与 DFS的关系 DFT变换对中，x(
5、n)与X(k)均为有限长序列,但由于WknN的周 期性，都隐含周期性，且周期均为N。有 限 长 序 列 是 取 周 期 序 列 的 一 个 周 期 来 表 示.周期序列 与有限长序列x(n)的转化:x(n),周期延拓,为了以后叙述方便，将(3.1.5)式用如下形式表示：,N(n)=x(n)N，,N(k)=X(k)N，,文字说明,图 3.1.2 有限长序列及其周期延拓,对任意整数m，总有 均为整数 因此:X(k)x(n)隐含周期性 X(k)满足 同理可证明x(n+mN)=x(n)DFT是 DFS的主值区间,x(n),X(k),DFS,DFT,公式说明,如果x(n)的长度为N，且(n)=x(n)N
6、，则可写 出(n)的离散傅里叶级数表示为,取主值区间,DFS对,DFT对,公式说明,式(3.1.5)(3.1.8)说明了DFT和DFS之间的关系。这些关系式成立的条件是N M，即DFT的变换区间N不能小于x(n)的长度M。如果该条件不满足，按照式(3.1.5)将x(n)进行延拓时，中将发生时域混叠，由式(3.1.8)得到的X(k)不再是x(n)的DFT，这时以上讲的DFS和DFT之间的关系不再成立,M为整数,M为整数,重要公式,(n)=x(n)N，,式中x(n)N表示x(n)以N为周期的周期延拓序列，(n)N 表示n对N求余，即如果 n=MN+n1，0n1N-1，M为整数，则(n)N=n1 例
7、如,则有,3.1.3 DFT的矩阵表示,周期序列 的DFS以及有限长序列x(n)的DFT如下可以发现它们右边的函数形式一样，当然k的定义域不同，X(k)只是 的主值区序列，或者说X(k)以N为周期进行周期延拓即是,返回,也可以表示成矩阵形式式中，X 是N点DFT频域序列向量:x是时域序列向量:DN称为N点DFT矩阵，定义为,(3.1.12),返回,回到本节,也可以表示为矩阵形式:称为N点IDFT矩阵，定义为从式(3.1.12)和式(3.1.14)，我们可以发现,(3.1.14),返回,回到本节,3.2 离散傅里叶变换的基本性质,1 线性性质 如果x1(n)和x2(n)是两个有限长序列，长度分别
8、为N1和N2。y(n)=ax1(n)+bx2(n)式中a、b为常数，即N=maxN1,N2，则y(n)的N点DFT为Y(k)=DFTy(n)=aX1(k)+bX2k,0kN-1(3.2.1)其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。若N1N2，则N=N2,那么需将x1(n)补上N2-N1个零值点后变成长度为N序列,然 后 都 作N点的 DFT.,2、X(k)x(n）隐含周期性,取整数,由于,3 循环移位性质（1）.移位线 性 移 位：序 列 沿 坐 标 轴 的 平 移序列的循环移位(圆周移位)设x(n)为有限长序列，长度为N，则x(n)的m 点循环移位定义为 表示将序
9、列 x(N)以N为周期进行周其延拓，再左移m 个单位，并取主值区间序列,图 3.2.1 循环移位过程示意图,有限长序列循环移位的 实现步骤,序列点数不够时补零,补到所需的N点,延拓为周期序列,移位,取主值区间,(2).时域循环移位定理 设N点 有限长序列x(n)的 DFTx(n)=X(k)0kN-1则 DFTx(n+m)NRN(n)=WN-kmX(k)证明:,令n+m=n，则有,因为式中x(n)NW knN，以N为周期，所以对其在任一个周期上求和的结果不变。,(3).频域循环移位定理设频域N点有限长序列X(k)0kN-1,则,4 循环卷积定理,卷 积线性卷积循环卷积(圆周卷积)圆周卷积与线性卷
10、积的对比线卷积：反折、平移、相乘、积分（或相加）圆卷积：循环反折、循环平移、相乘、相加,线性卷积,线 性 卷 积 定 义：有 限 长 序 列x1(n),0nN1-1;x2(n),0nN1-1则 线 性 卷 积 为 注意:线 性 卷 积 结 果 长 度 变 为 N1+N2-1.,反转移位,循环卷积(圆 周 卷 积),有限长序列x(n)和h(n)，长度分别为N和M,，循环卷积定义为,且圆 周 卷 积 结 果 长 度 不 变,为 L.,即循环卷积亦满足交换律。,循环反转循环移位,式中，L称为循环卷积的长度，L=max N，M。为了区别线性卷积，用 表示循环卷积，用 表示L点循环卷积，即 h(n)。,
11、循环卷积(圆 周 卷 积)的 实 现 步 骤,循环反转,循环移位,比较x(n)h(n)线性卷积 和 循环卷积(圆周卷积)的不同,线性卷积与圆周卷积步骤比较1,线性卷积：圆周卷积：(L=7)补零加长,2,3,1,x(m),5,4,m,0,N=5,2,3,1,x(m),5,4,0,L=7,m,(1),线性卷积与圆周卷积步骤比较2,2,3,1,h(m),0,m,(2)线卷积无需周期延拓，而圆周卷积需进行周期延拓：,线卷积的反折：圆卷积的反折(并取主值区间：,2,3,1,2,3,1,2,3,1,h(-m),m,0,7,线性卷积与圆周卷积步骤比较3,(3)平移,2,3,1,h(1-m),m,0,2,3,
12、1,h(1-m),m,0,（4）相乘x(m)h(-m)=51=5x(m)h(1-m)=5*2+4*1=14x(m)h(2-m)=5*3+4*2+3*1=26,2,3,1,x(m),5,4,m,0,2,3,1,x(m),5,4,0,N=7,m,x(m)h(3-m)=4*3+3*2+2*1=20 x(m)h(4-m)=3*3+2*2+1*1=14x(m)h(5-m)=2*3+1*2=8x(m)h(6-m)=1*3=3,线性卷积与圆周卷积步骤比较4,(5)相加得到线性卷积的示意图,相加得到圆周卷积的示意图,14,26,5,n,y(n),20,14,8,3,0,14,26,5,n,y(n),20,14
13、,8,3,0,可见,线性卷积与圆周卷积相同(当NN(5)+M(3)-1=7时),线性卷积与圆周卷积步骤比较5,若圆周卷积取长度为L=5,则求圆周卷积,2,3,1,x(m),5,4,0,N=5,m,2,3,1,h(-m),m,0,求得圆周卷积x(m)h(-m)=5*1+2*3+1*2=13x(m)h(1-m)=5*2+4*1+1*3=17x(m)h(2-m)=5*3+4*2+3*1=26,x(m)h(3-m)=4*3+3*2+2*1=20 x(m)h(4-m)=3*3+2*2+1*1=14看出圆卷积与线卷积不同.,17,13,26,y(n),n,0,20,14,有限长序列循环卷积的矩阵形式上式中
14、右边第一个矩阵称为x(n)的L点循环矩阵，它的特点是：(a)第一行是x(n)的L点循环倒相。x(0)不动，后面其它反转180放在他的后面。(b)第二行是第一行向右循环移一位；(c)第三行是第二行向右循环移一位；依次类推。,返回,例3.2：计算下面给出的两个长度为4的序列h(n)与x(n)的4点和8点循环卷积。解:按照式(3.2.21)写出h(n)与x(n)的4点循环卷积矩阵形式为,返回,周期延拓反折移动,h(n)与x(n)的8点循环卷积矩阵形式为,返回,时域卷积-频域相乘频域卷积-时域相乘(自已证),(2)循环卷积定理,时域卷积-频域相乘 证明：直接对上式两边进行DFT,令n-m=n，则有,因
15、为上式中x2(n)NW knN，以N为周期，所以对其在任一个周期上求和的结果不变。因此,用时域循环卷积定理计算两个序列循环卷积运算的方框图如下图所示,图3.2.3 用DFT计算两个有限长序列L点循环卷积运算的方框图,5离散巴塞伐尔定理,设长度为N的序列x(n)的N点DFT为X(k)，则,6 复共轭序列的DFT 设x*(n)是x(n)的复共轭序列，长度为N 且X(k)=DFTx(n)则 DFTx*(n)=X*(N-k),0mN-1(3.2.6)且 X(N)=X(0)类似的(3.2.7),证明：根据DFT的唯一性，只要证明(3.2.6)式右边等于左边即可，将DFT定义式中的K 用N-K代替，并取共
16、轭,又由X(K)的隐含周期性有X(N)=X(0)用同样的方法可以证明,7 DFT的共轭对称性,回顾:(1)序列的对称性a.奇 对 称(序 列)和 偶 对 称(序 列)xe(n)=xe(-n)x0(n)=-x0(-n)b.(DFT有限长)圆 周 奇 对 称(序 列)和 圆 周 偶 对 称(序 列)xep(n)=xep(N-n)xop(n)=-xop(N-n)c.共 轭 对 称(序列)和 共 轭 反 对 称(序 列)xe(n)=x*e(-n)xo(n)=-x*o(-n)d.(DFT有限长)圆 周 共 轭 对 称(序列)和 圆 周 共 轭 反 对 称(序 列)xep(n)=xep*(N-n)xop(
17、n)=-xop*(N-n),复,可见：a,c一般序列的对称指 对坐标原点的对称，而b,d圆周或DFT变换对有限长序列的对称是对 变称区间的中心 的对称,(2)序列的对称分量 x(n)=xo(n)+xe(n).a.奇 对 称 分 量 和 偶 对 称 分 量b.(DFT有限长)圆 周 奇 对 称 分 量 和 圆 周 偶 对 称 分 量 c.共 轭 对 称 分 量 和 共 轭 反 对 称 分 量d.(DFT有限长)圆 周 共 轭 对 称 分 量 和 圆 周 共 轭 反 对 称 分量,（1）.有限长 共轭对称 序列和共轭反对称 序列分别满足下式的称为有限长共轭对称序列和共轭反对称序列 xep(n)=x
18、*ep(N-n),0nN-1(3.2.9)xop(n)=-x*op(N-n),0nN-1(3.2.10),当N为偶数时，将上式中的n换成N/2-n可得到,图 3.2.3 共轭对称与共轭反对称序列示意图,图中*表示对应点为序列取共轭后的值。,任何有限长序列x(n)都可以表示成其共轭对称分量和共轭反对称分量之和，即 x(n)=xep(n)+xop(n),0nN-1 将上式中的n换成N-n，并取复共轭，得到 x*(N-n)=x*ep(N-n)+x*op(N-n)=xep(n)-xop(n)xep(n)=1/2x(n)+x*(N-n)(3.2.13)xop(n)=1/2x(n)-x*(N-n)(3.2
19、.14),(2)DFT的共轭对称性(奇偶虚实),(a),(b),复,(c)实信号的DFT共轭对称性,证明,证明,说明,设 x(n)=xr(n)+jxi(n)其中 xr=Rex(n)=1/2x(n)+x*(n)jxi(n)=jImx(n)=1/2x(n)-x*(n)可得 DFTxr(n)=1/2DFTx(n)+x*(n)=1/2X(k)+X*(N-k)=Xep(k)DFTjxi(n)=1/2DFTx(n)-x*(n)=1/2X(k)-X*(N-k)=Xop(k),由DFT的线性性质即可得 X(k)=DFTx(n)=Xep(k)+Xop(k)其中 Xep(k)=DFTxr(n),X(k)的共轭对称
20、分量 Xop(k)=DFTjxi(n),X(k)的共轭反对称分量,设 x(n)=xep(n)+xop(n)，0nN-1 其中 xep(n)=1/2x(n)+x*(N-n),x(n)的共轭对称分量 xop(n)=1/2x(n)-x*(N-n),x(n)的共轭反对称分量可得 DFTxep(n)=1/2DFTx(n)+x*(N-n)=1/2X(k)+X*(k)=ReX(k)DFTxop(n)=1/2DFTx(n)-x*(N-n)=1/2X(k)-X*(k)=jImX(k)因此 X(k)=DFTx(n)=XR(k)+jXI(k)其中 XR(k)=ReX(k)=DFTxep(n)jXI(k)=jImX(
21、k)=DFTxop(n),设x(n)是长度为N的实序列，且X(k)=DFTx(n)，则(a)X(k)=X*(N-k),0kN-1(3.2.19)(b)如果 x(n)实偶对称,即 x(n)=x(N-n)则X(k)实偶对称,即 X(k)=X(N-k)(3.2.20)(c)如果x(n)实奇对称,即 x(n)=-x(N-n)，则X(k)纯虚奇对称，即X(k)=-X(N-k)(3.2.21),利用DFT的共轭对称性，通过计算一个N点DFT，可以得到两个不同实序列的N点DFT，设x1(n)和x2(n)为两个实序列，构成新序列x(n)如下：x(n)=x1(n)+jx2(n)对x(n)进行DFT，得到 X(k
22、)=DFTx(n)=Xep(k)+Xop(k)Xep(k)=DFTx1(n)=1/2X(k)+X*(N-k)Xop(k)=DFTjx2(n)=1/2X(k)-X*(N-k)所以X1(k)=DFTx1(n)=1/2X(k)+X*(N-k)X2(k)=DFTx2(n)=-j1/2X(k)-X*(N-k),应用:,例：已知实序列x(n),y(n)的DFT 分别为X(k),Y(k),试给出一种计算 IDFT 就可得到 x(n),y(n)的计算方法。,解：令 w(n)=x(n)+jy(n),W(k)=DFT(w(n)w(n)=IDFT(W(k)所以，分别取Re(w(n),Im(w(n),3.3 频域采样
23、定理,将阐明：（1）FT变换、z变换与DFT的关系，在此基础上引出频域采样的概念，（2）频域采样理论（频域采样不失真条件）（3)频域内插公式,X(z)X(ejw),x(n),X(k),xN(n),采样,?,IDFT,分析频域采样,时域如何变换,(n),关系如下:,?,在单位圆上对X(z)等间隔采样N点得到,设任意序列x(n),在区间0,2 对 X(ejw)等间隔N点采样或,xN(n)=IDFTX(k)，0nN-1,实质上，是对x(n)的频谱函数 的等间隔采样。因为 以2为周期，所以 是以N为周期的频域序列,即,推导,由DFT与DFS的关系可知，X(k)是xN(n)以N为周期的周期延拓序列(n)
24、的离散傅里叶级数系数 的主值序列，即,而,代入上式得,式中,为整数,其它k,所以,结论:将x(n)的频域函数X(ejw)，按每周期 N点抽样，得到一周期序列,而时域,得到变换结果,是原序列x(n)周期延拓的序列.如下关系即 频 域 按 每 周 期 N 点 抽 样,时 域 便 按 N 点 周 期 延 拓.,由该式可知：是原序列 的周期延拓，周期为N，然后取主值。,频域抽样不失真条件 结论：如果序列x(n)的长度为L，则只有当频域采样点数NL时，才有 xN(n)=IDFTX(k)=x(n)可由频域采样X(k)恢复原序列，否则产生时域混叠现象。这就是所谓的频域采 样+定理。,返回,用频域采样X(k)
25、表示X(z)的内插公式和内插函数,频域内插公式,（1）内插公式,（2）内插函数,所谓频域内插公式，就是用频域采样 表示X(z)和。频域内插公式是FIR数字滤波器的频率采样结构和频率采样设计法的理论依据。,推导,恢复原序列:时域上恢复x(n),频域上恢复X(z)X(ejw)从 频 域 抽 样 不 失 真 条 件 可 以 知 道：N 个 频 域 抽 样 X(k)能 不 失 真 的 还 原 出 长 度 为 N 的 有 限 长 序 列 x(n)。那 么 用 N 个 X(k)也 一 定 能 完 整 地 表 示 出 X(z)以 及 频 率 响 应 即 单 位 圆 上 的 X(z).其过 程:先 由N 个
26、X(k)作 IDFT 得 到 x(n),再 把 x(n)作 Z 变 换 便 得 到 X(z).,设序列x(n)长度为M，在频域02之间等间隔采样N点，NM，则有,序列,，所以,的z变换为,由于,将上式代入X(z)的表示式中得,上式中W-kN N=1，因此,内插函数,用X(k)表示X(z)的内插公式,当z=ej时，就成为x(n)的傅里叶变换X(ej)的内插函数和内插公式，即,进一步化简可得,(3.3.7),(3.3.8),内插函数零极点与（）的幅频特性示意图,内插公式,内插函数零极点与（）的幅频特性示意图,解：,例：已知序列x(n)=-1,-1,4,3,n=0,1,2,3,对其频谱采样，采样频率
27、点 的取样值为X（k），求IDFT(X(k),解：x(n)=,-1,4,2，-1,4,2,-1,-1,4,3,-1,-1,4,3,-1,-1,4,3,2,-1,4,2，-1,4,2,3.5 DFT的应用举例,DFT的快速算法FFT的出现，使DFT在数字通信、语言信号处理、图像处理、功率谱估计、仿真、系统分析、雷达理论、光学、医学、地震以及数值分析等各个领域都得到广泛应用。以下面两点为基础 卷积和相关系数运算 作连续傅里叶变换的近似,仅介绍DFT在线性卷积和频谱分析两方面的应用。本节主要论述：,3.5.1 用DFT（FFT）计算两个有限长序列的线性卷积,3.5.2 用DFT计算有限长序列与无限长
28、序列的线性卷积,3.5.3 用DFT对序列进行谱分析,3.5.1 用DFT计算两个有限长序列线性卷积,时域循环卷积,频域是两序列的 DFT相乘.时频两域的转换(即 DFT 及 IDFT)有快速 傅里叶变换(FFT)算法.所以利用循环卷积定理计算循环卷积比计算卷积的计算速度快得多.实际问题中:即信号通过线性时不变系统h(n)后的响应y(n)是线 性卷积运算.思考：若做卷积的两序列都是有限长序列,能否用它们的圆周卷积结果代替它们的线性卷积结果呢?即圆周卷积与线性卷积的关系是什么?,圆周卷积,循环卷积定理:Y(k)=DFTy(n)=X1(k)X2(k),0kL-1,0kL-1,用DFT计算循环卷积框
29、图,圆周卷积与线性卷积相同的条件:LN+M-1,:假设h(n)和x(n)都是有很长序列，长度分别是N和M。其线性卷积和循环卷积分别表示如下：,推导,圆周卷积与线性卷积的关系:,其中，LmaxN,M,对照线性卷积式可以看出，上式中,(3.4.3),周期延拓,线性卷积,x1(n)与x2(n)的L点圆周卷积结果是其线性卷积结果yL(n)以L点周期延拓后再取主值序列.如 L取适当值LN+M-1,则线性卷积结果yL(n)被L点周期延拓后无混叠。即其主值序列=线性卷积结果,从而实现圆周卷积代替线性卷积.即当L N1+N2-1时，圆周卷积可以代替线性卷积即：,从,看出,图 3.4.2 线性卷积与循环卷积,图
30、 3.4.3 用DFT计算线性卷积框图,线性卷积,3.5.2 用DFT计算有限长序列与无限长序列的线性卷积,用FFT计算有限长序列与无限长序列的线性卷积 问题：h(n)为某滤波器的单位脉冲响应,长度有限 输入信号 x(n)很长，h(n)要补许多零再进行计算,计算量有很大的浪费 解决方法：重叠相加法 重叠保留法 重叠相加法：将x(n)分段，每段长度为M，然后依次计算各段与h(n)的卷积，再由各段的卷积结果得到y(n)。,返回,回到本节,设序列h(n)长度为N，x(n)为无限长序列。将x(n)均匀分段，每段长度取M，则,于是，h(n)与x(n)的线性卷积可表示为,(3.4.4),图 3.4.4 重
31、叠相加法卷积示意图,3.5.3 用DFT对序列进行谱分析,本节只讨论序列的频谱分析，连续信号的谱分析下章介绍。理论依据：序列的N点DFT就是序列的频谱函数在频率区间 上的N点等间隔采样。具体方法:(1)根据频率分辨率要求确定DFT变换区间长度N：在数字频率域，如果要求频率分辨率为D弧度，而N点DFT意味着频谱采样间隔为2/N，即DFT能够实现的频率分辨率为2/N，因此要求2/ND，即。另外为满足基2FFT对点数N的要求，一般取(M为 正整数)。(2)计算x(n)的N点DFT，并绘制频谱图。,回到本节,例:假设，用DFT分析x(n)的频谱，频率分辨率为0.02，要求画出幅频特性曲线和相频特性曲线
32、。解:(1)根据频率分辨率求N。因为2/N0.02,即N100,取N=100。(2)计算x(n)的N点DFT:,回到本节,的幅频特性和相频特性曲线如下图(a)和(b)所示。由上图可见，x(n)的频谱变化很缓慢，所以用DFT对该信号进行谱分析时，频率分辨率可以再低一些(即N小一些)也可以得到正确的频谱。当N=16时，频率分辨率为/8，幅频特性和相频特性曲线如图3.5.4(c)和(d)所示，与N=100的情况相差很小。,回到本节,课后习题,例1、求以下有限长序列的N点DFT（闭合表达式）。,直接用DFT公式求解X(k),图 3.1.1 X(k)与X(e j)的关系,当 为正整数,例2 实序列x(n)的8点DFT，前5个 值 0.25,0.125-j0.3,0,0.125-j0.5,0,（1）求X(k)的其它三个值,解：x(n)是实序列-X(k)共轭对称X*(N-k)=X(k),X(5)=X*(8-5)=X*(3)=0.125+j0.5X(6)=X*(2)=0X(7)=X*(1)=0.125+j0.3,(2),(3),因为,
