《离散傅立叶变换》PPT课件

第3章离散傅里叶变换 DFT 蒋明峰浙江理工大学 3 1四种不同傅里叶变换对 傅里叶级数 FS 连续时间 离散频率的傅里叶变换 连续傅里叶变换 FT 连续时间 连续频率的傅里叶变换 序列的傅里叶变换 DTFT 离散时间 连续频率的傅里叶变换 离散傅里叶变换 DFT 离散时间 离散频率的傅里叶变换 1 连续傅里叶变换 FT 非周期连续时间信号通过连续付里叶变换 FT 得到非周期连续频谱密度函数 例子 这以下变换对可以看出时域连续函数造成频域是非周期的谱 而是时域的非周期造成频域是连续的谱 2 傅里叶级数 FS 周期连续时间信号非周期离散频谱密度函数 周期为Tp的周期性连续时间函数x t 可展成傅里叶级数X jk 0 是离散非周期性频谱 表示为 FS 例子 通过以下变换对可以看出时域的连续函数造成频域是非周期的频谱函数 而频域的离散频谱就与时域的周期时间函数对应 频域采样 时域周期延拓 3 序列的傅里叶变换 DTFT 非周期离散的时间信号 经过单位园上的Z变换 DTFT 得到周期性连续的频率函数 这里的 是数字频率 它和模拟角频率 的关系为 T 如果把序列看成模拟信号的抽样 抽样时间间隔为T 抽样频率为fs 1 T s 2 T 代入x n x nT T 则这一变换对可写成 同样可看出 时域的离散造成频率的周期延拓 而时域的非周期对应于频率的连续 4 离散傅里叶变换 DFT 上面讨论的三种傅里叶变换对 都不适用在计算机上运算 因为至少在一个域 时域或频域 中 函数是连续的 因为从数字计算角度 我们感兴趣的是时域及频域都是离散的情况 这就是我们这里要谈到的离散傅里叶变换 周期性离散时间信号从上可以推断 周期性时间信号可以产生频谱是离散的离散时间信号可以产生频谱是周期性的 得出其频谱为周期性离散的 也即我们所希望的 DFT的变换 总之 一个域的离散必然造成另一个域的周期延拓 四种付里叶变换形式的归纳 可以得出一般的规律 一个域的离散对应另一个域的周期延拓 一个域的连续必定对应另一个域的非周期 表对这四种傅里叶变换形式的特点作了简要归纳 3 3离散傅里叶级数 DFS 及性质 1 周期序列的离散傅里叶级数 若离散时间序列x n 为周期序列 则一定满足 x n x n rN 其中N 正整数 为信号的周期 r为任意整数 为了和非周期序列区分 周期序列记作 因为周期序列不是绝对可和 因此周期序列不能用傅里叶变换来表示 但是周期序列可以用傅里叶级数 DFS 来表示 傅里叶级数 DFS 定义为 其中为周期序列傅里叶级数的系数 其大小为 为了书写方便 常令符号 这样周期序列的傅里叶变换对可以写为 正变换 反变换 例3 4设 将以N 10为周期作周期延拓 得到周期信号 求的DFS 解 3 4周期序列的傅里叶级数的性质 1 线性 如果 则有 2 移位 则有 如果 3 调制特性 设是周期为N的周期序列 则 4 周期卷积和 若 则有 记作 证 代入 得 将变量进行简单换元 即可得等价的表示式 周期卷积亦是一个卷积公式 但是它与非周期序列的线性卷积不同 首先 和 或 和都是变量m的周期序列 周期为N 故乘积也是周期为N的周期序列 其次 求和只在一个周期上进行 即m 0到N 1 所以称为周期卷积 周期卷积的过程可以用图6 7来说明 这是一个N 7的周期卷积 每一个周期里 有一个宽度为4的矩形脉冲 有一个宽度为3的矩形脉冲 图中画出了对应于n 0 1 2时的 周期卷积过程中一个周期的某一序列值移出计算区间时 相邻的同一位置的序列值就移入计算区间 运算在m 0到N 1区间内进行 即在一个周期内将与逐点相乘后求和 先计算出n 0 1 N 1的结果 然后将所得结果周期延拓 就得到所求的整个周期序列 图6 7两个周期序列 N 7 的周期卷积 图6 7两个周期序列 N 7 的周期卷积 图6 7两个周期序列 N 7 的周期卷积 例3 5两个周期序列N 6序列和如图 a b 所示 求他们的卷积和 解 N 0 1 2 N 1 N m N 0 1 2 N 1 N m N 0 1 2 N 1 N m N 0 1 2 N 1 N m a b N 0 1 2 N 1 N m N 0 1 2 N 1 N m N 0 1 2 N 1 N m N 0 1 2 N 1 N n 5 周期序列相乘 如果 则 3 5有限长序列的离散傅里叶变换 DFT 3 5 1离散傅里叶变换的定义 1 有限长序列与周期序列的性质 设x n 为有限长序列 长度为N 即x n 只在n 0 1 N 1有值 其他值时 x n 0 因此 可以把x n 看作周期为N的周期序列的一个周期 即 也可利用矩形序列表示成为 把看作有限长序列x n 以N为周期的周期延拓 表示为 通常我们把的第一个周期n 0 1 N 1定义为主值区间 称x n 为的主值序列 为了书写方便 将上式简写为 其中 表示数学上 n对N取余数 或称为 n对N取模值 例如 是周期为N 8的序列 则有 有限长序列的傅里叶变换的定义 2 有限长序列的离散傅里叶变换 DFT 正变换 反变换 例3 6已知 求x n 的8点DFT和16点DFT 解 N 8时 当N 16时 例3 7 已知 求的N点DFT 解 3 5 3DFT与DTFT及Z变换之间关系 若x n 是一个有限长序列 长度为N 对x n 进行Z变换 比较Z变换与DFT 我们看到 当z W kN时 即 表明 是Z平面单位圆上幅角为的点 也即将Z平面单位圆N等分后的第k点 所以X k 也就是对X z 在Z平面单位圆上N点等间隔采样值 此外 由于傅里叶变换X ej 即是单位圆上的Z变换 DFT与序列傅里叶变换的关系为上式说明X k 也可以看作DTFT的傅里叶变换X ej 在区间 0 2 上的N点等间隔采样 其采样间隔为 N 2 N 这就是DFT的物理意义 图DFT与DTFT Z变换的关系 3 6离散傅里叶变换的性质 1线性 如果序列和长度都为N 且 则有 注意以下两点 1 如果x1 n 和x2 n 长度皆为N即在0 n N 1范围有值 则的长度也是N 2 若x1 n 和x2 n 的长度不等 设x1 n 长度为N1 而x2 n 的长度为N2 则的长度应为N max N1 N2 故DFT必须按长度N计算 例如 若N1 N2 则取N N2 那么需将x1 n 补上N2 N1个零值点后变成长度为N2序列 然后都作N2点的DFT 2序列的圆周移位性 若设是的圆周移位 即 则 1 圆周移位的定义一个长度为N的有限长序列x n 的圆周移位定义为 y n x n m NRN n 我们可以这样来理解上式所表达的圆周移位的含义 首先 将x n 以N为周期进行周期延拓得到周期序列 再将加以移位 然后 再对移位的周期序列取主值区间 n 0到N 1 上的序列值 即x n m NRN n 所以 一个有限长序列x n 的圆周移位序列y n 仍然是一个长度为N的有限长序列 这一过程可用图3 9 a b c d 来表达 从图上可以看出 由于是周期序列的移位 当我们只观察0 n N 1这一主值区间时 某一采样从该区间的一端移出时 与其相同值的采样又从该区间的另一端循环移进 因而 可以想象x n 是排列在一个N等分的圆周上 序列x n 的圆周移位 就相当于x n 在此圆周上旋转 如图3 9 e f g 所示 因而称为圆周移位 若将x n 向左圆周移位时 此圆是顺时针旋转 将x n 向右圆周移位时 此圆是逆时针旋转 此外 如果围绕圆周观察几圈 那么看到的就是周期序列 图3 9圆周移位过程示意图 时域圆周移位定理 设x n 是长度为N的有限长序列 y n 为x n 圆周移位 即则圆周移位后的DFT为 证明利用周期序列的移位性质加以证明再利用DFS和DFT关系 频域圆周移位定理 对于频域有限长序列X k 也可看成是分布在一个N等分的圆周上 所以对于X k 的圆周移位 利用频域与时域的对偶关系 可以证明以下性质 若则 4 4 16 3 共轭对称性 设为的共轭复序列 则 有限长序列长度为N 则它的圆周共轭对称分量和圆周共轭反对称分量分别定义为 任何有限长序列x n 都可以表示成圆周共轭对称分量和圆周共轭反对称分量之和 即 则有 若x n 实序列 两边进行离散傅里叶变换则有 若x n 是纯虚序列 则显然X k 只有圆周共轭分量 即满足 5帕塞瓦尔 Parseval 定理 五 时域循环卷积 设x1 n 和x2 n 都是点数为N的有限长序列 0 n N 1 且有 若 则 证明这个卷积相当于周期序列和作周期卷积后再取其主值序列 先将Y k 周期延拓 即根据DFS的周期卷积公式由于0 m N 1为主值区间 因此将式经过简单换元 即可证明 圆周卷积过程中 求和变量为m n为参变量 先将x2 m 周期化 形成x2 m N 再反转形成x2 m N 取主值序列则得到x2 m NRN m 通常称之为x2 m 的圆周反转 对x2 m 的圆周反转序列圆周右移n 形成x2 n m NRN m 当n 0 1 2 N 1时 分别将x1 m 与x2 n m NRN m 相乘 并在m 0到N 1区间内求和 便得到圆周卷积y n 这一计算过程分5步 1 周期延拓 2 折叠 3 移位和取主值 4 相乘 5 相加 在图3 6 1 a 中 x1 n 的N个值按顺时针方向均匀分布在内圆周上 x2 n 的N个值按反时针方向均匀分布在外圆周上 把内外圆周上对应的数值两两相乘 然后把乘积相加就得到y 0 若将外圆周顺时针方向转动一格 如图3 6 1 b 所示 将内外圆周上对应的数值两两相乘并把乘积相加 便得到y 1 依次类推 可以得出y n 的其它值 因此循环卷积也叫做圆卷积 图3 6 1圆周卷积的圆形示意图 上述计算过程可写成矩阵形式 一般 对两个N点序列的循环卷积 其矩阵形式是式中矩阵X1称为循环矩阵 由第一行开始 依次向右移动一个元素 以出去的元素在下一行的最左边出现 即每一行都是由x1 0 x1 N 1 x1 1 这N个元素依此法则生成的 故X1称为循环矩阵 因此相对应的卷积称为循环卷积 频域圆周卷积和定理 如果 则有 时域圆周卷积在频域上相当于两序列的DFT的乘积 而计算DFT可以采用它的快速算法 快速傅里叶变换 FFT 因此圆周卷积与线性卷积相比 计算速度可以大大加快 但是实际问题大多总是要求解线性卷积 例如 信号通过线性时不变系统 其输出就是输入信号与系统的单位脉冲响应的线性卷积 如果信号以及系统的单位脉冲响应都是有限长序列 那么是否能用圆周卷积运算来代替线性卷积运算而不失真呢 下面就来讨论这个问题 设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 将两个不等式相加 得到 0 n N1 N2 2 在上述区间外 不是x1 m 0就是x2 n m 0 因而y1 n 0 所以y1 n 是N1 N2 1点有限长序列 即线性卷积的长度等于参与卷积的两序列的长度之和减1 例如 图3 6 2中 x1 n 为N1 4的矩形序列 图3 6 2 a x2 n 为N2 5的矩形序列 图2 16 b 则它们的线性卷积y1 n 为N N1 N2 1 8点的有限长序列 图3 6 2 c 3 97 2 我们再来看x1 n 与x2 n 的圆周卷积 为了分析其圆周卷积 我们先将序列x1 n 与x2 n 以L为周期进行周期延拓 它们的周期卷积序列为 3 98 前面已经分析了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 个点上的序列值则是补充的零值 因此 圆周卷积正是周期卷积取主值序列 所以要使圆周卷积等于线性卷积而不产生混叠的必要条件为 3 99 满足此条件后就有 即x1 n x2 n x1 n x2 n L 图3 6 2 d e f 正反映了 2 46 式的圆周卷积与线性卷积的关系 在图3 6 2 d 中 L 6小于N1 N2 1 8 这时产生混叠现象 其圆周卷积不等于线性卷积 而在图3 6 2 e f 中 L 8和L 10 这时圆周卷积结果与线性卷积相同 所得y n 的前8点序列值正好代表线性卷积结果 所以只要L N1 N2 1 圆周卷积结果就能完全代表线性卷积 图3 6 2线性卷积与圆周卷积 图3 6 2线性卷积与圆周卷积 例一个有限长序列为 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 由DFT计算公式可求得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频域采样理论 首先 考虑一个任意的绝对可和的非周期序列x n 它的Z变换为 由于绝对可和 所以其傅里叶变换存在且连续 故Z变换收敛域包括单位圆 如果我们对X z 在单位圆上进行N点等距采样 3 101 问题在于 这样采样以后是否仍能不失真地恢复出原序列x n 也就是说 频率采样后从X k 的反变换中所获得的有限长序列 即xN n IDFT X k 能不能代表原序列x n 为此 我们先来分析X k 的周期延拓序列的离散傅里叶级数的反变换 令其为 将式 3 101 代入此式 可得 由于 所以 3 102 这说明由得到的周期序列是原非周期序列x n 的周期延拓 其时域周期为频域采样点数N 在第1章中已经知道 时域采样造成频域的周期延拓 这里又看到一个对称的特性 即频域采样同样会造成时域的周期延拓 1 如果x n 是有限长序列 点数为M 则当频域采样不够密 即当N M时 x n 以N为周期进行延拓 就会造成混叠 这时 从就不能不失真地恢复出原信号x n 来 因此 对于M点的有限长序列x n 频域采样不失真的条件是频域采样点数N要大于或等于时域采样点数M 时域序列长度 即满足 N M 3 103 此时可得到 N M 3 104 也就是说 点数为N 或小于N 的有限长序列 可以利用它的Z变换在单位圆上的N个等间隔点上的采样值精确地表示 2 如果x n 不是有限长序列 即无限长序列 则时域周期延拓后 必然造成混叠现象 因而一定会产生误差 当n增加时信号衰减得越快 或频域采样越密 即采样点数N越大 则误差越小 即xN n 越接近x n 既然N个频域采样X k 能不失真地代表N点有限长序列x n 那么这N个采样值X k 也一定能够完全地表达整个X z 及频率响应X ej 讨论如下 由于 将它代入X z 式子中 得到 由于WN Nk 1 因此 这就是用N个频率采样X k 来表示X z 的内插公式 它可以表示为 3 105 3 106 式中 3 107 称为内插函数 令其分子为零 得 r 0 1 k N 1 即内插函数在单位圆的N等分点上 也即采样点上 有N个零点 而分母为零 则有z WN k 的一个极点 它将和第k个零点相抵消 因而 插值函数 k z 只在本身采样点r k处不为零 在其他 N 1 个采样点r上 r 0 1 N 1 但r k 都是零点 有 N 1 个零点 而它在z 0处还有 N 1 阶极点 如图3 14所示 图3 14内插函数的零极点 现在来讨论频率响应 即求单位圆上z ej 的Z变换 由式 2 69 可得 而 3 108 可将 k ej 表示成更为方便的形式 式中 3 109 3 110 这样式 3 108 又可改写为 3 111 图3 15内插函数幅度特性与相位特性 N 5 当变量 0时 1 当 i 1 2 N 1 时 0 因而可知 满足以下关系 2 76 k 0 1 N 1 请注意 一般来说 这里的X ej 和X k 都是复数 也就是说 函数在本采样点 而在其他采样点上 函数 整个X ej 就是由N个函数分别乘上X k 后求和 所以很明显 在每个采样点上X ej 就精确地等于X k 因为其他点的插值函数在这一点上的值为零 没有影响 即 各采样点之间的X ej 值由各采样点的加权插值函数在所求 点上的值的叠加得到的 在以后章节中 我们将会看到 频率采样理论为FIR滤波器的结构设计 以及FIR滤波器传递函数的逼近提供了又一个有力的工具 例3 11设序列的长度为M 8 其大小为 现对的序列傅里叶变换