信息率失真函数.ppt

第四章信息率失真函数 无失真信源编码和有噪信道编码 香农第一定理和香农第二定理 告诉我们 只要信道的信息传输速率小于信道容量 总能找到一种编码方法 使得在该信道上的信息传输的差错概率任意小 反之 若信道的信息传输速率大于信道容量 则不可能使信息传输差错概率任意小 但是 无失真的编码并非总是必要的 原始图像 红色图像 绿色图像 蓝色图像 原始图像和限失真图像 香农首先定义了信息率失真函数R D 并论述了关于这个函数的基本定理 定理指出 在允许一定失真度D的情况下 信源输出的信息传输率可压缩到R D 值 这就从理论上给出了信息传输率与允许失真之间的关系 奠定了信息率失真理论的基础 信息率失真理论是进行量化 数模转换 频带压缩和数据压缩的理论基础 本章主要介绍信息率失真理论的基本内容 重点讨论离散无记忆信源 给出信源的失真度和信息率失真函数的定义与性质 讨论离散信源和连续信源的信息率失真函数计算 在此基础上论述保真度准则下的信源编码定理 4 1失真测度 一 失真度从直观感觉可知 若允许失真越大 信息传输率就可越小 若允许失真越小 信息传输率需越大 所以信息传输率与 信源 编码所引起的失真 或误差 是有关的 首先讨论失真的测度 离散无记忆信源X 信源符号集X a1 a2 ar 概率分布为p x p a1 p a2 p ar 信源符号通过信道传输到接收端 接收端的接收符号集Y b1 b2 bs 对应于每一对 ai bj 我们指定一个非负的函数 称为单个符号的失真度 或失真函数 通常较小的d值代表较小的失真 而d ai bj 0表示没有失真 若信源变量X有r个符号 接收变量Y有s个符号 则d ai bj 就有r s个 它可以排列成矩阵形式 即 该失真矩阵D 是r s阶矩阵 实际这里X指的是原始的未失真信源 而Y是指失真以后的信源 如果假设X是信源 Y是信宿 那么X和Y之间必有信道 从X到Y之间实际上是失真算法 所以这里的转移概率p bj ai 是指一种失真算法 有时又把p bj ai 称为试验信道的转移概率 如图所示 例1 离散对称信源 r s 0 1 失真 信源X a1 a2 ar 接收Y b1 b2 bs 定义单个符号失真度 这种失真称为汉明失真 汉明失真矩阵是一方阵 对角线上的元素为零 即 对二元对称信源 s r 2 信源X 0 1 接收变量Y 0 1 在汉明失真定义下 失真矩阵为 例2 删除信源 信源X a1 a2 ar 接收Y b1 b2 bs s r 1 定义其单个符号失真度为 其中接收符号bs作为一个删除符号 此时 意味着若把信源符号再现为删除符号bs时 其失真程度要比再现为其他接收符号的失真程度少一半 二元删除信源r 2 s 3 X 0 1 Y 0 1 2 失真度为 例 对称信源 s r 信源X a1 a2 ar 接收Y b1 b2 bs 若失真度定义为 如果信源符号代表信源输出信号的幅度值 这就是一种平方误差失真度 它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重 其严重的程度用平方来表示 当r 3时 0 1 2 0 1 2 则失真矩阵为 上述例子说明了失真度的具体定义 一般情况下根据实际信源的失真 可以定义不同的失真和误差的度量 另外还可以按其他标准 如引起的损失 风险 主观感觉上的差别大小等来定义失真度d a b 二 序列失真度 则序列失真度定义为 三 平均失真度 信源X和信宿Y都是随机变量 故单个符号失真度d ai bj 也是随机变量 规定了单个符号失真度d ai bj 后 传输一个符号引起的平均失真 即信源平均失真度 在离散情况下 信源X a1 a2 ar 其概率分布p x p a1 p a2 p ar 信宿Y b1 b2 bs 若已知试验信道的传递概率为p bj ai 时 则平均失其度为 若平均失真度D不大于我们所允许的失真D0 即 D D0称此为保真度准则 4 2信息率失真函数及其性质 一 信息率失真函数的定义 信源给定 且又具体定义了失真函数以后 总希望在满足一定失真的情况下 使信源传输给收信者的信息传输率R尽可能地小 即在满足保真度准则下 寻找信源必须传输给信宿的信息率R的下限值 这个下限值与D有关 从接收端来看 就是在满足保真度准则下 寻找再现信源消息所必须获得的最低平均信息量 而接收端获得的平均信息量可用平均互信息I X Y 来表示 这就变成了在满足保真度准则的条件下 寻找平均互信息I X Y 的最小值 寻找平均互信息I X Y 的最小值 而PD是所有满足保真度准则的试验信道集合 因而可以在D失真许可的试验信道集合PD中寻找一个信道p bj ai 使I X Y 取极小值 由于平均互信息I X Y 是p bj ai 的U型凸函数 所以在PD集合中 极小值存在 这个最小值就是在D D0的条件下 信源进行传输的最小平均信息量 即 R D 信息率失真函数或简称率失真函数单位是 比特 信源符号 率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系 其逆函数D R 称为失真率函数 D R 表示一定信息速率下所可能达到的最小的平均失真 二 信息率失真函数的性质 允许失真度D的下限可以是零 这是不允许任何失真的情况 1 R D 的定义域 R D 的定义域为且 解 例4 设试验信道输入符号集 各符号等概分布 失真矩阵如下所示 求和以及相应的试验信道的转移概率矩阵 令对应最小失真度的 其它为 0 可得对应的试验信道转移概率矩阵为 上式中第二项最小 所以令 可得对应的试验信道转移概率矩阵为 2 R D 是关于平均失真度D的下凸函数 设为任意两个平均失真 则有 3 R D 是区间上的连续和严格单调递减函数 信息率失真函数的一般形状 4 3离散无记忆信源的信息率失真函数 已知信源的概率分布p x 和失真函数d x y 就可求得信源的R D 函数 原则上它与信道容量一样 即在有约束条件下求极小值的问题 也即选取适当的试验信道p x y 使平均互信息最小化 其约束条件为 一般取等号 一 等概率 对称失真信源的R D 计算 对于等概 对称失真的信源 存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R D 解 例5 有一个二元等概平稳无记忆信源 接收符号集为且失真矩阵为 求率失真函数R D 由于信源等概分布 失真函数具有对称性 因此 存在着与失真矩阵具有同样对称性的转移概率分布达到率失真R D 该转移概率矩阵可写为 由于 因此对于任何有限平均失真 必须 于是转移概率矩阵为 对应此转移概率矩阵的平均失真 因此 可求得此时的互信息为 二 信息率失真函数的参量表述 求信源的R D 函数 原则上与求信道容量一样 是在有约束条件下求极小值的问题 也就是适当选取试验信道p y x 使平均互信息最小化 应用拉格朗日乘子法 原则上可以求出解来 困难在于 要得到显式的解析表达式 则比较困难 通常只能用参量形式来表达 要保证约束条件式p bj ai 0 应用拉格朗日乘子法解得的某些p bj ai 很可能是负的 在这情况下 必须假设其p bj ai 0 然后重新计算 这就使得计算复杂化了 下面介绍用拉格朗日乘子法求解R D 函数 并用s作为参量来表述率失真函数R s 和失真函数D s 由 1 式知 当信源的概率分布p x 固定 平均互信息仅仅是试验信道p bj ai 的函数 若先不考虑 2 式的约束 约束条件 3 式包含n个等式 取拉格朗日乘子 i i 1 2 n 分别与之对应 并取拉氏乘子s与 4 式对应 由此构成辅助函数 2 3 4 1 求极值 即为求 5 式一阶导数等于零的方程组的解 已知平均互信息I X Y 是信道P的U型凸函数 所以 若极值存在 它一定是极小值 即求 1 3 4 经整理得结论 注 这时所得的结果是以s为参量的表达式 而不是显式表达式 因而所得到的R D 的表达式也是以s为参量的表达式 参量s对应的限制条件为 4 式 它与允许的失真度D有关 所以 以s为参量就相当于以D为参量 4 例6 设离散信源 和接收变量 并设失真矩阵为 求该信源的信息率失真函数R D 解 根据 4 2 4 式计算可得 由题已知 根据参量表达式按如下步骤进行 第一步 由式 4 3 14 求 第二步 由式 4 3 13 求 第三步 由式 4 3 16 求D s 将上述结果代入式 4 3 16 有 第四步 由式 4 3 17 求R s 应用式 4 3 11 还可求得此时的试验信道转移概率 4 4连续无记忆信源的信息率失真函数 研究连续信源的信息率失真函数比离散信源更有实际意义 因为连续随机变量不可能用有限比特加以精确描述 即连续信源信息量为无限大 传送无限大信息量既无必要 也不可能 所以连续信源的讨论都属于限失真范畴 一 连续无记忆信源的信息率失真函数的定义连续信源的平均失真度定义为 通过试验信道获得的平均互信息为 同样 确定一允许失真度D 凡满足平均失真小于D的所有试验信道的集合记为PD 则连续信源的信息率失真函数定义为 二 高斯信源的信息率失真函数对高斯信源 在一般失真函数下 其率失真函数是很难求得的 但在平方误差失真度量下 其率失真函数有简单的封闭表达式 对平方误差失真 试验信道输入符号和输出符号之间失真为 对应的平均失真度为 在平方误差失真下 设允许失真为D 则高斯信源的率失真函数为 下图表示当时 的曲线 三 连续无记忆信源信息率失真函数的参量表述类似于离散信源 连续信源的率失真函数的计算也归结为求有约束极值的问题 不过在连续信源情况下试验信道的条件概率也是函数 所以 率失真函数的计算就变成求泛函的极值 即求 的极小值 满足约束条件为 约束条件下的泛函求极值问题和约束条件下的函数求极值问题类似 即利用拉格朗日乘子将问题转化为无约束极值问题 并用变分代替微分 对本节讨论的问题 等价于使下式的一阶变分为零 其中为待定函数 s为待定常数 其求解顺序完全类似于离散情况 在此我们仅给出最终结论 在连续无记忆信源下 达到信息率失真函数的试验信道的转移概率密度函数必需满足 其中 此时的率失真函数 从此意义上讲 连续信源的熵压缩编码是必不可少的 四 差值失真度量下连续无记忆信源的信息率失真函数 一般情况下 连续无记忆信源下信息率失真函数的计算相当困难 绝大多数情况下无解析解 但当连续信源的失真函数D x y 为x和y的差值形式如 x y x y 2时 可以较容易地采用参量表述式来求得其上 下限 1 差值失真度量下率失真函数的Shannon下限 上式是香农首先得到的 因此称其右端为差值失真度量时连续信源的香农下限 2 平方误差 差方 失真度量下率失真函数的上限对均值为零 方差为的任意连续无记忆信源 在差方失真度量下的率失真函数满足如下结论 4 5保真度准则下的信源编码定理 定理4 1 保真度准则下的信源编码定理 香农第三定理 设R D 为一离散无记忆信源的信息率失真函数 并且有有限的失真测度D 对于任意D 以及任意长的码长k 一定存在一种信源编码C 其码字个数为使编码后码的平均失真度 定理的含义是 只要码长k足够长 总可以找到一种信源编码 使编码后的信息传输率略大于 直至无限逼近 率失真函数R D 而码的平均失真度不大于给定的允许失真度 即 由于R D 为给定D前提下信源编码可能达到的