限失真信源编码-第16讲.ppt

2020 1 29 1 问题 假设已给定信源概率Pi和失真函数dij 在约束条件下 求信源的R D 函数的极小值问题 第二节离散信源和连续信源的R D 计算 2020 1 29 2 R D 三种特殊表示 1 当d x y x y 2 p x 时 R D 2 当d x y p x 时 R D 2020 1 29 3 3 当D x y 时 R D H p H D 2020 1 29 4 分析 1 它们都有一最大失真值Dmax 对应R D 0 当允许的平均失真D大于这最大值时 R D 当然也是零 也就是不用传送信息已能达到要求 上述三种情况的Dmax分别为和p 若p 1 2 不然就是1 p 2020 1 29 5 2 当D Dmax时 R D 就已不是零 随着D的减小 R D 单调地增加 3 当D 0 前两种情况下R D 趋于无限 这就是说 大于信息量无限大的连续信源符号 无法进行无损编码 除非信息率R趋向无限大 对于离散信源就不同 在第三种情况下 D 0时 R 0 H p 这就是无损编码时 所需的信息率不能小于信源的符号熵 2020 1 29 6 1 离散无记忆信源R D 的计算 例 已知离散无记忆信源 2020 1 29 7 解 1 2 2020 1 29 8 R D 随D的变化曲线 2020 1 29 9 结论 对于n元等概信源 有 当失真函数为对称失真时 即此时下式成立 2020 1 29 10 例 求失真函数为d x y y x 2的连续信源的Dmax和信息率失真函数R D 解 连续信源的Dmax 均方失真的连续信源的R D 因为离散信源 2 连续无记忆信源R D 的计算 2020 1 29 11 例 设某连续信源X服从高斯分布 均值 0 方差 2 失真函数为均方失真即d x y y x 2 求它的信息率失真函数R D 和Dmax 解 因此 需求Dmax 代入得 2020 1 29 12 上题的扩展 若连续信源服从 2 的高斯分布 则再求上题 解 代入得 先求Dmax 2020 1 29 13 结论 1 若失真函数为均方失真 即d x y x y 2时 连续信源的信息率失真函数 且2 同理 当失真函数为绝对失真即d x y x y 时 指数分布的连续信源 当概率密度函数为 2020 1 29 14 3 信道容量和信息率失真函数的比较 相同点 二者都是求平均互信息的极值不同点 1 1 信道容量 选择某一信源分布的情况下 求平均互信息的极大值 依据 平均互信息I是信源概率分布p xi 的严格上凸函数 2 信息率失真函数 求选择某一试验信道 转移概率分布 的情况下 依据保真度准则 求平均互信息的极小值 依据 平均互信息I是信道转移概率分布p yj xi 的严格下凸函数 2020 1 29 15 2 1 信道容量C一旦求出来 则与信源分布无关 只是证明存在这样的满足信道容量的信源分布 只和信道转移概率分布p yj xi 有关 即信道容量和信源特性无关 反映信道特性 2 信息率失真函数R D 一旦求出来 则与信道转移概率分布无关 只是证明存在达到最小信息率的试验信道 只和信源概率分布p xi 有关 即信息率失真函数和信道特性无关 反映信源特性 2020 1 29 16 限失真信源编码定理 设离散无记忆信源X的信息率失真函数为R D 则当信息率R R D 只要信源序列长度L足够长 一定存在一种编码方法 其译码失真小于或等于D 为任意小的正数 反之 若R R D 则无论采用什么样的编码方法 其译码失真必大于D 第三节限失真信源编码定理 2020 1 29 17 说明 1 如果是二元信源 对于任意小的 0 每一个信源符号的平均码长满足如下公式 则在失真限度内使信息率任意接近R D 的编码方法存在 2 该定理只能说明最佳编码是存在的 而具体构造编码方法却一无所知 因而就不能像无损编码那样从证明过程中引出概率匹配的编码方法 一般只能从优化的思路去求最佳编码 实际上 迄今尚无合适的可实现的编码方法来接近R D 这个界 2020 1 29 18 5 4 1游程编码游程编码基本思想 将任何 二元 序列变换成一一对应的游程长度序列 按哈夫曼编码或其他方法处理以达到压缩码率的目的 第四节常用信源编码方法简介 2020 1 29 19 什么叫二元序列游程和游程长度 在二元序列中 只有两种符号 即 0 和 1 这些符号可连续出现 连 0 这一段称为 0 游程 连 1 这一段称为 1 游程 它们的长度分别称为游程长度L 0 和L l 0 游程和 l 游程总是交替出现的 如果规定二元序列是以 0 开始 第一个游程是 0 游程 第二个必为 1 游程 第三个又是 0 游程等等 对于随机的二元序列 各游程长度将是随机变量 其取值可为1 2 3 直到无限 游程长度编码的主要思想是将一个相同值的连续申用其值和申长 重复的个数 的数对二元组来替代 2020 1 29 20 说明 对二元序列进行哈夫曼编码时 应先测定 0 游程长度和 l 游程长度的概率分布 或由二元序列的概率特性去计算各种游程长度的概率 2020 1 29 21 什么叫多元序列游程和游程长度 对于多元序列也存在相应的游程序列 例如m元序列中 可有m种游程 连着出现符号ar的游程 其长度L r 就是 r 游程长度 这也是一个随机变量 用L r 也可构成游程序列 但是这种变换必须再加一些符号 才能成为一一对应或可逆的 2020 1 29 22 说明 1 与二元序列变换所得的游程序列不同 这里每个 r 游程的前面和后面出现什么符号是不确定的 除r外的任何符号都是可能的 因此这一游程之后是何种符号的游程就无法确定 除非插人一个标志说明后一游程的类别 上述的附加标志可能抵销压缩编码所得的好处 对原来的多元序列直接编码 或许会更有效一些 所以把多元序列变换成游程序列再进行压缩编码是没有多大意义的 2020 1 29 23 2 一般情况下 游程长度越大 其概率越小 这在以前的计算中也可看到 而且将随长度的增大渐趋向零 对于小概率的码字 其长度未达到概率匹配或较长 损失不会太大 也就是对平均码字长度影响较小 这样就可对长游程不严格按哈夫曼码步骤进行 在实际应用时 常采用截断处理的方法 2020 1 29 24 3 游程编码只适用于二元序列 对于多元信源 一般不能直接利用游程编码 2020 1 29 25 5 4 2算术编码 算术编码的基本思路 从全序列出发 将各信源序列的概率映射到 0 1 区间上 使每个序列对应这区间内的一点 也就是一个二进制的小数 这些点把 0 1 区间分成许多小段 每段的长度等于某一序列的概率 再在段内取一个二进制小数 其长度可与该序列的概率匹配 达到高效率编码的目的 2020 1 29 26 2020 1 29 27 2020 1 29 28 这种比较一直进行到两个符号不相同为止 然后进入步骤3 2020 1 29 29 例3 假设有4个符号的信源 它门的概率如表4 07所示 表4 07符号概率 2020 1 29 30 2020 1 29 31 2020 1 29 32 图4 04算术编码概念 2020 1 29 33 5 4 3矢量量化 什么叫标量量化 连续信源进行编码的主要方法是量化 即将连续的样值x离散化成为yi i l 2 3 n n是量化级数 yi是某些实数 这样就把连续值转化为n个实数 可用0 1 2 n 1等n个数字来表示 离散信源也会涉及量化的问题 比如当提供的量化级数少于原来的量化级数时 也需要对该信源信号进行再次量化 在上述的这些量化中 由于x是一个标量 因此称为标量量化 2020 1 29 34 什么叫量化噪声 当一个样值x经量化后所产生的误差为zi x yi或yi x zi也就是在信号值x上叠加了一个样值为 zi 的噪声信号 这种噪声通常称为量化噪声 2020 1 29 35 什么叫做矢量量化 连续信源也是如此 当把多个信源符号联合起来形成多维矢量 再对矢量进行标量量化时 自由度将更大 同样的失真下 量化级数可进一步减少 码率可进一步压缩 这种量化叫做矢量量化 2020 1 29 36 5 4 4预测编码 常用信源编码方法评述 1 哈夫曼码对于独立多值信源符号很有效 2 二元序列的游程编码实际上是为了把二值序列转化成多值序列以适应哈夫曼编码 3 多个二元符号合并成一个符号的方法也有类似的情况 算术码对于独立二元信源序列是很有效的 对于相关信源虽然可采用条件概率来编码而达到高效率 但这样做所引起的复杂度 往往使之难以实现 2020 1 29 37 常用的解除相关性的两种措施 常用的解除相关性的两种措施是预测和变换 它们既适应于离散信源 也可用于连续信源 其实两者都是序列的变换 一般来说 预测有可能完全解除序列的相关性 但必需确知序列的概率特性 变换编码一般只解除矢量内部的相关性 但它可有许多可供选择的变换矩阵 以适应不同信源特性 这在信源概率特性未确知或非平稳时可能有利 2020 1 29 38 什么叫预测 预测就是从已收到的符号来提取关于未收到的符号的信息 从而预测其最可能的值作为预测值 并对它与实际值之差进行编码 达到进一步压缩码率的目的 由此可见 预测编码是利用信源的相关性来压缩码率的 对于独立信源 预测就不适用 2020 1 29 39 什么叫估计 估计就是用实验数据组成一个统计量作为某一物理量的估值或预测值 最常见的估计是利用某一物理量在被干扰下所测定的实验值 这些值是随机变量的样值 可根据随机量的概率分布得到一个统计量作为估值 若估值的数学期望等于原来的物理量 就称这种估计为无偏估计 若估值与原物理量之间的均方误差最小 就称之为最佳估计 用来预测时 这种估计就成为最小均方误差的预测 所以也就认为这种预测是最佳的 2020 1 29 40 利用预测值编码的方法可分两类 一类是差值编码 用实际值与预测值之差进行编码 常用于相关性强的连续信源 也可用于离散信源 在连续信源的情况下 就是对此差值量化 由于相关性很强的信源可较精确地预测待编码的值 这差值的方差将远小于原来的值 所以在同样失真要求下 量化级数可明显地减少 从而较显著地压缩码率 对于离散信源也有类似的情况 2020 1 29 41 另一类方法是根据差值的大小 决定是否需传送该信源符号 例如 可规定某一可容许值 当差值小于它时可不传送 对于连续函数或相关性很强的信源序列 常有很长一串符号可以不送而只需传送这串符号的个数 这样能大量压缩码率 这类方法一般是按信宿要求设计的 也就是失真应能满足信宿需求 2020 1 29 42 5 4 5变换编码 什么叫变换编码 变换编码就是经变换后的信号的样值能更有效地编码 也就是通过变换来解除或减弱信源符号间的相关性 再将变换后的样值进行标量量化 或采用对于独立信源符号的编码方法 以达到压缩码率的目的