信息率失真函数与限失真信源编码.ppt

第七章 信息率失真函数与限失真信源编码定理 本章研究内容 概述失真的度量信息率失真函数限失真信源编码定理限失真信源编码定理应用实用型信源编码香农三大定理的关系和比较 7 1 概述 1 无噪信道编码定理回顾 总可以找到一种输入分布 信源编码方法 使在无噪无损信道上 能够以信道容量C无误地传输信息 压缩冗余度 最好地利用C 限 平均码长最小值Hr S 每个码符号平均能够携带的最大信息量 7 1 概述 2 有噪信道编码定理回顾 只要R C 总可以找到一种信道编码方法 使在信道上能够以尽可能小的PE传输信息 增加冗余度 最好地匹配信道特性 限 信息传输率最大值C每个信道符号平均能够携带的最大信息量 7 1 概述 3 存在问题对于连续和模拟信源H S 信道传输率R H S n 比特 码符号 R 平均码长l Hr S H S logr l 实际上 因为B有限 C一定有限 R C 7 1 概述 4 实际需求特点 信宿对真实度的要求 实际语音信号 20Hz 8KHz人耳能够分辨 300Hz 3400Hz图象色差 可达足够多视觉分辨 256级 黑白 已足够可以允许一定的失真度完全保真没必要 7 1 概述 5 引出的研究内容限失真的信源编码问题允许一定的失真度下 能将信源信息压缩到什么程度 最少需要多少比特才能在收端描述信源 一定的信息传输率R下 可能达到的最小的平均失真是多少 相关问题失真如何度量 率失真函数如何计算 7 1 概述 6 方法 抽象 将与讨论重点关系小的部分抽象因为涉及信源编码 对信道进行抽象信道编码 信道 信道译码信道 研究失真影响时 信道 可以忽略根据信道编码定理 信道 是一个没有干扰的广义信道 信宿收到信息的失真只来自于信源编码 7 1 概述 7 方法 虚拟 将讨论重点虚拟细化将限失真信源的编译码过程虚拟信源编码过程 信道 信源译码过程试验信道可以用信道传递概率来描述限失真信源编译码前后的关系 信源编码 信道 信源译码 信源 信宿 信源 信宿 试验信道 U V P V U 7 2 失真的度量 1 失真度定义平均失真度保真度准则试验信道 7 2 失真的度量 2 失真度定义在U V联合空间上定义 d ui vj ui U vj V为U V的失真测度 d ui vj 有距离的概念性质1 ui vj时 d 0性质2 mind 0性质3 0 d 7 2 失真的度量 3 失真度定义0 ui vj离散信源 用失真矩阵描述 dij 0 ui vj0 ui vj汉明距离度量时 dij 1 ui vj连续信源 用失真函数描述 d u v u v 2 u v 7 2 失真的度量 4 平均失真度单符号失真度 d ui vj 0 i 1 r j 1 s 信源的失真矩阵可表示为 共r s个元素 7 2 失真的度量 5 平均失真度平均失真度 U V是随机变量 d ui vj 也是随机变量平均失真度 7 2 失真的度量 6 平均失真度confer d d 描述了某个信源符号通过传输后失真的大小 不同的信源符号 其d不同 描述了某一个单符号信源在某一试验信道传输下的失真 它不仅与单个符号的d有关 还与试验信道的统计特性有关 7 2 失真的度量 7 平均失真度N维信源符号序列的平均失真度 此时D为一rN sN阶的矩阵与 d u v p u p v u N均有关 7 2 失真的度量 8 平均失真度N维信源符号序列信源平均失真度信源 信道均无记忆时 信源平稳时 序列中第l个分量的平均失真度 7 2 失真的度量 9 保真度准则给定D 若 D 则称此为保真度准则对于序列信源 保真度准则为 ND 7 2 失真的度量 10 试验信道 P v u 不是实际的信道特性矩阵 在此相当于不同的编码方法 编码方法不同 不同 定义 所有 D的试验信道构成D失真许可的试验信道集合BD 7 3 率失真函数 1 问题引出度量了失真 进一步关心的问题是 一定的失真D下 最小的信息传输率R是多少 一定的失真D下 收端再现信源需要的最低的平均信息量是多少 定义 信息 率失真函数R D 对于N维序列信源 7 3 率失真函数 2 率失真函数的进一步解释单位 比特 信源符号 同互信息 离散无记忆信源 RN D NR D P v u 无实际信道含义 只代表不同编码方法求R D 就是在D条件下 选择一种编码方法 使R最小 定义域 D 0 Dmax R D 的性质 凸状性单调递减性连续性 一般情况下 Dmin 0 R Dmin H U 有条件 当D Dmax时 R D 0 而当DminR D 0 7 3 删除信道 求 7 3 率失真函数 3 7 3 率失真函数 4 Dmax与R Dmax 定义当D Dmax时 R Dmax 0使R Dmax 0的p v u 不止一个不同的p v u 有不同的对我们有意义的 具有最小的的p v u 利用该p v u 求得使R Dmax 0时的DmaxR 0时 U V统计独立p v u 只是v的函数 则有 p v u P v 例 二元信源 计算 7 3 率失真函数 5 7 3 率失真函数 6 R D 的计算求解R D 求解互信息的极小值互信息I X Y 是条件转移概率的下凸函数 极小值存在一般情况下很难得到R D 的显函数表达式 只能得到参量表达式具体计算很困难 一般利用计算机进行迭代计算 7 3 率失真函数 7 二进制对称信源的R D 计算已知条件 二进制对称信源U 0 1 接收变量V 0 1 允许的失真DP u 1 1 2汉明失真矩阵 7 3 率失真函数 8 求解步骤 由Dmin 0 找到满足最小失真的试验信道p v u 得到R 0 由汉明失真矩阵和失真度定义 计算最大允许的失真度Dmax由Dmax 找到满足最大失真的试验信道p 并得到R Dmax 在一般条件下当0 D Dmax时 计算平均失真度选取一个信道 使 D 求互信息求互信息的下限值 得到R D 验证 找到满足R D 的试验信道 验证其正确性结果分析 R D 曲线分析 7 3 率失真函数 9 对于同一个D 信源分布越均匀 R D 就越大 信源压缩的可能性越小反之 若信源分布越不均匀 即信源剩余度越大 R D 就越小 压缩的可能性就越大 二进制对称信源的R D 函数 等概信源的信息率失真函数 信源输出符号集 等概分布 输出符号集 失真函数定义为 7 3 率失真函数 10 7 3 率失真函数 11 高斯信源的R D 计算已知条件 高斯信源U 其均值为m 方差为 2 接收变量V概密函数 失真函数 均方误差失真 即 求解步骤 计算平均失真度当 D 求互信息求互信息的下限值 得到包含有D和 2的R D 表达式讨论D和 2比值不同时R D 的取值验证 找到满足R D 的试验信道 验证其正确性结果分析 R D 曲线分析 7 3 率失真函数 12 当D 2时 R D 0 即 如果允许失真等于信源的方差 则只需用均值m来表示信源输出 而不需要传送信源的任何实际输出 当D 0时 R D 即 在连续信源情况下 要毫无失真地传送连续信源必须要求信道具有无限大的容量 当D 0 25 2时 R D 1 比特 自由度 即 允许均方误差小于或等于 2 4时 连续信号的每个样本值最少需要用一个二元符号来传输 高斯信源在均方误差准则下的R D 函数 7 4 限失真信源编码定理 1 限失真信源编码定理限失真信源编码定理的证明限失真信源编码定理的实用意义 7 4 限失真信源编码定理 2 限失真信源编码定理设R D 为一离散无记忆平稳信源的信息率失真函数 并且有有限的失真测度 对于任意D 0 0 0以及任意足够长的码长n 则一定存在一种信源编码C 其码字个数为 M exp n R D 而编码后码的平均失真度 d C D 如果用二元编码 R D 取比特为单位 则上式M可写成 M 2 n R D 7 4 限失真信源编码定理 3 定理解释 对于任何失真度D 0 只要码长n足够长 总可以找到一种编码C 使编码后每个信源符号的信息传输率 R R D 即 R R D 而码的平均失真度d C D 在允许失真D的条件下 信源最小的 可达的信息传输率是信源的R D 7 4 限失真信源编码定理 4 限失真信源编码定理的证明问题 设有达到R D 的试验信道p v u 要证明对于任意的R R D 时 存在一种信息传输率为R 的信源编码 其平均失真度 D 思路 产生码书选取编译码方法计算失真度方法 产生码书 在Vn空间随机抽取M 2nR 个随机序列v编码方法 若存在与信源序列u构成失真典型序列对的序列v 则编码u v 否则编码u v 1 译码 再现v 失真度计算 在所有随机码书和Un空间统计平均的基础上计算平均失真度 7 4 限失真信源编码定理 5 限失真信源编码定理的几点说明只是一个存在性定理 没有构造方法存在问题 符合实际信源的R D 函数计算相当困难信源统计特性的确切数学描述难得符合主客观实际的失真测度难得R D 计算本身困难即使求得了R D 还需研究最佳编码方法才能达到极限值R D 7 4 限失真信源编码定理 6 限失真信源编码定理的实用意义存在性R D 的实用意义在允许一定失真的情况下 信源的R D 函数可以作为衡量各种压缩编码方法性能优劣的一种尺度 举例 举例 二进制无记忆对称信源编译码 无噪无损信道传输 举例 结论 R 1 3 比特 信源符号 该压缩编码方法下的信息传输率d C 1 4该压缩编码方法下的平均失真R 1 4 1 H 1 4 0 189 比特 信源符号 失真1 4下 最小的信息传输率R是0 189 比特 信源符号 R 1 4 R 在1 4失真度下 该压缩编码方法不是最佳的 或该信源还可以压缩 7 5 限失真信源编码定理应用 1 定理 对任一连续非正态信源 若已知其方差为 熵为 并规定失真函数为 则其R D 满足下列不等式 正态 上限 结论 在平均功率受限条件下 正态分布R D 函数值最大 它是其他一切分布的上限值 也是信源压缩比中最小的 所以人们往往将它作为连续信源压缩比中最保守的估计值 7 5 限失真信源编码定理应用 2 利用连续信源的R D 函数 分析语音的波形编码 为了分析方便 假设语音遵从平稳正态分布 例1 分析PCM编码及其压缩潜力 采样率 8KHz 量化位数 8信息率 8 8 64Kb s相关性 样点间独立 且每个样点8bit信噪比 入公用网的要求26dB 7 5 限失真信源编码定理应用 3 其中D为噪声 允许失真 功率 R D 由正态分布的信息率失真函数的公式 实际语音的R D 值要小于4 3bit 因为语音不遵从正态分布 而是近似遵从Laplace分布 一级近似 Gamma分布 二级近似 它们的R D 函数值均小于正态分布的R D 值 可见 4 3bit至现用的PCM8bit 大约有一倍差距 7 5 限失真信源编码定理应用 4 例2 若对语音编码进一步计入相关性 则其R D 函数为 则可算出其R D 值 即对应压缩比 相对于PCM编码64Kb s 若计入语音实际分布 R D 值小于正态分布值 以及R D 的主观特征 在25 26dB要求下 实际R D 值大约等于2左右 可以获得大约4倍的压缩比 结论 压缩比K 1 2 压缩比K 7 5 限失真信源编码定理应用 5 例3 参量编码 以英语为例 其音素大约为128 256个 按照通常讲话速率 每秒大约平均发出10个音素 这时语音信源给出的信息率为 7 6 香农三大定理的关系和比较 1 7 7 香农三大定理的关系和比较 2 作业 1 一个四元对称信源U接收符号为V 0 1 2 3 其失真矩阵为 求Dmax和Dmin及信源的R D 函数 并画出其曲线 取4至5个点 二元对称信源的R D 函数 已知 U 0 1 P u 1 1 2 V 0 1 1 Dmin 0 可以找到满足该最小失真的信道 且是一个无噪无损的信道 信道矩阵为 计算得 R 0 I U V H Dmin Dmax 可以找到满足该最大失真的信道 信道矩阵为 计算得 R Dmax R I U V 0 2 3 0 D D