离散傅里叶变换DFT.ppt

第三章DFT离散傅里叶变换 3 7抽样Z变换 频域抽样理论 3 8利用DFT对连续时间信号的逼近 3 6DFT的性质 3 5DFT 有限长序列的离散频域表示 3 3周期序列的DFS 3 4DFS的性质 3 2傅氏变换的几种可能形式 3 1引言 点击进入 目录 3 1引言 在第2章中讨论了序列的傅里叶变换和Z变换 由于数字计算机只能计算有限长离散序列 因此有限长序列在数字信号处理中就显得很重要 当然可以用Z变换和傅里叶变换来研究它 但是 这两种变换无法直接利用计算机进行数值计算 针对序列 有限长 这一特点 可以导出一种更有用的变换 离散傅里叶变换 DiscreteFourierTransform 简写为DFT 它本身也是有限长序列 作为有限长序列的一种傅里叶表示法 离散傅里叶变换除了在理论上相当重要之外 而且由于存在有效的快速算法 快速离散傅里叶变换 因而在各种数字信号处理的算法中起着核心作用 有限长序列的离散傅里叶变换 DFT 和周期序列的离散傅里叶级数 DFS 本质上是一样的 为了讨论离散傅里叶级数与离散傅里叶变换 我们首先来回顾并讨论傅里叶变换的几种可能形式 一 DFT是重要的变换1 分析有限长序列的有用工具 2 在信号处理的理论上有重要意义 3 在运算方法上起核心作用 谱分析 卷积 相关都可以通DFT在计算机上实现 返回目录 二 DFT是现代信号处理桥梁DFT要解决两个问题 一是离散与量化 二是快速运算 信号处理 DFT FFT 傅氏变换 离散量化 连续时间 连续频率 傅里叶变换 连续时间 离散频率 傅里叶级数 离散时间 连续频率 序列的傅里叶变换 离散时间 离散频率 离散傅里叶变换 3 2傅里叶变换的几种可能形式 一 连续时间 连续频率 傅里叶变换 FT 这是连续时间 非周期信号x t 的傅里叶变换 它得到连续的 非周期的频谱密度函数X j 二 连续时间 离散频率 傅里叶级数 FS 这是连续时间 周期信号x t 的傅立叶变换 它得到离散的 非周期的频谱密度函数X j 例如信号x t sin100 t只有一个频率分量 X jK 0 是频谱相邻两谱线间角频率的间隔 K为谐波序号 三 离散时间 连续频率 序列的傅里叶变换 DTFT 由第一章采样定理的知识 我们知道 时域离散 将导致频域周期化 且这个周期是 s 四 离散时间 离散频率 离散傅里叶变换 DFT 上面所讲的三种傅里叶变换至少在一个域内是连续的 不适于计算机运算 最好是时域和频域均为离散的 才方便用计算机运算 思路 从序列的傅里叶变换出发 若时域为离散的序列 则频域是连续周期的 若此时我们对频域的连续信号抽样 人为的使其离散化 这样 频域的离散又导致时域的周期化 于是有 四种傅里叶变换形式的归纳 各种形式的傅里叶变换 3 3周期序列的离散傅里叶级数 DFS 设是一个周期为N的周期序列 即 r为任意整数 周期序列不是绝对可和的 所以不能用Z变换表示 因为在任何z值下 其Z变换都不收敛 也就是 但是 正如连续时间周期信号可以用傅里叶级数表示一样 周期序列也可以用离散傅里叶级数来表示 该级数相当于成谐波关系的复指数序列 正弦型序列 之和 也就是说 复指数序列的频率是周期序列的基频 2 N 的整数倍 这些复指数序列ek n 的形式为 3 1 式中 k r为整数 由式 3 1 可见 复指数序列ek n 对k呈现周期性 周期也为N 也就是说 离散傅里叶级数的谐波成分只有N个独立量 这是和连续傅里叶级数的不同之处 后者有无穷多个谐波成分 因而对离散傅里叶级数 只能取k 0到N 1的N个独立谐波分量 不然就会产生二义性 因而可展成如下的离散傅里叶级数 即 3 2 式中 求和号前所乘的系数1 N是习惯上已经采用的常数 是k次谐波的系数 下面我们来求解系数 这要利用复正弦序列的正交特性 即 3 3 将式 3 2 两端同乘以 然后从n 0到N 1的一个周期内求和 则得到 把r换成k可得 3 4 这就是求k 0到N 1的N个谐波系数的公式 同时看出也是一个以N为周期的周期序列 即 这和离散傅里叶级数只有N个不同的系数的说法是一致的 可以看出 时域周期序列的离散傅里叶级数在频域 即其系数也是一个周期序列 因而与 是频域与时域的一个周期序列对 式 3 2 与式 3 4 一起可看作是一对相互表达周期序列的离散傅里叶级数 DFS 对 为了表示方便 常常利用复数量WN来写这两个式子 WN定义为 3 5 WN的性质 1 周期性 2 共轭对称性 3 可约性 4 正交性 使用WN 式 2 4 及式 2 2 可表示为 3 6 3 7 式中 DFS 表示离散傅里叶级数正变换 IDFS 表示离散傅里叶级数反变换 从上面看出 只要知道周期序列一个周期的内容 其他的内容也都知道了 所以 这种无限长序列实际上只有一个周期中的N个序列值有信息 因而周期序列和有限长序列有着本质的联系 例3 1设为周期脉冲串 3 8 因为对于0 n N 1 所以利用式 2 6 求出的DFS系数为 3 9 在这种情况下 对于所有的k值均相同 于是 将式 3 9 代入式 3 7 可以得出表示式 3 10 例3 2已知周期序列如图3 2所示 其周期N 10 试求解它的傅里叶级数系数 图3 2例3 2的周期序列 周期N 10 由式 3 6 3 11 这一有限求和有闭合形式 3 12 图3 3图3 2所示序列的傅里叶级数系数的幅值 式 3 6 中的周期序列可看成是对的第一个周期x n 作Z变换 然后将Z变换在Z平面单位圆上按等间隔角2 N采样而得到的 令 通常称x n 为的主值区序列 则x n 的Z变换为 3 13 把式 3 13 与式 3 6 比较可知 3 14 可以看出 当0 k N 1时 是对X z 在Z平面单位圆上的N点等间隔采样 在此区间之外随着k的变化 的值呈周期变化 图3 4画出了这些特点 由于单位圆上的Z变换即为序列的傅里叶变换 所以周期序列也可以解释为的一个周期x n 的傅里叶变换的等间隔采样 因为 3 15 比较式 3 15 和式 3 6 可以看出 这相当于以2 N的频率间隔对傅里叶变换进行采样 3 16 例3 3为了举例说明傅里叶级数系数和周期信号的一个周期的傅里叶变换之间的关系 我们再次研究图2 2所示的序列 在序列的一个周期中 3 17 则的一个周期的傅里叶变换是 3 18 可以证明 若将 2 k 10代入式 2 18 即 图3 5对图3 2所示序列的一个周期作傅里叶变换的幅值 图3 6图3 3和图3 5的重叠图 它表明一个周期序列的DFS系数等于主值区序列的傅里叶变换的采样 其中 a b为任意常数 3 4DFS的性质 一 线性 如果 则有 以下性质均在条件 x1 n 和x2 n 都是周期为N的周期序列 二 序列的移位 则有 如果 证明 令i m n 则n i m n 0时 i m n N 1时 i N 1 m 所以 和都是以N为周期的周期函数 三 调制特性如果则有 证明 时域乘以虚指数 的m次幂 频域搬移m 调制特性 四 周期卷积和 重点 1 如果则 周期卷积是线性卷积的周期延拓 Go 线性卷积的长度及周期卷积代替线性卷积的条件 GO 圆周卷积的定义及求解过程 GO 利用DFS求解线性卷积的步骤 Go 周期卷积的方法举例 说明它仍然是同周期的DFS并引导出与线性卷积的关系 nextpage 2 两个周期序列的周期卷积过程 1 画出和的图形 2 将翻摺 得到可计算出 返回目录 返回目录 012345 计算区 012345 012345 012345 012345 3 将右移一位 得到 可计算出 返回目录 返回目录 012345 012345 4 将再右移一位 得到可计算出 返回目录 5 以此类推 返回目录 n 计算区 返回目录 3 频域卷积定理如果 则 证明从略 3 5有限长序列离散傅里叶变换 DFT DFT的定义 上一节我们讨论的周期序列实际上只有有限个序列值有意义 因而它和有限长序列有着本质的联系 本节将根据周期序列和有限长序列之间的关系 由周期序列的离散傅里叶级数表示式推导得到有限长序列的离散频域表示即离散傅里叶变换 DFT 设x n 为有限长序列 长度为N 即x n 只在n 0到N 1点上有值 其他n时 x n 0 即 为了引用周期序列的概念 我们把它看成周期为N的周期序列的一个周期 而把看成x n 的以N为周期的周期延拓 即表示成 这个关系可以用图2 8来表明 通常把的第一个周期n 0到n N 1定义为 主值区间 故x n 是的 主值序列 即主值区间上的序列 而称为x n 的周期延拓 对不同r值x n rN 之间彼此并不重叠 故上式可写成 用 n N表示 nmodN 其数学上就是表示 n对N取余数 或称 n对N取模值 令 0 n1 N 1 m为整数 则n1为n对N的余数 例如 是周期为N 9的序列 则有 利用前面的矩形序列RN n 式可写成 同理 频域的周期序列也可看成是对有限长序列X k 的周期延拓 而有限长序列X k 可看成是周期序列的主值序列 即 我们再看表达DFS与IDFS 这两个公式的求和都只限定在n 0到N 1和k 0到N 1的主值区间进行 它们完全适用于主值序列x n 与X k 因而我们可以得到有限长序列的离散傅里叶变换的定义 0 k N 1 0 n N 1 x n 和X k 是一个有限长序列的离散傅里叶变换对 我们称上面第一式为x n 的N点离散傅里叶变换 DFT 称式第二式为X k 的N点离散傅里叶反变换 IDFT 已知其中的一个序列 就能唯一地确定另一个序列 这是因为x n 与X k 都是点数为N的序列 都有N个独立值 可以是复数 所以信息当然等量 此外 值得强调得是 在使用离散傅里叶变换时 必须注意所处理的有限长序列都是作为周期序列的一个周期来表示的 换句话说 离散傅里叶变换隐含着周期性 例1已知序列x n n 求它的N点DFT 解单位脉冲序列的DFT很容易由DFT的定义式 2 30 得到 k 0 1 N 1 n 的X k 如图2 9 这是一个很特殊的例子 它表明对序列 n 来说 不论对它进行多少点的DFT 所得结果都是一个离散矩形序列 图2 9序列 n 及其离散傅里叶变换 例2已知x n cos n 6 是一个长度N 12的有限长序列 求它的N点DFT 解由DFT的定义式 2 30 利用复正弦序列的正交特性 再考虑到k的取值区间 可得 图2 10有限长序列及其DFT 例3已知如下X k 求其10点IDFT 解X k 可以表示为 X k 1 2 k 0 k 9 写成这种形式后 就可以很容易确定离散傅里叶反变换 由于一个单位脉冲序列的DFT为常数 3 5DFT 有限长序列的离散频域表示一 预备知识1 余数运算表达式如果 m为整数 则有 此运算符表示n被N除 商为m 余数为 是的解 或称作取余数 或说作n对N取模值 或简称为取模值 n模N 返回目录 例如 1 2 返回目录 先取模值 后进行函数运作 而视作将周期延拓 2 返回目录 二 有限长序列x n 和周期序列的关系 周期序列是有限长序列x n 的周期延拓 有限长序列x n 是周期序列的主值序列 返回目录 如 N 1 n x n 0 0 N 1 定义从n 0到 N 1 的第一个周期为主值序列或区间 返回目录 三 周期序列与有限长序列X k 的关系 同样 周期序列是有限长序列X k 的周期延拓 而有限长序列X k 是周期序列的主值序列 返回目录 四 从DFS到DFT 从上式可知 DFS IDFS的求和只限定在n 0到n N 1 及k 0到N 1的主值区间进行 因此可得到新的定义 即有限序的离散傅氏变换 DFT 的定义 返回目录 或者 本节结束返回目录 3 6离散傅里叶变换的性质 本节讨论DFT的一些性质 它们本质上和周期序列的DFS概念有关 而且是由有限长序列及其DFT表示式隐含的周期性得出的 以下讨论的序列都是N点有限长序列 用DFT 表示N点DFT 且设 DFT x1 n X1 k DFT x2 n X2 k 线性 式中 a b为任意常数 该式可根据DFT定义证明 2 和的长度N1和N2不等时 选择为变换长度 短者进行补零达到N点 线性性质仍然成立 这里包括三层意思 1 先将x n 进行周期延拓 2 再进行移位 3 最后取主值序列 二 序列的圆周移位 1 定义 一个有限长序列x n 的圆周移位定义为 由于我们取主值序列 即只观察n 0到N 1这一主值区间 当某一抽样从此区间一端移出时 与它相同值的抽样又从此区间的另一端进来 如果把x n 排列一个N等分的圆周上 序列的移位就相当于x n 在圆上旋转 故称作圆周移位 当围着圆周观察几圈时 看到就是周期序列 2 圆周移位的含义 3 时域圆周移位定理设x n 是长度为N的有限长序列 y n 为x n 圆周移位 即 则圆周移位后的DFT为 证利用周期序列的移位性质加以证明 再利用DFS和DFT关系 这表明 有限长序列的圆周移位在离散频域中引入一个和频率成正比的线性相移 而对频谱的幅度没有影响 4 频域圆周移位定理对于频域有限长序列X k 也可看成是分布在一个N等分的圆周上 所以对于X k 的圆周移位 利用频域与时域的对偶关系 可以证明以下性质 若 则 这就是调制特性 它说明 时域序列的调制等效于频域的圆周移位 三 共轭对称性 1 周期序列共轭对称分量与共轭反对称分量 同样 有 周期为N的周期序列的共轭对称分量与共轭反对称分量分别定义为 2 有限长序列的圆周共轭对称分量与圆周共轭反对称分量 由于 所以 这表明长为N的有限长序列可分解为两个长度相同的两个分量 有限长序列的圆周共轭对称分量与圆周共轭反对称分量分别定义为 3 共轭对称特性之一 证明 4 共轭对称特性之二 证明 可知 5 共轭对称特性之三 证明 6 共轭对称特性之四 证明 7 共轭对称特性之五 六 8 X k 圆周共轭对称分量与圆周共轭反对称分量的对称性 9 实 虚序列的对称特性 当x n 为实序列时 根据特性之三 则X k Xep k 又据Xep k 的对称性 当x n 为纯虚序列时 根据特性之四 则X k Xop k 又据Xop k 的对称性 总结 共轭对称性 纯虚序列的共轭对称性 实数序列的共轭对称性 例 设x1 n 和x2 n 都是N点的实数序列 试用一次N点DFT运算来计算它们各自的DFT 例 求序列 x n n 2 n 1 3 n 2 4 n 3 的4点DFT 例 求序列 x n n 2 n 1 3 n 2 4 n 3 的8点DFT 四 DFT形式下的帕塞伐定理 证 如果令y n x n 则式变成 即 这表明一个序列在时域计算的能量与在频域计算的能量是相等的 四 圆周卷积和 1 时域卷积定理设和均为长度为N的有限长序列 且 如果 则 证明 相当于将作周期卷积和后 再取主值序列 将周期延拓 则有 在主值区间 所以 同样可证 圆周卷积过程 1 补零 当两序列不等长时 2 周期延拓 有限长序列变周期序列 3 翻褶 取主值序列 周期序列的翻褶 4 圆周移位5 相乘相加 0 m 0 m 0 m 0 m 最后结果 五 有限长序列的线性卷积与圆周卷积 1 线性卷积的长度的长度为的长度为它们线性卷积为 的非零区间为的非零区间为两不等式相加得也就是不为零的区间 为长 例如 1 0 1 2 n 1 0 1 2 n 3 m n 2 1 0 3 1 4 5 2 3 3 2 1 2 有限长序列的线性卷积与圆周卷积 时域圆周卷积在频域上相当于两序列的DFT的乘积 而计算DFT可以采用它的快速算法 快速傅里叶变换 FFT 见第4章 因此圆周卷积与线性卷积相比 计算速度可以大大加快 但是实际问题大多总是要求解线性卷积 例如 信号通过线性时不变系统 其输出就是输入信号与系统的单位脉冲响应的线性卷积 如果信号以及系统的单位脉冲响应都是有限长序列 那么是否能用圆周卷积运算来代替线性卷积运算而不失真呢 下面就来讨论这个问题 设x1 n 是N1点的有限长序列 0 n N1 1 x2 n 是N2点的有限长序列 0 n N2 1 1 先看它们的线性卷积 x1 m 的非零区间为 0 m N1 1 x2 n m 的非零区间为 0 n m N2 1 2 43 将两个不等式相加 得到 0 n N1 N2 2 在上述区间外 不是x1 m 0就是x2 n m 0 因而y1 n 0 所以y1 n 是N1 N2 1点有限长序列 即线性卷积的长度等于参与卷积的两序列的长度之和减1 例如 图2 16中 x1 n 为N1 4的矩形序列 图2 16 a x2 n 为N2 5的矩形序列 图2 16 b 则它们的线性卷积y1 n 为N N1 N2 1 8点的有限长序列 图2 16 c 2 44 为了分析其圆周卷积 我们先将序列x1 n 与x2 n 以L为周期进行周期延拓 它们的周期卷积序列为 2 45 前面已经分析了y1 n 具有N1 N2 1个非零值 因此可以看到 如果周期卷积的周期L N1 N2 1 那么y1 n 的周期延拓就必然有一部分非零序列值要交叠起来 从而出现混叠现象 只有在L N1 N2 1时 才没有交叠现象 这时 在y1 n 的周期延拓中 每一个周期L内 前N1 N2 1个序列值正好是y1 n 的全部非零序列值 而剩下的L N1 N2 1 个点上的序列值则是补充的零值 圆周卷积正是周期卷积取主值序列 因此 所以要使圆周卷积等于线性卷积而不产生混叠的必要条件为 2 47 满足此条件后就有 即x1 n x2 n x1 n x2 n L 图2 16 d e f 正反映了 2 46 式的圆周卷积与线性卷积的关系 在图2 16 d 中 L 6小于N1 N2 1 8 这时产生混叠现象 其圆周卷积不等于线性卷积 而在图2 16 e f 中 L 8和L 10 这时圆周卷积结果与线性卷积相同 所得y n 的前8点序列值正好代表线性卷积结果 所以只要L N1 N2 1 圆周卷积结果就能完全代表线性卷积 图2 16线性卷积与圆周卷积 图2 16线性卷积与圆周卷积 例2 8一个有限长序列为 1 计算序列x n 的10点离散傅里叶变换 2 若序列y n 的DFT为 式中 X k 是x n 的10点离散傅里叶变换 求序列y n 3 若10点序列y n 的10点离散傅里叶变换是 式中 X k 是序列x n 的10点DFT W k 是序列w n 的10点DFT 求序列y n 解 1 由式 2 30 可求得x n 的10点DFT 2 X k 乘以一个WNkm形式的复指数相当于是x n 圆周移位m点 本题中m 2 x n 向左圆周移位了2点 就有 y n x n 2 10R10 n 2 n 3 n 8 3 X k 乘以W k 相当于x n 与w n 的圆周卷积 为了进行圆周卷积 可以先计算线性卷积再将结果周期延拓并取主值序列 x n 与w n 的线性卷积为 z n x n w n 1 1 1 1 1 3 3 2 2 2 2 2 圆周卷积为 在0 n 9求和中 仅有序列z n 和z n 10 有非零值 用表列出z n 和z n 10 的值 对n 0 1 2 9求和 得到 所以10点圆周卷积为 y n 3 3 1 1 1 3 3 2 2 2 3 7抽样Z变换 频域抽样理论讨论 时域抽样 对一个频带有限的信号 根据抽样定理对其进行抽样 所得抽样信号的频谱是原带限信号频谱的周期延拓 因此 完全可以由抽样信号恢复原信号 频域抽样 对一有限序列 时间有限序列 进行DFT所得x k 就是序列傅氏变换的采样 所以DFT就是频域抽样 频域抽样定理要研究的问题 M点 N点 问题 能否由频域抽样X k 恢复序列x n 能否由频域抽样X k 恢复序列x z 或若能恢复其条件是什么 如何推导内插恢复公式 2 由频域抽样恢复序列 一个绝对可和的非周期序列x n 的Z变换为 由于x n 绝对可和 故其傅氏变换存在且连续 也即其Z变换收敛域包括单位圆 这样 对X Z 在单位圆上N等份抽样 就得到 对进行反变换 并令其为 则 x n 为无限长序列 混叠失真x n 为有限长序列 长度为M1 N M 不失真2 N M 混叠失真 频率采样定理 若序列长度为M 则只有当频域采样点数 时 才有 即可由频域采样X k 不失真地恢复原信号x n 否则产生时域混叠现象 3 用频域采样表示的内插公式 4 用频域采样表示的内插公式 3 8利用DFT计算模拟信号的傅里叶变换 级数 对 信号的频谱分析 计算信号的傅里叶变换 1 对连续时间非周期信号的DFT逼近 1 将x t 在t轴上等间隔T分段 2 将x n 截短成有限长序列t 0 T0 N个抽样点 3 频域抽样 一个周期分N段 采样间隔 时域周期延拓 周期为 2 对连续时间非周期信号的DFT逼近过程1 时域抽样2 时域截断3 频域抽样 近似逼近 3 频率响应的混叠失真及参数的选择 同时提高信号最高频率和频率分辨率 需增加采样点数N 信号最高频率与频率分辨率之间的矛盾 例 有一调幅信号用DFT做频谱分析 要求能分辨xa t 的所有频率分量 问 1 抽样频率应为多少赫兹 2 抽样时间间隔应为多少秒 3 抽样点数应为多少点 1 抽样频率应为 解 2 抽样时间间隔应为 1 混迭对连续信号x t 进行数字处理前 要进行采样采样序列的频谱是连续信号频谱的周期延拓 周期为fs 如采样率过低 不满足采样定理 fs 2fh 则导致频谱混迭 使一个周期内的谱对原信号谱产生失真 无