离散傅里叶变换及其快速计算方法ppt课件.ppt

DFS和DFT的导出DFS和DFT的性质Z变换与DFS的关系FFTIDFT频谱分析 第三章DFT 离散付氏变换 1 连续信号xa t 其傅里叶变换为 xa t 为时域连续信号Xa 为频域连续信号 3 1问题的提出 连续信号的傅里叶变换 2 离散信号在两种变换域中的表示方法 1 离散时间傅里叶变换DTFT 提供了绝对可加的离散时间序列在频域 中的表示方法 2 Z变换 提供任意序列的z域表示 这两种变换有两个共同特征 1 变换适合于无限长序列 2 它们是连续变量 或z的函数 3 1问题的提出 离散信号的变换 3 问题 X z X ejw 都是连续的 利用计算机处理有困难 例如使用Matlab 因此提出了在频域内取样 使频谱离散化的问题 必须截断序列 得到有限个点的序列 目标 我们需要得到一个可进行数值计算的变换方法 1 DTFT 频域中原始信号频谱的周期拓展 2 对DTFT在频域中采样 DFS 3 将DFS推广到有限持续时间序列 DFT DFT避免了前面提到的那两个问题 并且它是计算机可实现的变换方式 DFT已成为DSP算法中的核心变换 原因 1 有限长序列傅里叶变换的重要方法 2 有快速算法 3 1问题的提出 可计算性 4 3 1问题的提出 傅里叶变换的四种形式 1 非周期连续时间 傅里叶变换 FT 连续频率周期连续时间 傅里叶级数 FS 离散频率非周期离散时间 离散时间傅里叶变换 DTFT 连续频率周期离散时间 离散傅里叶级数 DFS 离散频率 5 3 1问题的提出 傅里叶变换的四种形式 2 1 连续信号 非周期 的付氏变换 时域连续函数造成频域是非周期的谱时域的非周期造成频域是连续的谱 6 2 周期连续时间信号 傅里叶级数FS 时域连续函数造成频域是非周期的谱 频域的离散对应时域是周期函数 3 1问题的提出 傅里叶变换的四种形式 3 时域周期 频域离散 7 3 非周期离散信号 离散时间傅里叶变换DTFT 时域的离散化造成频域的周期延拓时域的非周期对应于频域的连续 3 1问题的提出 傅里叶变换的四种形式 4 时域离散 频域周期 取样定理 8 4 周期离散时间信号 离散傅里叶级数DFS 一个域的离散造成另一个域的周期延拓离散傅里叶级数的时域和频域都是离散的和周期的 3 1问题的提出 傅里叶变换的四种形式 5 时域周期 离散 频域周期 离散 9 四种傅里叶变换形式的归纳总结 离散时间函数的取样间隔 T1 取样频率 离散频率函数的取样间隔 F0 时间周期 3 1问题的提出 傅里叶变换的四种形式 6 结论 时域中函数取样 离散 映射 频域中函数周期重复 频域中函数取样 映射 时域中函数周期重复 取样间隔 映射 周期 2 间隔 10 0 时域中函数的取样和频域中函数的取样 3 1问题的提出 傅里叶变换的四种形式 7 11 由以上讨论可以清楚地看到 时域取样将引起频域的周期延拓 频域取样也将引起时域的周期延拓 因此可以设想 如果同时对频域和时域取样 其结果是时域和频域的波形都变成离散 周期性的波形 从而我们可以利用付氏级数这一工具 得到它们之间的离散付氏级数DFS关系 3 2DFS及其性质 12 基本关系式若r m都是整数 则 其中 DFS定义 预备知识 证明 对于r m 不论k取何值 显然等式成立 对于r m 13 为了推导的关系 作下列变量代换 时域 频域 则得 DFS定义 正变换 14 周期离散序列的Z变换存在 收敛 的问题因为周期离散序列 而对于周期信号 严格数学意义上讲 其Z变换不收敛 因为 而对于找不到衰减因子使它绝对可和 收敛 为此 定义新函数 其Z变换 DFS定义 正变换 15 其频谱 是连续变量 需要对其离散化 DFS定义 正变换 取的一个主周期进行Z变换 16 频域取样X ej 是连续变量 的周期函数 周期为2 把 离散化 即在0 2 区间内等间隔取N个点 取样间隔为2 N 另一个角度看 X ej 是Z平面单位圆上的Z变换 连续变量 的离散化也可以认为是把单位圆分N等分 每分为2 N 其中 称为频域中的取样间隔 也称为频率分辨率 DFS定义 正变换 17 DFS定义 正变换 18 DFS DFS定义 正变换 也仅有0 1 N 1个独立值 周期为N 因为 所以 19 反变换IDFS正变换两端乘以 m 0 1 N 1然后令k 0 1 N 1求和 得 DFS定义 反变换 用正交条件 20 DFS定义 反变换 即 只有m n时 才有值 而m不等于n时 为零 因此 x n 只取x m 变量m替换为n 得 21 DFS变换对 时域周期序列与频域周期序列间的关系 DFS定义 反变换 其中 22 在什么条件下不产生混迭失真 频率取样频率取样 若时间信号有限长 当满足下列条件时 X ej 的样本值X k 能不失真的恢复成原信号 为了避免时间上的混迭 1 必须是时间限制 有限时宽 2 取样频率间隔小于 DFS定义 几点说明 23 频率分量如果变量DFS可表示为 因此 时域n及频域k都是有物理意义的 DFS定义 几点说明 指数项kn不变 24 更具体地 傅里叶系数的标号k和频率f的关系为 所以 对应关系 傅里叶系数标号k 0 N数字频率 0 2 模拟频率f 0 fs DFS定义 几点说明 25 DFS定义 几点说明 频率成份直流分量 当k 0时 此时得到的傅里叶级数的系数称为信号的直流分量 DCComponent 是信号的平均值 交流分量 其它频率 k 0 称为周期信号的谐波 此时的傅里叶级数系数称为信号的交流分量 k 1时的频率为信号的一次谐波 或基频 频率大小为fs N 时间为NTs 等于完成一个周期所需要的时间 其它谐波为基频的整数倍 离散傅里叶级数包含了0到 N 1 fs N的频率 因而N个傅里叶级数的系数位于从0直到接近取样频率的频率上 时域 26 DFS定义 几点说明 周期信号的频谱由傅里叶系数可得到的幅度频谱和相位频谱 不难证明 如果是实序列 那么幅度频谱是周期性偶函数 相位频谱是周期性奇函数 周期信号由离散傅里叶级数DFS得到的频谱 和非周期信号由离散时间傅里叶变换DTFT得到的频谱之间有重要区别 DTFT产生连续频谱 这意味着频谱在所有的频率处都有值 因而非周期信号的幅度和相位频谱是光滑无间断的曲线 与之相反 DFS仅有N点的频谱 仅包含有限个频率 因而周期信号的幅度和相位频谱是线谱 即相等间隔的竖线 当频谱的横坐标变量用实际频率f代替k时 谱线间隔为fs N 并不是所有的周期信号都含有全部谐波 例如有些频谱只有奇次谐波 比如三角波 偶次谐波为0 而有些频谱仅在一些谐波处的值为0 27 DFS的Matlab的实现 由DFS的定义可以看出它是一种可进行数值计算表示式 它可由多种方式实现 1 利用循环语句for end实现为了计算每个样本 可用for end语句实现求和 为了计算所有的DFS系数 需要另外一个for end循环 这将导致运行嵌套的两个for end循环 显然 这种方法的效率较低 28 设和代表序列x n 和X k 主周期的列向量 则DFS的正反变换表达式由下式给出 其中矩阵WN由下式给出 矩阵WN为方阵 叫做DFS矩阵 2 利用矩阵 矢量乘法 29 function Xk dfs xn N n 0 1 N 1 rowvectorfornk 0 1 N 1 rowvecorforkWN exp j 2 pi N Wnfactornk n k createsaNbyNmatrixofnkvaluesWNnk WN nk DFSmatrixXk xn WNnk rowvectorforDFScoefficientsfunction xn idfs Xk N n 0 1 N 1 rowvectorfornk 0 1 N 1 rowvecorforkWN exp j 2 pi N Wnfactornk n k createsaNbyNmatrixofnkvaluesWNnk WN nk IDFSmatrixxn Xk WNnk N rowvectorforIDFSvalues DFS的Matlab的实现 30 例 求出下面周期序列的DFS表示式 解 上述序列的基本周期为N 4 因而W4 e j2 4 j 31 32 33 例 下面给出一周期 方波 序列 其中 m 0 1 2 N是基本周期 L N是占空比 a 确定一种用L与N描述的的表达式 b 分别画出当L 5 N 20 L 5 N 40 L 5 N 60 L 7 N 60时表达式 c 对所得结果进行讨论 34 解 a 由DFS定义可得 而 的幅值可表示为 35 b Matlab程序如下 Chapter3 Example3 03L 5 N 20 改变参数 x ones 1 L zeros 1 N L xn x ones 1 3 xn xn n N 1 2 N 1 subplot 1 1 1 subplot 2 1 2 stem n xn xlabel n ylabel xtilde n title Threeperiodsofxtilde n axis N 2 N 1 0 5 1 5 36 Part b L 5 N 20 改变参数 xn ones 1 L zeros 1 N L Xk dfs xn N magXk abs Xk N 2 1 N Xk 1 N 2 1 k N 2 N 2 subplot 2 2 1 stem k magXk axis N 2 N 2 0 5 5 5 xlabel k ylabel Xtilde k title DFSofSQ wave L 5 N 20 37 注意 是周期信号 图中只画出了从 N 2到N 2的部分 c 从图中可以看到 方波的DFS系数的包络像 Sinc 函数 K 0时的幅度等于L 同时函数的零点位于N L 占空比的倒数 的整数倍处 L 5不变 N变大 即填0 但有效信息没有增加 则形状不变 只是更平滑 即获得了一个高密度谱 N 60不变 L变大 即增加了原始数据长度 则变换后得形状发生了变化 获得了更多的信息 即高分辨率谱 38 例 设当N 5 10 20 50时 分别对其Z变换在单位圆上取样 研究不同的N对时域的影响 39 Frequency domainsampling x n 0 7 n u n X z z z 0 7 z 0 7subplot 1 1 1 N 5 改变参数 k 0 1 N 1 wk 2 pi k N zk exp j wk Xk zk zk 0 7 xn real idfs Xk N 只取实部 去掉产生的虚部误差xtilde xn ones 1 8 画出8个周期xtilde xtilde subplot 2 2 1 stem 0 39 xtilde axis 0 40 0 1 1 5 xlabel n ylabel xtilde n title N 5 40 从图中清楚地表明在时域中出现的混叠 尤其是当N 5与N 10时 对于大的N值 其x n 的尾部足够小 实际上不会导致明显的混迭 这对于变换前 有效截取无限序列 是非常有效的 1 2020 1 0291 1 0008 1 0000 41 线性 且 则 a b为任意常数 DFS的性质 线性 42 序列的周期移位 时域 若是周期序列 其周期为N 移位后仍为周期序列 且 DFS的性质 序列的周期移位 证明 43 调制特性 频域周期移位 DFS的性质 调制特性 证明 44 周期卷积 时域 若 则 频域相乘 时域卷积周期卷积 两个周期序列在一个周期上的线性卷积 是一种特殊的卷积计算形式 DFS的性质 周期卷积 1 45 DFS的性质 周期卷积 2 证明 46 DFS的性质 周期卷积 3 1 x1 n 和x2 n 是周期的 2 求和范围为一个周期 3 周期序列周期卷积后 序列的长度仍然是周期的 位置保持不变 47 序列的线性卷积与周期卷积的几点区别 线性卷积的求和对参与卷积的两个序列无任何要求 而周期卷积要求两个序列是周期相同的周期序列 线性卷积的求和范围由两个序列的长度和所在的区间决定 而周期卷积的求和范围是一个周期N 线性卷积所得序列的长度 M N 1 由参与卷积的两个序列的长度确定 而周期卷积的结果仍是周期序列 且周期与原来的两个序列周期相同 周期卷积等同于两个周期序列在一个周期上的线性卷积计算 DFS的性质 周期卷积 4 48 解 例 已知序列x1 n R4 n x2 n n 1 R5 n 分别将序列以周期为N 6拓展成周期序列 求两个周期序列的周期卷积和 49 1 5 4 5 1 2 50 频域周期卷积利用DFS的对偶性有 若 则 时域相乘 频域卷积 DFS的性质 周期卷积 5 注意频域卷积的求和号前面有1 N 51 DFS的性质 共轭对称性 由任一周期性序列 定义如下两个序列 共轭偶对称周期性序列共轭奇对称周期性序列 且具有如下关系 其它对称性质见教科书 52 DFS定义和性质 小结 时域周期序列与频域周期序列的关系DFSDFS的性质重点 周期移位调制特性周期卷积 53 对于一段有限长信号 连续 分析频谱问题是付氏积分问题 进行时域周期重复和取样两过程 就可把广义积分问题变成有限项求和 即由CTFT DFS DFS变换 周期离散时间函数与一周期离散频率函数的组合 它们是有限求和 而不是积分 常用DFS来逼近连续时间过程的傅氏变换 也即要用数字运算能完全计算出付氏积分 必须对时间函数和频率函数取样 即DFS 选择时间有限和频率有限的信号 时间取样 取样频率大于信号最高频率两倍 频率取样 取样间隔足够小 使时间函数的周期 单位圆上等分 取样 的点数 大于信号的时域长度 结果 频域和时域中均不出现混迭现象 3 3有限离散傅里叶变换及其性质 1 54 离散傅氏级数提供了一种对离散时间傅氏变换作数值计算的技巧 它在时域和频域都是周期的 但在实际中大多数信号不具有周期性 它们很可能具有有限持续时间 对这些信号 怎样探讨一种可数值计算的傅氏表达式 理论上 可通过构造一周期信号 其基本形状为有限持续时间信号 然后计算此周期信号的DFS 实际上 这也就是定义了一种新的变换 称为离散傅氏变换 DFT 它是DFS的主周期 DFT是对任意有限持续时间序列可数值计算的傅氏变换 3 3有限离散傅里叶变换及其性质 2 55 同样 X k 也是一个N点的有限长序列 关系 其中 DFT定义 表达式 1 周期序列的表示 56 DFT定义 表达式 2 若n n1 n2N成立 且n1满足0 n1 N 1 则把n1称做n对N的模数 用符号 n N表示 即 n模N n N n1 也就是n对N取余数 例 是周期为N 6的序列 求n 19及n 2两数对N的余数 解 n 19 1 3 6 19 6 1n 2 1 6 4 2 6 4即 57 在无混迭的情况下 我们看如何把DFS变成DFT DFS DFT定义 表达式 3 因无混迭 则时域中一个周期长的主值序列对应于频域中一个周期长的主值序列 从DFS的时域和频域中各取出一个周期 即得到有限长度离散序列的时域和频域傅氏变换 58 有限长序列的DFT正变换和反变换 其中 DFT DFT定义 表达式 4 或 注意 从工程角度看 DFS和DFT的表达式没有本质区别 59 DFT的矩阵表示形式 若令 则 DFT定义 表达式 5 60 DFT定义 表达式 6 DFT图形解释 61 不仅浓缩了的全部内容 同时也浓缩了的全部内容 能够如实 全面地表示的频域特征 所以DFT具备明确的物理含义 DFT定义 表达式 7 DFT意义 62 由上面的讨论可知 在0 n N 1上 DFS和DFT相同 因此 可用类似的方法实现DFT 把原先名为dfs和idfs的Matlab函数改名为dft和idft函数 即可实现离散傅氏变换DFT 实际中 我们用的更多的是DFT的快速算法FFT 见后续内容 DFT定义 Matlab实现 63 例 x n 是一个4点序列 1 计算离散时间傅氏变换X ejw 并画出它的幅度和相位 2 计算x n 的4点DFT DFT定义 举例 64 解 1 离散时间傅氏变换为 因而 DFT定义 举例 65 DFT定义 举例 66 2 用X4 k 表示4点DFT DFT定义 举例 b 4 pointDFTN 4 w1 2 pi N k 0 N 1 X dft x N magX abs X phaX angle X 180 pisubplot 2 1 1 plot w N 2 pi magH axis 0 1 4 1 1 5 holdonstem k magX 67 k DFT定义 举例 68 例 怎样得到DTFTX ejw 的其他样本 解 显然 我们的采样频率应更小一些 也就是说 应增加N的长度 有两种方法 一种是采样时就采样更多的样本 另一种是在序列后面添加一定长度的零 叫做填零运算 在实际中 为了得到一个较密的频谱 这种运算是必要的 3 3 1DFT定义 举例 69 a 给x n 后附加4个零得到一个8点序列 x n 1 1 1 1 0 0 0 0 设X8 k 为一8点DFT 则在这种情况下 频率分辨率为w1 2 8 4 DFT定义 举例 70 b 8 pointDFTN 8 w1 2 pi N k 0 N 1 x x zeros 1 4 X dft x N magX abs X phaX angle X 180 pi结果如下 magX 4 00002 61310 00001 08240 00001 08240 00002 6131phaX 0 67 5000 153 4349 22 5000 90 000022 5000 53 130167 5000 DFT定义 举例 71 DFT定义 举例 72 b 更进一步 给x n 填充12个零 变成一个16点序列 即 x n 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 在这种情况下 频率分辨率为w1 2 16 8 DFT定义 举例 73 c 16 pointDFTsubplot 1 1 1 N 16 w1 2 pi N k 0 N 1 x x zeros 1 8 X dft x N magX abs X phaX angle X 180 pisubplot 2 1 1 plot w N 2 pi magH axis 0 1 16 1 1 5 holdonstem k magX xlabel k ylabel X k title MagnitudeoftheDFT N 16 holdoffsubplot 2 1 2 plot w N 2 pi phaH 180 pi axis 0 1 16 1 200 200 holdonstem k phaX xlabel k ylabel Degrees title AngleoftheDFT N 16 DFT定义 举例 74 DFT定义 举例 75 结论 基于以上两个例子 可以得到以下结论 填零是给原始序列填零的运算 这导致较长的DFT 它会给原始序列的离散时间傅氏变换提供间隔更密的样本 在Matlab中 用zeros函数实现填零运算 为精确地画出离散时间傅氏变换X ejw 只需要4点DFTX4 k 这是因为x n 仅有4个非零样本 因此 可通过填零得到X8 k X16 k 等等 用它们来填充X ejw 的值 填零运算提供了一个较密的频谱和较好的图示形式 但因为在信号中只是附加了零 而没有增加任何新的信息 因此 它不能提供更高分辨率的频谱 为了得到更高分辨率的频谱 需要获得更多的数据 其他的先进方法则是利用边缘信息和非线性技术 DFT定义 举例 76 例 为了说明高密度频谱和高分辨率频谱之间的区别 考察序列求出它基于有限个样本的频谱 a 当0 n 10时 确定并画出x n 的离散傅氏变换 b 当0 n 100时 确定并画出x n 的离散傅氏变换 DFT定义 举例 77 a 首先确定x n 的10点DFT 得到其离散时间傅氏变换的估计 Highresolutionspectrumbasedon100samplesofthesignalx n subplot 1 1 1 n 0 1 99 x cos 0 48 pi n cos 0 52 pi n Spectrumbasedonthefirst10samplesofx n n1 0 1 9 y1 x 1 1 10 subplot 2 1 1 stem n1 y1 title signalx n 0 n 9 xlabel n axis 0 10 2 5 2 5 Y1 dft y1 10 magY1 abs Y1 1 1 6 k1 0 1 5 w1 2 pi 10 k1 subplot 2 1 2 stem w1 pi magY1 只画了一半的点 原因是镜像对称的点 title SamplesofDTFTMagnitude xlabel frequencyinpiunits axis 0 1 0 10 disp PressRETURNtocontinue pause DFT定义 举例 78 DFT定义 举例 79 填充90个零以得到较密的频谱 Highdensityspectrum 100samples basedonthefirst10samplesofx n n2 0 1 99 y2 x 1 1 10 zeros 1 90 subplot 2 1 1 stem n2 y2 title signalx n 0 n 9 90zeros xlabel n axis 0 100 2 5 2 5 Y2 dft y2 100 magY2 abs Y2 1 1 51 k2 0 1 50 w2 2 pi 100 k2 subplot 2 1 2 plot w2 pi magY2 Holdon stem w2 pi magY2 title DTFTMagnitude xlabel frequencyinpiunits axis 0 1 0 10 disp PressRETURNtocontinue holdoff pause DFT定义 举例 80 DFT定义 举例 从结果图中可以看到 此序列在w 0 5 处有一主频率 原始序列则没有说明这一点 填零运算提供了更加平滑 高密度的频谱曲线 81 b 为得到更多的频谱信息 采集更多的样本 用x n 的100个样本来确定它的DFT Highresolutionspectrumbasedon100samplesofthesignalx n subplot 2 1 1 stem n x title signalx n 0 n 99 xlabel n axis 0 100 2 5 2 5 X dft x 100 magX abs X 1 1 51 k 0 1 50 w 2 pi 100 k subplot 2 1 2 plot w pi magX title DTFTMagnitude xlabel frequencyinpiunits axis 0 1 0 60 disp PressRETURNtocontinue DFT定义 举例 82 DFT清楚地表明了两个靠得很紧的频率 这是x n 的高分辨率的频谱 采样更多的数据提供了更多的信息 DFT定义 举例 83 DFT从整体上可看成是由窄带相邻滤波器组成的滤波器组DFT的每个分量X k 可看成是窄带滤波器的输出 此窄带滤波器的中心位于数字频率2 k N弧度 带宽为2 N 此概念的一个典型应用是数字音频压缩中的分析滤波器 例如AC3和MPEGAudio都是如此 分辨率 子带带宽 N点DFT覆盖了0到fs 取样频率 的频率范围 因此 频率取样点以fs N为间隔 该频率间隔称为DFT的频率分辨率 它描述了DFT分辨相邻信号频率的程度 频率间隔越小 分辨率越好 间隔越大 DFT分辨率越差 假定取样频率保持不变 当取样点越大时 DFT分辨率就会越好 这样频率间隔小 可获得频谱的许多细节 从滤波器组的角度看 分辨率好的DFT是由大量非常窄的带通滤波器构成的 DFT定义 DFT频谱 84 DFT定义 DFT频谱 滤波器的中心频率DFT分量X k 位于以下频率处 如果画出对频率f Hz 而不是对k的频谱 则更容易从实际角度解释DFT频谱 当k N 2时 f到达了fs 2奈奎斯特频率 因而 k 0到k N 2的DFT点携带了DFT全部必要的幅度和相位信息 其余点只是基带重要信号频率的镜像副本 是取样的人为结果 即幅度频谱是周期性的偶对称 85 例 为了体会DFT的滤波器组解释 x t 由两个余弦信号和随机噪声构成 取样频率fs 6 4Hz 请分析其频谱 解 x t 包含两个频率1 16Hz和3 8Hz 以6 4Hz取样后 相应的数字频率由 T 2 f fs 分别为 1 2 102 4和 2 6 51 2弧度 则在40秒内以6 4Hz进行取样 共得40 6 4 256个取样点 DFT定义 DFT频谱 86 3 3 1DFT定义 DFT频谱 15 87 在上图中随机噪声采用的是正态分布的高斯白噪声 randn函数 由于白噪声信号中所有频率的贡献均相等 所以白噪声频谱近似平坦 对于N 256点DFT 每个标号k对应于数字频率2 k 256弧度 由于DFT可以看作一组相邻窄带滤波器构成 每个滤波器以数字频率2 k 256弧度为中心 因而频谱峰值应位于2 k 256 2 102 4和2 k 256 6 51 2 即k 2 5 非整数 和k 15 整数 处 由于k必须是整数 k 2 5处的峰值又分成k 2和k 3处的两个小峰 当DFT变换的长度N是多个数字频率公倍数的整数倍时 即数字频率正好位于子带滤波器的中心频率上时 则得到理想的谱线 DFT是在频谱中对连续频谱进行取样 因此DFT不能超过DFT频率分辨率所允许的范围而去准确定位频率 即当信号谱线所在位置与DFT频率分辨率位置保持一致时 则能准确定位此谱线 当DFT中没有频率与所分析信号的重要频率相符时 DFT就将导致真实频谱的模糊 DFT定义 DFT频谱 88 例 以256Hz取样频率对信号取样 得到离散信号x n 计算其频谱 解 数字频率 数字信号 数字周期 数字周期为64 覆盖了15个模拟信号周期 DFT定义 DFT频谱 89 对上述离散信号进行N 128和N 130点DFT 因为128是64的整数倍 2倍 从图中看 128点DFT的幅度频谱中有两个理想尖锋 第二个尖锋是第一个的镜像 频谱中的理想尖锋就标志着正弦的频率 而当N 130不是该数字信号的数字周期64的整数倍 尖锋变宽并变小了 这就是频谱模糊现象 3 3 1DFT定义 DFT频谱 30 90 序列x n 的Z变换在单位圆上进行N等分 即 2 N 就是序列的DFT变换 取样 Z变换和DFT的关系是取样和内插的关系 这在实际应用中很重要 DFT与DTFT和Z变换的关系 91 取样Z变换设x n 为一个长度为N的有限长序列 则有 DFT与Z变换的关系 取样Z变换 92 从DTFT的角度看 有限长序列的DFT结果包含了N个离散频率点处的DTFT结果 这个离散频率点等间隔地分布在区间 0 2 内 从Z变换的角度看 DFT结果包含了z平面上N个离散点处的Z变换结果 这N个离散点均匀地分布在单位圆上 由此也称DFT为单位圆上的取样Z变换 DFT与Z变换的关系 取样Z变换 93 频域取样定理 若序列长度为M 则只有当频域采样点数N满足N M时 才有 即可由频域取样X k 不失真地恢复原信号x n 否则产生时域混叠现象 此时可由N个取样值X k 内插恢复出X z 或X ejw DFT与Z变换的关系 z域内插 时域取样定理 在满足奈奎斯特定理条件下 时域取样信号可以不失真地还原原连续信号 频域取样情况如何 取样条件 内插公式 94 Z域内插公式 由DFTX k 可以确定z平面上任一点处的X z DFT与Z变换的关系 z域内插 z平面内插公式 内插函数 95 内插函数的零极点分布极点 N 1 阶极点z 0 一阶极点z 1 零点 N个一阶零点 抵消 z 1处的一阶极点和一阶零点互相抵消 一阶零点数量变为 N 1 个 3 3 2DFT与Z变换的关系 z域内插 z 的零 极点分布 96 3 3 2DFT与Z变换的关系 F域内插 F域内插公式 由频域取样DFTX k 表示DTFTX ejw 97 即 其中 频域内插函数 频域内插公式 3 3 2DFT与Z变换的关系 F域内插 98 F内插函数的零极点分布根据 z 的零极点分布规律可知 零极点对系统频率响应的影响 极点 ej 到极点z 0的距离恒为1 对幅频特性没有影响零点 在区间 0 2 内 存在 N 1 个零值点存在 N 1 个极值点 分别为 z 的零 极点分布 3 3 2DFT与Z变换的关系 F域内插 99 插值函数的幅度特性与相位特性 N 5 DFT与Z变换的关系 F域内插 100 频域内插的物理含义 只有当频域取样点数N大于序列长度M时 中不会出现混迭现象 这时能够从中如实恢复x n 即能够由X k 准确重建X z 和X ejw 对序列作DFT变换点数不应低于序列的长度 X k 浓缩了x n 在变换域中的全部特性 DFT与Z变换的关系 F域内插 101 这里 序列长度及DFT点数均为N若不等 分别为N1 N2 则需补零使两序列长度相等 均为N 且 若两序列x1 n 和x2 n 的长度均为N 且其N点DFT分别为 则 DFT的性质 线性 a b为任意常数 102 对于周期序列 有 其中 周期共轭偶对称分量 周期共轭奇对称分量又定义 又由于则 即有限长序列由共轭偶对称和共轭奇对称两部分组成 DFT的性质 对称性 共轭奇对称分量 共轭偶对称分量 103 DFT的性质 对称性 104 若存在有限长序列x n 长度为N 其N点DFT的结果为X k 则有 证明 DFT的性质 帕斯瓦尔定理 该定理表明 可利用序列的DFT结果表示信号的能量 序列在时域计算的能量与在频域计算的能量相等 即变换前后的能量保持不变 这进一步说明 虽然DFT有别于DTFT 但其仍然具有明确的物理含义 105 DFT的性质 反转定理 循环反转的定义如果x n 是长度为N的序列 则称x n NRN n 为x n 的循环反转运算 循环反转运算是有限长序列所特有的一种运算 其结果仍然是集合 0 1 N 1 上的有限长序列 特别注意n 0时情况 计算过程 1 补零为N 2 周期延拓 3 纵轴镜像 4 取主值序列 106 DFT的性质 反转定理 循环反转的DFT 若 则 证明 107 DFT的性质 序列的循环移位 圆周移位 循环移位的定义 称其为循环移位的原因在于 当序列从一端移出范围时 移出的部分又会从另一端移入该范围 线性移位 若N点序列沿一方向线性移位 它将不再位于区间0 n N 1上 108 DFT的性质 序列的循环移位 圆周移位 有的书上称为圆周移位 把x n 看作排列在N等分的圆周上 循环移位就相当于序列x n 在圆周上移动 故称为圆周移位 实际上重复观察几周时 看到的就是周期序列 109 例 设x n 10 0 8 n 0 n 10为11点序列 a 画出x n 4 11R11 n 也就是向左循环移位4个样本的序列 b 画出x n 3 15R15 n 也就是假定x n 为15点序列 向右循环移位3个样本 DFT的性质 序列的循环移位 圆周移位 110 b 在这种情况下 给x n 后填充4个零 将其看作一个15点序列 此时的循环移位与N 11时不同 看起来像线性移位x n 3 因此 序列的周期长度是非常重要的一个参数 DFT的性质 序列的循环移位 圆周移位 111 结论 有限长序列的循环移位 在离散频域中只引入了一个和频率成正比的线性相移 对幅频特性没有影响 DFT的性质 序列循环移位后的DFT 若 则 证明 112 时域序列的调制等效于频域的循环移位 DFT的性质 频域循环移位后的IDFT 频域循环移位后的IDFT 调制特性 由DFT所具有的对偶特性不难看出 在频域内循环移位时 将有类似的结果 即 证明 113 DFT的性质 频域循环移位后的IDFT 证明 114 DFT的性质 循环卷积 圆周卷积 循环卷积定义 设x1 n 和x2 n 都是长度为N的有限长序列 把它们分别拓展为周期序列和 定义循环卷积为 周期序列卷积后取主值 115 因为上式的求和范围是m由0到N 1 因此第一个序列x1 m 可以不作周期拓展 即注意两个N点序列的线性卷积将导致一个更长的序列 而循环卷积将区间限制在0 n N 1 结果仍为N点序列 它与线性卷积的结构类似 不同点在于求和范围和N点循环移位 它与N有关 也叫做N点循环卷积 DFT的性质 循环卷积 圆周卷积 N 窗函数限定了循环卷积的范围 116 循环卷积过程 1 补零 2 周期延拓 3 反转 取主值序列 循环反转 4 对应位相乘 然后求和 得到n 0时的卷积结果 5 向右循环移位 圆周移位 6 重复 n 1 N 1 DFT的性质 循环卷积 圆周卷积 注意n 0时的循环反转 117 循环卷积的时频映射关系由DTFT的性质可知 两个序列时域上的线性卷积运算在频域上表现为两个序列DTFT结果的乘积 同样的 若则即当在频域中进行两个N点DFT相乘时 在时域中映射为循环卷积 而不是通常的线性卷级 DFT的性质 循环卷积 圆周卷积 118 证明 将X1 k 和X2 k 作周期延拓 分别得到X1 k N和X2 k N 则 再设 于是 DFT的性质 循环卷积 圆周卷积 令 119 因为 所以 此时上式最后一个求和号中 已不对r求和 故此求和号可以去掉 因此 因而 即 DFT的性质 循环卷积 圆周卷积 120 利用时域 频域的对偶性可得频域循环卷积 若 则 时域循环卷积可在频域中完成 DFT的性质 循环卷积 圆周卷积 121 1 同心圆法 2 利用求周期卷积的作图法 3 解析式法 4 Matlab方法 DFT的性质 循环卷积计算方法 122 同心圆法可用两个同心圆来表示 x1 n 内圆顺时针方向排列x2 n 外圆逆时针方向排列x1 0 与x2 0 对齐 DFT的性质 循环卷积计算方法 123 两圆上对应数两两相乘后求和 得x3 0 将x2 n m 移位一位 即外圆顺时针转动一位 重复 1 步骤 得x3 1 依次下去 求得 DFT的性质 循环卷积计算方法 124 作图法 1 x1 m 和x2 m 在m轴上周期延拓 成为 2 将反转 3 计算周期卷积 4 取一个周期 得到 DFT的性质 循环卷积计算方法 125 上述过程 只需将x1 n 和x2 n 分别做周期延拓 得到和 再按照计算周期卷积的作图法 计算出n由0到N 1的周期卷积 即为循环卷积 126 DFT的性质 循环卷积计算方法 例 设x1 n 1 2 2 x2 n 1 2 3 4 计算4点循环卷积解 注意x1 n 为3点序列 进行循环卷积之前在其尾部填一个零 使其成为4点序列 分别在时域和频域中求解这个问题 127 1 时域方法4点循环卷积由下式给出对每个n产生一个循环移位序列 将它的样本逐个与x1 m 相乘 然后求和 得此n值的循环卷值 在0 n 3上重复此过程 考虑x1 m 1 2 2 0 和x2 m 1 2 3 4 n 0时 DFT的性质 循环卷积计算方法 注意此为x2 0 而不是 4 3 2 1 128 n 2时 DFT的性质 循环卷积计算方法 n 3时 因此 129 2 频域方法 首先计算x1 n 和x2 n 的4点DFT 逐个样本相乘 取IDFT 得到循环卷积 DFT的性质 循环卷积计算方法 则 注意 X1 k 和X2 k 对应位相乘 IDFT后 得 表面看来 这样做反而更复杂 且涉及复数运算 但后面我们会看到 DFT有快速算法FFT 特别是当N很大时 效率会显著提高 130 利用DFT求离散线性卷积条件 N N1 N2 1方法 时域转换到频域 处理后再转换回时域用DFT进行信号频谱分析参数选择频谱泄漏栅栏效应 DFT的应用 131 DFT的应用 线性卷积求解 132 线性卷积 N点循环卷积 DFT的应用 线性卷积求解 循环卷积和线性卷积的关系 133 讨论线性卷积y n x n h n 的长度从x m 看 非零值区为 0 m N 1从h n m 看 非零值区为 0 n m M 1将二不等式相加 得到y n 的非零区 0 n M N 2在此区间之外 不是x m 0 就是h n m 0 即y n 0 因此 y n 的长度为M N 1 DFT的应用 线性卷积求解 134 讨论循环卷积的长度循环卷积是周期卷积的主值序列 为了研究长度不等的两个序列的周期卷积 构造周期序列 使它们的长度相等 且均为L 表示为 DFT的应用 线性卷积求解 135 周期卷积如下 周期卷积是线性卷积的周期延拓 周期为L 当周期为L N M 1时 不会发生混迭 线性卷积正好是周期卷积的一个周期 循环卷积又是周期卷积的主值序列 DFT的应用 线性卷积求解 因为 即0 m L 1范围内x m qL 只有一个周期 136 由于循环卷积是周期卷积的主值序列 因此 此时循环卷积与线性卷积完全相同 即 因此 循环卷积等于线性卷积的条件是 即对于N长度的x n M长度的h n 在它们后面补零 使其长度均变为L M N 1 DFT的应用 线性卷积求解 137 138 讨论 若序列的长度为 序列的长度为 且有大于 那么 和的点循环卷积结果为 其中 139 此时 两序列的线性卷积结果的长度 对其在时域作周期为的延拓相加得到序列 主值序列的前个点存在混迭 因此 在中也就是说 序列中最后个点与两序列的线性卷积结果相同 140 答 1 7 19点 2 27点 141 即时域循环卷积频域相乘 DFT的应用 线性卷积求解 设 若 则 用DFT求解线性卷积 142 如果循环卷积的长度N满足N N1 N2 1 则此循环卷积Y k 就等于x n 和h n 的线性卷积 用流程图表示法求y n x n h n 的过程如下 因为DFT IDFT都有快速算法 因此 线性卷积可以实现快速算法 DFT的应用 线性卷积求解 143 DFT的应用 线性卷积求解 乘法次数循环卷积 在上述DFT求解线性卷积过程中 需要3次DFT FFT 运算 后面我们会讲到N点FFT所需要的乘法次数为 因此 用DFT求线性卷积所需要的总的乘法次数 线性卷积 每一个输入值x n 都必须和全部的h n 值乘一次 因此 总共需要N1N2次乘法运算 ML N1N2 设 若N1 N2时 则 144 DFT的应用 线性卷积求解 结论 N1 N2越长 循环卷积的优越性越大 但当其中一个序列很长时 例如x n 当很长时 即 这时 Cm下降 循环卷积快速算法的优点不能发挥出来 克服的办法 分段卷积将长序列分段 每一段分别与短序列进行循环卷积 即用FFT运算 分为重叠相加法 重叠保留法 145 线性卷积求解小结时域直接求解 z变换法 DFT法 DFT的应用 线性卷积求解 146 上面介绍的是两个有限长序列x1 n x2 n 的线性卷积 但有时其中某个序列会很长或无限长 若等长序列存储或输入完后再做卷积运算 将产生问题 1 存储量过大 运算量也太大 2 等待输入的时间很长 引起不能忍受的延迟 3 采用DFT FFT快速算法的效率降低 具体方法 重叠保留法 重叠相加法 解决此问题的思路 把长序列分段 每一分段分别与短序列进行卷积 分段卷积 DFT的应用 分段卷积 147 误差分析在分析分段卷积之前 我们首先分析两个有限长度序列的循环卷积的误差情况 设x n 为N1点序列 h n 为N2点序列 由前面分析知道 线性卷积y n 和循环卷积yC n 关系为 DFT的应用 分段卷积 一般地讲 循环卷积是线性卷积的一种混叠形式 但当N N1 N2 1 没有混迭产生 此时线性卷积y n 和循环卷积yN n 相等 148 为了用DFT计算线性卷积 必须选择适当的N 但实际中却可能做不到这一点 尤其是当一个序列的长度很大而存储空间有限时 当选择比所需要的小的N值进行循环卷积时 会引入误差 下面我们计算此误差的大小 DFT的应用 分段卷积 首先N max N1 N2 假设此时 循环卷积yc n 的取值范围为而线性卷积y n 的非零范围为 149 有上式可知 误差为 DFT的应用 分段卷积 150 因为max N1 N2 N N1 N2 1 上面的求和式中只剩下对应于r 1的项 其它的r值超出了max N1 N2 N N1 N2 1 因此 一般来讲 如果x n 和h n 为因果序列 则y n 也为因果序列 即 因此 DFT的应用 分段卷积 151 它说明当时 样本n处的误差与线性卷积中第n N个样本相等 N1 N2 1 个样本后 线性卷积结果为零 这说明循环卷积中的头M个样本存在误差 M等于线性卷积长度和循环卷积长度之差 而剩下的则为正确的线性卷积样本 DFT的应用 分段卷积 0 循环卷积长度N N1 N2 1 N y n 线性卷积长度N1 N2 1 循环卷积的错误样本 152 此结论在用分段处理法实现长卷积时是非常有用的 DFT的应用 分段卷积 错误样本数 线性卷积长度 循环卷积长度 153 例 设x1 n 和x2 n 是两个四点序列 x1 n 1 2 2 1 x2 n 1 1 1 1 计算当N 6 5 4时的循环卷积 并在每种情况下 验证它们的误差 DFT的应用 分段卷积 154 当N 5时 得到5点序列的循环卷积为 DFT的应用 分段卷积 当N 4时 得到4点序列的循环卷积为 155 重叠保留法 对输入x n 预处理基本思路假设把序列x n 分成多段N点序列 一个系统的脉冲响应为M点序列 M N 由上面的结论可知 输入分段序列和脉冲响应之间的N点循环卷积产生该段的输出序列 其中前 M 1 个样本不是正确的输出值 若将x n 简单地分成互不重叠的各段 则所得的输出序列会有不正确样本区间存在 输入数据如何分段 结果如何处理 DFT的应用 重叠保留法 156 为了解决这个问题 将x n 分为长度N1的分段 然后每段再往前多取 M 1 个样本 即第k段的最后M 1点保留下来作为第 k 1 段的前M 1点 各段长变为 其中最前面的一段x0 n 在其前面补上M 1个零 使其长度也为N 其中任一段xk n 与h n 进行N点卷积运算 循环卷积 DFT的应用 重叠保留法 相应的周期卷积的周期为 N N1 M 1 线性卷积 157 yk n 的长度为 DFT的应用 重叠保留法 158 DFT的应用 重叠保留法 159 将每一段所得到的循环卷积的前M 1个值去掉 保留后面的N1个值 再将各段保留的N1个值前后拼接起来 就得到所要求的线性卷积y n DFT的应用 重叠保留法 因此 循环卷积yk n 的前M 1个值是线性卷积yk n 前面的M 1个值与yk 1 n 后面M 1个值的混迭 是错误的样本 循环卷积yk n 的后N1个值才与yk n 中间的N1个值相同 160 这种通过将与相重叠的部分舍去 即舍去循环卷积yk n 中前M 1项 保留后面的N1个数值 来得到所求结果的方法称为重叠保留法 有的书中又称为重叠舍去法 DFT的应用 重叠保留法 161 例 设x n n 1 0 n 9 h n 1 0 1 按N 6用重叠舍去法计算y