离散傅里叶变换(DFT).ppt

第三章 离散傅里叶变换DFT 引言 3.1 离散傅里叶变换(DFT)的定义 3.2 离散傅里叶变换的基本性质 3.3 频域采样 3.4 DFT快速算法FFT 3.5 DFT的应用举例 第3章 离散傅里叶变换(DFT)及其快速算 法（FFT） 第三章 离散傅里叶变换DFT 引言 DFT与FT区别 FT: 序列的付里叶变换,时频对应关系 DFT: 序列的FT的有限点采样. 也可以直接定义 即DFT 是FT的N点等间隔采样 -频域采样定理 频域采样 时域周期重复 -N越大,DFT包络线越逼近FT DFT变换的意义:FT是连续谱,采样离散化后便于计算 机处理 DFT的定义、性质及频域采样定理、FFT及其应用 第三章 离散傅里叶变换DFT 3.1 离散傅里叶变换的定义 DFT定义 DFT与Z变换及FT的关系: DFT的物理意义 DFT的周期性: -DFT与DFS的关系 DFT是DFS的主值区间 DFT 的矩阵表示 回到本节 第三章 离散傅里叶变换DFT 3.1 离散傅里叶变换的定义 3.1.1 DFT的定义 设x(n)是一个长度为M的有限长序列， 则定义x(n)的N点 离散傅里叶正变换为 离散傅里叶逆变换为 离散傅里叶变换对 式中式中 ， N N称为称为DFTDFT变换区间长度变换区间长度NMNM，可见可见： DFTDFT使有限长使有限长时域离散序列时域离散序列与有限长与有限长频域离散序列频域离散序列建立起建立起 对应关系对应关系 回到本节 第三章 离散傅里叶变换DFT 例例 1 1 已知 ，分别求 和 时的 。 解： 由该例可知：频率采样点数不同，DFT的长度不同， DFT 的结果也不同。 第三章 离散傅里叶变换DFT 图 3.1.1 X(k)与X(e j)的关系 第三章 离散傅里叶变换DFT 例2 ： ，分别计算x(n)的8点、16点DFT。 解: x(n)的8点DFT为 x(n)的16点DFT为 返回 回到本节 第三章 离散傅里叶变换DFT 是 在频率区间上的等间隔采样 返回 回到本节 第三章 离散傅里叶变换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变换进行抽样. 表达式如下表达式如下 第三章 离散傅里叶变换DFT 设序列x(n)的长度为N， 其Z变换和DFT分别为： 比较上面二式可得关系式 第三章 离散傅里叶变换DFT 离散频率、数字频率和模拟频率间的关系 模拟频率 离散频率离散频率 或或 ，分别表示，分别表示模拟频率模拟频率与与模拟角频率模拟角频率。单位分。单位分 别为赫兹（别为赫兹（HzHz）和弧度）和弧度/ /秒（秒（rad/srad/s）。两者关系为：）。两者关系为： ，单位为弧度（，单位为弧度（radrad）。通过采样信号的频谱，可建）。通过采样信号的频谱，可建 立模拟频率与离散（信号数字）频率之间的关系：立模拟频率与离散（信号数字）频率之间的关系： 的取值范围： 对应于模拟频率能取的最高频率对应于模拟频率能取的最高频率 就是离散（信号数字）频率能取的最高频率 此时，虽然信号在时域时离散的，但 仍然是连续的 注意 第三章 离散傅里叶变换DFT 离散频率、数字频率和模拟频率间的关系离散频率、数字频率和模拟频率间的关系 数字频率数字频率 它是将它是将离散（信号数字）频率离散（信号数字）频率 离散化后的结果，用离散化后的结果，用 表示。表示。 ，因此可得出离散频率，因此可得出离散频率 、数字频数字频 率率 和模拟频率和模拟频率 之间的对应关系为：之间的对应关系为： 以上所讨论的三种频率变量之间的关系，在对模 拟信号进行数字处理以及利用模拟滤波器设计数 字滤波器乃至整个数字信号处理中十分重要，望 同学们高度重视。 回到本节 第三章 离散傅里叶变换DFT 3.1.2 DFT的隐含周期性- DFT与 DFS的关系 DFT变换对中，x(n)与X(k)均为有限长序列,但由于WknN的周 期性， 都隐含周期性， 且周期均为N。 有 限 长 序 列 是 取 周 期 序 列 的 一 个 周 期 来 表 示 . 周期序列 与有限长序列x(n)的转化: x(n) 周期延拓 取一个周期x(n) 为了以后叙述方便， 将(3.1.5)式用如下形式表示： N(n)=x(n)N， N(k)=X(k)N， 文字说明文字说明 第三章 离散傅里叶变换DFT 图 3.1.2 有限长序列及其周期延拓 第三章 离散傅里叶变换DFT 对任意整数m， 总有 均为整数 因此: X(k) x(n) 隐含周期性 X(k)满足 同理可证明x(n+mN)=x(n) DFT是 DFS的主值区间 x(n) X(k) DFS DFT 公式说明公式说明 第三章 离散傅里叶变换DFT 如果x(n)x(n)的的长度为长度为N N， 且 (n)=x(n)N， 则可写 出 (n)的离散傅里叶级数表示为 取主值区间 DF S对 DF T对 公式说明公式说明 式(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之间的关系不再成立 第三章 离散傅里叶变换DFT M为整数 M为整数 重要公式 (n)=x(n)N， 第三章 离散傅里叶变换DFT 式中x(n)N表示x(n)以N为周期的周期延拓序列， (n)N 表示n对N求余， 即如果 n=MN+n1， 0n1N-1， M为整数， 则 (n)N=n1 例如 则有 回到本节 第三章 离散傅里叶变换DFT 3.1.3 DFT的矩阵表示 周期序列 的DFS以及有限长序列x(n)的DFT如下 可以发现它们右边的函数形式一样，当然k的定义域不同， X(k)只是 的主值区序列，或者说X(k)以N为周期 进行周期延拓即是 返回 回到本节 第三章 离散傅里叶变换DFT 也可以表示成矩阵形式 式中，X 是N N点DFT频域序列向量: x是时域序列向量向量: DN称为N点DFT矩阵，定义为 (3.1.12) 返回 回到本节 第三章 离散傅里叶变换DFT 也可以表示为矩阵形式: 称为N点IDFT矩阵，定义为 从式(3.1.12)和式(3.1.14)，我们可以发现 (3.1.14) 返回 回到本节 第三章 离散傅里叶变换DFT 3.2 离散傅里叶变换的基本性质 1 线性性质 如果x1(n)和x2(n)是两个有限长序列，长度分别为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。 若N1频域相乘 频域卷积-时域相乘(自已证) (2)循环卷积定理 第三章 离散傅里叶变换DFT 时域卷积-频域相乘 证明： 直接对上式两边进行DFT 令令n-m=nn-m=n， 则有 第三章 离散傅里叶变换DFT 因为上式中x2(n)NW knN， 以N为周期， 所以对 其在任一个周期上求和的结果不变。 因此 用时域循环卷积定理计算两个序列循环卷积运算的方 框图如下图所示 图3.2.3 用DFT计算两个有限长序列L点循环卷积运算的方框图 第三章 离散傅里叶变换DFT 5离散巴塞伐尔定理 设长度为N的序列x(n)的N点DFT为X(k)，则 第三章 离散傅里叶变换DFT 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 证明： 根据DFT的唯一性， 只要证明(3.2.6)式右边等于左边 即可，将DFT定义式中的K 用N-K代替，并取共轭 又由X(K)的隐含周期性有X(N)=X(0) 用同样的方法可以证明 第三章 离散傅里叶变换DFT 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(n) =-xop*(N-n) 实 复 可见：可见：a,ca,c一般序列的对称指一般序列的对称指 对坐标原点的对称，而对坐标原点的对称，而b,db,d圆周或圆周或 DFTDFT变换对有限长序列的对称是对变换对有限长序列的对称是对 变称区间的中心变称区间的中心 的对称的对称 第三章 离散傅里叶变换DFT (2) 序列的对称分量 x(n)= xo(n)+ xe(n). a.奇 对 称 分 量 和 偶 对 称 分 量 b. (DFT有限长)圆 周 奇 对 称 分 量 和 圆 周 偶 对 称 分 量 c.共 轭 对 称 分 量 和 共 轭 反 对 称 分 量 d. (DFT有限长)圆 周 共 轭 对 称 分 量 和 圆 周 共 轭 反 对 称 分量 第三章 离散傅里叶变换DFT （1）. 有限长 共轭对称 序列和共轭反对称 序列 分别满足下式的称为有限长共轭对称序列和共轭反对 称序列 xep(n)=x*ep(N-n), 0nN-1 (3.2.9) xop(n)=-x*op(N-n), 0nN-1 (3.2.10) 当N为偶数时， 将上式中的n换成N/2-n可得到 第三章 离散傅里叶变换DFT 图 3.2.3 共轭对称与共轭反对称序列示意图 图中*表示对应点为序列取共轭后的值。 第三章 离散傅里叶变换DFT 任何有限长序列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.14) 第三章 离散傅里叶变换DFT (2 )DFT的共轭对称性 (奇偶虚实) x(n)= xr(n) + jxi(n) X(k)=Xep(k)+Xop(k) x(n)= xep(n) + xop(n) X(k)=XR(k)+jXI(k) (a) (b) 复 (c) 实信号的DFT共轭对称性 证明 证明 说明 第三章 离散傅里叶变换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 由DFT的线性性质即可得 X(k)=DFTx(n)=Xep(k)+Xop(k) 其中 Xep(k)=DFTxr(n) , X(k)的共轭对称分量 Xop(k)=DFTjxi(n) , X(k)的共轭反对称分量 第三章 离散傅里叶变换DFT 设 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(k)=DFTxop(n) 第三章 离散傅里叶变换DFT 设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 利用DFT的共轭对称性， 通过计算一个N点DFT， 可以得到两个不同实序列的N点DFT， 设x1(n)和x2(n) 为两个实序列， 构成新序列x(n)如下 ： x(n)=x1(n)+jx2(n) 对x(n)进行DFT， 得到 X(k)=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) 应用: 回到本节 第三章 离散傅里叶变换DFT 例：已知实序列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) 第三章 离散傅里叶变换DFT 3.3 频域采样定理 问题的提出： 时域： 通过满足“时域采样定理”的采样 频域： ？ 回到本节 将阐明： （1）FT变换、z变换与DFT的关系，在此基础上引出频域采样 的概念， （2）频域采样理论（频域采样不失真条件） （3)频域内插公式 第三章 离散傅里叶变换DFT X(z) X(ejw)x(n) X(k)xN(n) 采 样 ? IDFT 分析频域采样,时域如何变换 (n) 关系如下: ? 第三章 离散傅里叶变换DFT 在单位圆上对X(z)等间隔采样N点得到 设任意序列x(n) 在区间0, 2 对 X(ejw) 等间隔N点采样或 xN(n)=IDFTX(k)， 0nN-1 实质上， 是对x(n)的频谱函数 的等间隔采样。因 为 以2为周期，所以 是以N为周期的频域序列,即 第三章 离散傅里叶变换DFT 由DFT与DFS的关系可知， X(k)是xN(n)以N为周 期的周期延拓序列 (n)的离散傅里叶级数系数 的 主值序列， 即 而 第三章 离散傅里叶变换DFT 代入上3.3.1式得 式中 为整数 其它k 所以 第三章 离散傅里叶变换DFT 结论: 将x(n)的频域函数X(ejw)，按每周期 N点抽样，得到一周 期序列 , 而时域,得到变换结果 ,是原序列x(n) 周期延拓的序列.如下关系 即 频 域 按 每 周 期 N 点 抽 样, 时 域 便 按 N 点 周 期 延 拓. 由该式可知：由该式可知： 是原序列是原序列 的周期延拓，周期为的周期延拓，周期为N N， 然后取主值。然后取主值。 第三章 离散傅里叶变换DFT 频域抽样不失真条件 结论：如果序列x(n)的长度为L， 则只有当频域采样 点数NL时， 才有 xN(n)=IDFTX(k)=x(n) 可由频域采样X(k)恢复原序列， 否则产生时域混 叠现象。 这就是所谓的频域采 样+定理。 第三章 离散傅里叶变换DFT 返回 第三章 离散傅里叶变换DFT 用频域采样X(k)表示X(z)的内插公式和内插函数 频域内插公式 （1）内插公式 （2）内插函数 所谓频域内插公式，就是用频域采样 表示X(z)和 。 频域内插公式是FIR数字滤波器的频率采样结构和频率采样 设计法的理论依据。 第三章 离散傅里叶变换DFT 推导 恢复原序列:时域上恢复x(n), 频域上恢复X(z) X(ejw) 从 频 域 抽 样 不 失 真 条 件 可 以 知 道： N 个 频频 域域 抽抽 样样 X(k)X(k) 能 不 失 真 的 还 原 出 长 度 为 N 的 有 限 长 序 列 x(n)。 那 么 用 N 个 X(k) 也 一 定 能 完 整 地 表 示 出 X(z) 以 及 频 率 响 应 即 单 位 圆 上 的 X(z). 其过其过 程程: : 先 由N 个 X(k) 作 IDFT 得 到 x(n), 再 把 x(n) 作 Z 变 换 便 得 到 X(z). 第三章 离散傅里叶变换DFT 设序列x(n)长度为M， 在频域02之间等间隔采样N点， NM， 则有 序列 ，所以 的z变换为 由于 第三章 离散傅里叶变换DFT 将上式代入X(z)的表示式中得 上式中W-kN N=1， 因此 内插 函数 用X(k)表示X(z)的内插公式 第三章 离散傅里叶变换DFT 当z=ej时，就成为x(n)的傅里叶变换X(ej)的内插函数和 内插公式， 即 进一步化简可得 (3.3.7) (3.3.8) 回到本节 第三章 离散傅里叶变换DFT 内插函数零极点与（）的幅频特性示意图 内插公式内插公式 内插函数零极点与内插函数零极点与（ ）的幅）的幅频频频频特性示意特性示意图图图图 第三章 离散傅里叶变换DFT 例：已知 ，对 在单位 圆上等间隔采样N点 解： 第三章 离散傅里叶变换DFT 例：已知序列x(n)=-1, -1, 4, 3, n=0, 1, 2, 3, 对其频谱 采样， 采样频率点 的取样值为 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, 第三章 离散傅里叶变换DFT 3.5 DFT的应用举例 DFT的快速算法FFT的出现， 使DFT在数字通信、 语言信号处理、 图像处理、 功率谱估计、 仿真、 系 统分析、 雷达理论、 光学、 医学、 地震以及数值分 析等各个领域都得到广泛应用。以下面两点为基础 卷积和相关系数运算 作连续傅里叶变换的近似 回到本节 第三章 离散傅里叶变换DFT 仅介绍DFT在线性卷积和频谱分析两方面的应用。 本节主要论述： 返回 p 3.5.1 用DFT（FFT）计算两个有限长序列两个有限长序列的线性卷积 p 3.5.2 用DFT计算有限长序列与无限长序列的线性卷积 p 3.5.3 用DFT对序列进行谱分析 第三章 离散傅里叶变换DFT 3.5.1 用DFT计算两个有限长序列线性卷积 时域循环卷积,频域是两序列的 DFT相乘. 时频两域的转换 (即 DFT 及 IDFT)有快速 傅里叶变换 (FFT)算法. 所以利用循环卷积定理计算循环卷积比计算卷积的计算速 度快得多. 实际问题中: 即信号通过线性时不变系统h(n)后的响应y(n)是线 性卷积运 算. 思考：若做卷积的两序列都是有限长序列,能否用它们的 圆周卷积结果代替它们的线性卷积结果呢?即圆周卷积与 线性卷积的关系是什么? 第三章 离散傅里叶变换DFT 圆周卷积 循环卷积定理: Y(k)=DFTy(n)=X1(k)X2(k), 0kL-1 0kL-1 用DFT计算循环卷积框图 第三章 离散傅里叶变换DFT 圆周卷积与线性卷积相同的条件: LN+M-1 :假设h(n)和x(n)都是有很长序列， 长度分别是N和M。 其 线性卷积和循环卷积分别表示如下： 圆周卷积与线性卷积的关系: 第三章 离散傅里叶变换DFT 其中， LmaxN, M 对照线性卷积式可以看出， 上式中 (3.4.3) 周期延拓周期延拓 线性卷积线性卷积 第三章 离散傅里叶变换DFT x1(n)与x2(n)的L点圆周卷积结果是其线性卷积结果 yL(n)以L点周期延拓后再取主值序列. 如 L取适当值LN+M-1,则线性卷积结果yL(n)被L点周 期延拓后无混叠。即其主值序列=线性卷积结果,从而 实现圆周卷积代替线性卷积. 即当L N1+N2-1时，圆周卷积可以代替线性卷积即： 从 看出 第三章 离散傅里叶变换DFT 图 3.4.2 线性卷积与循环卷积 第三章 离散傅里叶变换DFT 图 3.4.3 用DFT计算线性卷积框图 线性卷积 返回 第三章 离散傅里叶变换DFT 3.5.2 用DFT计算有限长序列与无限长序列的线 性卷积 用FFT计算有限长序列与无限长序列的线性卷积 问题： h(n) 为某滤波器的单位脉冲响应,长度有限 输入信号 x(n)很长，h(n) 要补许多零再进行计算, 计算量有很大的浪费 解决方法： 重叠相加法 重叠保留法 重叠相加法： 将x(n)分段，每段长度为M，然后依次计算各段与h(n) 的卷积，再由各段的卷积结果得到y(n)。 返回 回到本节 第三章 离散傅里叶变换DFT 设序列h(n)长度为N， x(n)为无限长序列。 将x(n