4 信息编码与理论基础 信息率失真函数.ppt

第四章信息率失真函数 4 1基本概念4 2离散信源的信息率失真函数4 3连续信源的信息率失真函数4 4保真度准则下的信源编码定理 2 4 1基本概念 4 1 1失真函数与平均失真度4 1 2信息率失真函数的定义4 1 3信息率失真函数的性质率失真函数的定义域率失真函数对允许平均失真度的下凸性率失真函数的单调递减和连续性 3 引入限失真的必要性 失真在传输中是不可避免的连续信源的绝对熵为无限大 若要无失真地进行传输 则要求信息传输率也为无限大 然而现实世界中信道带宽总是有限的 信道容量总有一定限度 因此不可能实现完全无失真的信源信息的传输另一方面 从无失真信源编码考虑 由于要求码字包含的信息量不小于信源的熵 所以对于连续信源 要用无限多个比特才能完全无失真地来描述 这是不现实的即使是离散信源 若要处理的信息量很大 采用无失真编码将使得信息的存储和传输成本非常高 而且在很多场合 过高的信息传输率是不必要的 4 引入限失真的必要性 续 信宿只具有有限的的分辨能力与灵敏度 超过分辨能力与灵敏度的信息传送过程是毫无意义的例1 由于人耳能够接收的带宽和分辨率是有限的 因此对数字音频传输的时候 就允许有一定的失真 并且对欣赏音乐没有太大的影响例2 对于数字电视 由于人的视觉系统的分辨率有限 并且对低频比较敏感 对高频不太敏感 因此也可以损失部分高频分量例3 放映电影 理论上要完全无失真地表现出一个连续动作 需要用无穷多个静态画面连续放映 但利用人眼的 视觉暂留性 只要每秒钟连续放映24幅静态画面 就几乎让观众感觉不到失真的存在 5 引入限失真的必要性 续 如果允许信息有某些失真 就可以大大降低信息传输速率 从而降低通信成本 在允许一定程度失真的条件下 怎样用尽可能少的码符号来表达信源的信息 也就是信源熵所能压缩的极限或者说编码后信息传输率压缩的极限值是多少 保真度准则下的离散信源编码定理 在允许一定失真度D的情况下 信源输出的信息传输率可压缩到极限值 信息率失真函数R D 6 失真函数 由于本章学习内容只涉及信源编码问题 因此可以把从信源编码器到信源译码器之间的所有部件合在一起等效为一个有噪声的试验信道 试验信道 7 对每一对 xi yj 指定一个非负的函数 失真函数 续 称为单个符号的失真度或失真函数 表示离散信源发出一个符号xi而在接收端再现成yj所引起的误差和失真 上述非负的失真函数共有n m个 可以整体表示成失真矩阵 由于信源发出的符号X和信宿收到 再现 的符号Y均是随机变量 因此单个符号的失真函数d xi yj 也是随机变量 的一次实现 8 常用的失真函数 失真函数是根据人们的实际需要和失真引起的损失 风险 主观感觉上的差别等因素人为规定的 可以有多种形式 平方误差失真函数 绝对误差失真函数 相对误差失真函数 误码失真函数 平方失真和绝对失真只与 yj xi 有关 而不是分别与xi yj有关 在数学处理上比较方便 相对失真与主观特性比较匹配 因为主观感觉往往与客观量的相对数成正比 但其数学处理比较困难误码失真函数表明 只要发送符号与接收符号不同 由此引起的失真都相同 为常数a 若常数值为1 则称为汉明失真 适用于离散信源 9 平均失真度 由于单个符号的失真函数d xi yj 是随机变量 的一次实现 它只能表示两个特定的具体符号xi yj之间的失真 无法从整体上描述信道平均每传递一个符号所引起失真大小定义平均失真度为失真函数的数学期望 即d xi yj 在X和Y的联合概率空间P XY 中的统计平均值 平均失真度与信源统计特性 信道统计特性和规定的失真度有关 如果信源和失真度给定以后 就只是信道统计特性的函数 如果规定平均失真度不超过某一允许失真的上界D 最大允许平均失真度 简称允许平均失真度 则称 为保真度准则 满足保真度准则的限定条件下 求信息传输率的最小值 10 符号序列的失真度 若信源是单符号离散无记忆信源的N次扩展 其限失真编码可视为N长随机序列经由单符号离散无记忆信道的N次扩散信道 再现为N长的随机序列 N长输入符号序列与N长输出符号序列间的失真函数 由于N次扩展信源和N次扩展信道都是无记忆的 因此 11 符号序列的平均失真度 符号序列的平均失真度 符号序列的保真度准则 12 4 1 2信息率失真函数的定义 在单符号信源已知并规定了单符号失真度后 并非所有的信道都能满足保真度准则 凡满足保真度准则的信道称为D失真许可试验信道 所有的D失真许可试验信道构成集合 对于离散无记忆N次扩展信源和N次扩展信道 相应的D失真许可试验信道为 对于固定的信源分布 平均互信息是信道转移概率的下凸函数 也就是说 存在一个信道使给定的信源经过此信道传输时 信道的平均互信息达到最小信源限失真编码后的信息传输率R就是通过试验信道的平均互信息I X Y 为了便于传送和处理 人们总是希望将信息传输率R压缩到最小 13 信息率失真函数的定义 续 给定信源和失真度后 在所有的D失真许可试验信道中 寻找一个信道使得从输入端传送过来的信息量最小 这个最小的平均互信息称为信息率失真函数R D 简称率失真函数 在研究R D 时 计算I X Y 所用的条件概率并没有实际信道的含义 只是为了求平均互信息的最小值而引用的 假想的可变试验信道的信道特性 实际上这些信道反映的仅是不同的限失真信源编码 或称信源压缩R D 是在限定允许平均失真为D时信源最小信息传输率 可以通过改变试验信道特性来达到 实质上是选择一种限失真信源编码方式使试验信道的信息传输率为最小 即在满足保真度准则下 使信源的压缩率达到最高 14 率失真函数的定义域 D的下界 允许失真度D是平均失真度的上限 而是非负函数的数学期望 因此D的下界至多为0 对应于无失真的情况 此时信息传输率应等于信源输出的信息熵 即 D能否达到下界0 与单个符号的失真函数有关 在给定的失真矩阵中 对每一个xi 找一个yj与之对应 使d xi yj 最小 不同的xi对应的最小d xi yj 也不相同 相当于在失真矩阵的每一行找一个最小的d xi yj 然后对各行不同的d xi yj 求统计平均值 就是信源平均失真度上限的下界 显然 如果失真矩阵的每一行至少有一个0元素 信源平均失真度上限D的下界才能取到0 15 率失真函数的定义域 D的上界 R D 是在一定约束条件下平均互信息I X Y 的最小值 由于I X Y 是非负的 其下界为至多为0如果不允许失真 平均传送一个信源符号所需的信息传输率最大 R D 可以达到信源熵 反之如果允许一定的失真 则信息传输率可以小一些 或者说信息传输率越小 容忍的平均失真度越大显然 当R D 达到下界0时 允许的平均失真度最大 由于满足R D 0的D可以有无穷多个 定义使R D 0成立的最小的D值为率失真函数的定义域的上界Dmax当R D 0时 最小的I X Y 0 这相当于X和Y相互统计独立的情况 这意味着接收端收不到信源发送的任何信息 与信源不发送任何信息是等效的 所以在理论上 传送信源符号的信息传输率可以压缩至0 16 率失真函数的定义域 Dmax的计算 如果试验信道的转移概率满足即X和Y相互统计独立 等效于信道关闭或者信源不发任何消息 此时必有 从而 用不同的输出概率分布对求数学期望 取最小的那一个作为 如果在中找到最小的 当该j对应的而其余的输出概率为0时 上式计算出的值最小 即 17 率失真函数R D 的定义域为 Dmin Dmax 一般情况下 Dmin 0 R Dmin H X 当D Dmax时 R D 0当D Dmin Dmax 时 0 R D H X 18 率失真函数对允许平均失真度的下凸性 19 新试验信道在所有满足保真准则的信道集合中并不一定是达到率失真函数 使平均互信息达到最小 的信道 固定信源X 平均互信息I X Y 是信道转移概率的下凸函数 因此R D 在定义域内是允许平均失真度D的下凸函数 即 20 率失真函数的连续性 由数学分析理论 定义在开区间上的凸函数必是连续函数 知 定义域为 Dmin Dmax 且具有下凸性的R D 是连续函数 首尾相连的弦线斜率是递增的 21 由于允许的平均失真越大 所要求的信息率就可以越小率失真函数R D 是在平均失真度小于或等于允许平均失真度为D的所有试验信道组成的集合PD中 取平均互信息I X Y 的最小值当允许的平均失真度增大后 集合PD也随之扩大 它当然仍包含原来满足保真度准则的所有信道 这时再在扩大的PD集合中挑选I X Y 的最小值 显然新挑选出最小值或者不变 或者变小 所以率失真函数R D 是单调非增的以下将通过证明率失真函数R D 在定义域 Dmin Dmax 内不可能为常数从而证明率失真函数是严格单调递减的函数 率失真函数的单调递减性 22 23 新试验信道在所有满足保真准则的信道集合中并不一定是达到率失真函数的信道 因此 R D I X Y 满足保真准则 固定信源 平均互信息是信道转移概率的下凸函数 所以 综上分析可知 时 可见在区间上不是常数 原假设不成立 24 根据率失真函数所具有的下凸性 连续性 严格单调下降性可绘出率失真函数的典型曲线图 率失真函数曲线的一般形式 对于连续信源 R 0 曲线不与R D 相交R Dmin H X 及R Dmax 0决定了率失真函数曲线边缘的两个交点 25 4 2离散信源的信息率失真函数 由率失真函数的定义可知 求解R D 实质上是求解平均互信息的条件极值 与求信道容量C类似 可以采用拉格朗日乘子法求解 R D 是求解I X Y 的条件极小值 具体而言 给定信源概率分布p x 和失真函数d x y 在满足保真度准则的试验信道集合PD中选择信道转移概率p y x 使I X Y 最小 需要满足以下n 1个限定条件 很难求解出I X Y 条件极小值的显式表达式 在一般情况下只能求得用参量 R D 的斜率S 来描述的参量表达式 并借助计算机进行迭代运算 26 4 2 1离散信源信息率失真函数的参量表达式 27 28 29 30 31 4 2 2二元及等概率离散信源的信息率失真函数 32 33 二元离散信源率失真函数曲线 34 多元等概率离散信源的率失真函数 35 4 3连续信源的信息率失真函数 4 3 1连续信源信息率失真函数的参量表达式4 3 2高斯信源的信息率失真函数4 3 3信息率失真函数与信息价值4 3 4信道容量与信息率失真函数的比较 36 4 3 1连续信源信息率失真函数的参量表达式 37 4 3 1连续信源信息率失真函数的参量表达式 续 38 4 3 2高斯信源的信息率失真函数 39 40 41 42 43 4 3 3信息率失真函数与信息价值 同样的信息对不同的接收者其 客观 信息量是相同的 但对不同的接收者其价值是有差别的尽管信息率失真理论只研究客观信息量 不涉及信息对接收者有着不同的价值 但如果把平均失真理解为平均损失 据此定义信息价值 就可以用信息论解决许多实际问题 例某印刷电路板 PCB 加工厂的产品合格率约为98 一块好的PCB板出厂价约为100元 但如果客户发现一块不合格的板子可向厂方索赔10000元 已知厂方检验员检验的正确率约为95 假设合格品出厂 废品报废都不造成损失 以下用信息率失真理论来分析检验的作用并作比较 解根据题意 可将PCB产品作为一信源 记生产的PCB板为随机变量X 检验员的检测结果为Y 即 44 将平均失真度理解PCB厂的平均损失 并定义如下失真函数 产品不经检验而出厂 都当合格品 即这种情况每销售出去一块PCB板 加工厂将要另外承担可能损失200元的风险 考虑到每块销售100元 实际上是每卖出一块可能要实际净损失100元 45 产品不经检验全部报废 都当废品 即每生产一块PCB板 加工厂将有损失98元的风险 因为把98 本来可以卖100元一块的板子也报废了 比较以上两种情况可知 做出全部报废决定造成的损失 要小于做出全部出厂决定所造成的损失 不做任何检验 在全部出厂和全部报废两者之间抉择 选择后者的损失反而小 如果选择 则 产品无需进行质量管理 相当于信源没有输出任何信息量 46 正确无误地判断合格品和废品 完美的检验 以下探讨每1比特信息量的价值 该式说明 如果从每块PCB板上获取0 14144比特的信息量 就可以避免一切细小的损失 可能造成的最大损失为98元 块 所以0 14144比特信息量的最大价值为98元 则每1比特信息的最大价值为 一般将全部产品都报废的可能性极小 实际的损失要小于98元 块 完全无误的检验因其高昂的代价 所提供的单位信息价值不一定是最高的 47 检测时允许有一定的错误 非完美的检验 即这种情况每销售出去一块PCB板 加工厂将要另外承担可能损失14 9元 块的风险 考虑到每块销售100元 实际上是每卖出一块实际收益至少是85 1元 这种情况和最大损失 98元 相比 损失减少了98 14 9 83 1元 块 Why 由于在检验的过程中获取了一定的信息量 检验的过程好比 信道 获取的信息量也就是平均互信息I X Y 48 通过允许有错的检验 平均而言从对每块PCB板的检验中只获取了0 07202比特的信息量 但是其损失比不检验时减少