3无失真信源编码

第三章无失真信源编码 3 1编码的相关概念3 2定长编码定理3 3变长编码定理3 4最佳编码 无失真信源编码 为什么要对进行编码 1 信源发出的消息符号可能不适合信道的传输 将信源发出的消息符号转换为适合信道传输的符号 2 信源消息确定后 提高通信的有效性 信源编码 3 提高通信的可靠性 编码具有发现错误或纠正错误的抗干扰能力 信道编码 4 提高通信的安全性 加密编码 3 1编码的相关概念 3 1 1信源编码的定义3 1 2信源编码的研究方法3 1 3编码相关概念3 1 4唯一可译码的存在条件 编码的相关概念 信源编码的定义信源编码定义 指定能够满足信道特性 适合于信道传输的符号序列 码序列 来代表信源输出的消息 完成编码功能的器件称为编码器 离散信源输出的码序列离散信源输出的消息是由一个个离散符号组成的随机序列 信源符号序列 X X1X2 Xl XL Xl x1 x2 xi xn 信源编码就是把信源输出的随机符号序列变成码序列 Y Y1Y2 Yk YK Yk y1 y2 yj ym 信源编码的研究方法 研究方法研究信源编码时 将信道编码和译码看成是信道的一部分 而突出信源编码 信道 信源编码的研究方法 研究信道编码时 将信源编码和译码看成是信源和信宿的一部分 而突出信道编码 信源 信宿 信源编码的研究方法 讨论无失真信源编码可以先不考虑抗干扰问题 所以它的数学模型比较简单 如图所示 编码相关概念 码元和码字码元 符 集 信道可传输的基本符号的集合 记为Y 设Y有m个符号 Y y1 y2 ym 其中yi称为码元或码符 m元信道 可传输m个基本符号的信道 二元信道 可传输2个基本符号的信道 这是一种最常用的信道 基本符号常用0 1表示 码字 由码元组成的序列称为码字 记为Yi 码字Yi的码元个数Ki称为Yi的码长 所有码字Yi的码长Ki均相等称为定长码 码字Yi的码长Ki不全相等称为变长码 编码相关概念 编码与译码信源编码 将信源符号xi或符号序列X按一种规则映射成码字Yj的过程 无失真编码 信源符号到码字的映射必须一一对应 译码 从码符号到信源符号的映射 码表 所有映射规则的集合 编码相关概念 许用码和禁用码许用码字 信源的符号xi或符号序列X与码字Yj定义了对应关系的码字 禁用码字 信源的符号xi或符号序列X与码字Yj未定义对应关系的码字 许用码字的全体称为码集 编码相关概念 分组码 块码 分类按码字的码长分类定长码 码集中所有码字的码长相等 变长码 码集中所有码字的码长不全相等 按信源符号与码字对应关系分类非奇异码 信源符号与码字是一一对应的 奇异码 信源符号与码字不是一一对应的 编码相关概念 分类 按译码唯一性分类唯一可译码 对于多个码字组成的有限长码流 只能唯一地分割一个个的码字 唯一可译码又称为单义码 唯一可译码在传输过程中不需要同步码 非唯一可译码 对有限长码流 不能唯一地分割一个个的码字 例 码流100111000 码1 x1 0 x2 10 x3 11可分割10 0 11 10 0 0码2 x1 1x2 10 x3 11则无法唯一分割 编码相关概念 分类 按译码的即时性分类非即时码 接收端收到一个完整的码字后 不能立即译码 还需要等到下一个码字开始接收后才能判断是否可以译码 即时码 接收端收到一个完整的码字后 就能立即译码 即时码又称为非延长码或异前缀码 例 非即时码 码流01001100 x1 0 x2 01x3 11译码为x2 x1 x1 x3 x1 即时码 码流01001100 x1 0 x2 10 x3 11译码为x1 x2 x1 x3 x1 x1 结论 即时码指的是码集任何一个码不能是其他码的前缀 即时码必定是唯一可译码 唯一可译码不一定是即时码 编码相关概念 分类 举例 例 码1 显然不是惟一可译码 x2和x4对应于同一码字 11 码1本身是一个奇异码 码2 是非奇异码 不是惟一可译码 当收到一串码符号 01000 时 可将它译成 x4x3x1 也可译为 x4x1x3 x1x2x3 或 x1x2x1x1 等 这种码从单个码字来看虽然不是奇异的 单从有限长的码序列来看 它仍然是一个奇异码 码3 虽然是惟一可译码 但它要等到下一个 1 收到后才能确定码字的结束 译码有延时 码4 既是惟一可译码 又没有译码延时 码字中的符号 1 起了逗点的作用 故称为逗点码 前缀条件码 异前置码 异字头码 逗点码 即时码 非延长码 如果一个码的任何一个码字都不是其它码字的前缀 唯一可译码的存在条件 码树图码树图 用码树来描述给定码集各码字的方法 码树图有树根 树枝 节点 一般中间节点 一级节点 二级节点 用 表示 终端节点用 表示 传输m个基本符号信道的码可用 例 二元 进制 码树 x1 1x2 01x3 001 唯一可译码的存在条件 码树图 如果节点过多 也可以用如下方法表示码树图 唯一可译码的存在条件 码树图 用码树图构造码的方法在树的生长过程中 中间节点生出树枝 各树枝标出相应的码元 为了清晰起见相同码元的树枝方向相同 终端节点表示信源符号 从树根到终端节点所经过的树枝旁的码元按经过的顺序组成的序列构成码字 用码树图构造即时码的条件如果表示信源符号的终端节点不再延伸 即信源符号都在终端节点上 这样构造的码满足即时码条件 唯一可译码的存在条件 前提条件 非奇异码唯一可译码存在定理 设n为信源符号或信源符号序列个数 m为码元个数或进制数 Ki为信源各符号或信源符号序列对应的码长 则唯一可译码存在的充分和必要条件是满足Kraft不等式 注意 Kraft不等式是一个存在定理 不是唯一可译码的判定定理 如果n m Ki满足该不等式 则存在唯一可译码如果是唯一可译码 则n m Ki必定满足该不等式 唯一可译码的存在条件 例 设二进制码树中X x1 x2 x3 x4 K1 1 K2 2 K3 2 K4 3 应用上述判断定理 可得 因此 不存在满足这种Ki的唯一可译码 用树码进行检查如图所示 唯一可译码的存在条件 信息率若信源输出符号序列长度L 1变换成由KL个符号组成的码序列 码字变换要求 能够无失真或无差错地从Y恢复X 同时传送Y时所需要的信息率最小 唯一可译码的存在条件 信息率 Yk有m种可能值 能编成的码字个数所以平均每个符号输出的最大信息量为logm KL长码字最大信息量为KLlogm 用该码字表示长度为L的信源序列 则送出一个信源符号所需要的信息率平均为 所谓信息率最小 就是找到一种编码方式使KLlogm L最小 几个问题 信息率最小为多少时 才能无失真译码 若小于这个信息率是否还能无失真译码 3 2定长编码定理 3 2 1平均码长和编码有效性3 2 2定长编码定理 平均码长和编码有效性 平均码长单符号信源空间 其中信源符号xi对应的码字为Yi i 1 2 n 码字Yi对应的码长为Ki i 1 2 n 所有的Ki相等为定长码 记为K 不相等时为变长码 单符号对应变长码的平均码长 码符 信源符号 平均码长和编码有效性 平均码长 符号序列信源空间XL其中XL是X的L次扩展 信源符号序列对应的码字为Yi i 1 2 nL 码字Yi对应的码长为Ki i 1 2 nL 符号序列对应变长码的平均码长 码符 信源符号序列 码符 信源符号 平均码长和编码有效性 编码效率 编码效率 码率 定义 平均一个码符所携带的平均信息量称为编码效率 记作 平均码长和编码有效性 例 信源空间H X 1 2log1 2 1 4log1 4 1 8log1 8 1 8log1 8 1 75bit 消息信源符号个数为n 4 二元码符 0 1 码符个数为m 2 Ki为信源各符号对应的码字长 且满足Kraft不等式 定长码 K1 K2 K3 K4 22 2 2 2 2 2 2 2 1码字 Y1 00 Y2 01 Y3 10 Y4 11编码效率 H X K 1 75 2 0 825 平均码长和编码有效性 举例 变长码 K1 1 K2 2 K3 3 K4 3满足不等式 2 1 2 2 2 3 2 3 1码字 Y1 0 Y2 10 Y3 110 Y4 111方案1 x1 0 x2 10 x3 110 x4 111 1 1 2 2 1 4 3 1 8 3 1 8 1 75码符 信源符号 1 75 1 75 1方案2 x1 111 x2 110 x3 10 x4 0 3 1 2 3 1 4 2 1 8 1 1 8 2 625码符 信源符号 1 75 2 625 0 667 平均码长和编码有效性 讨论1 为什么定长码的编码效率小于1 而变长码的编码效率能达到1 原因 因为H X 1 75 是个小数 而定长码的码长不可能为小数 所以编码效率小于1 除非H X 为整数 但变长码的平均码长可以为小数 可能等于H X 平均码长和编码有效性 讨论2 编码后码字集合确定 符号对应的码字长度不同 为什么编码效率不同 原因 不同符号的先验概率不同 对应的码字长度不同 计算出的平均码长也不同 编码效率也就不同 总结 一般情况下 变长编码的编码效率可能达到1 对于变长编码 若概率大的符号对应短码 概率小的符号对应长码 编码效率越高 反之越低 这也是后面最佳编码的思路 定长编码定理 定理 由L个符号组成的 每个符号的熵为HL X 的无记忆平稳信源符号序列X1X2 Xl XL 可用KL个符号 每个符号有m种可能值 进行定长编码 对任意 0 0 只要 则当L足够大时 必可使译码差错小于 反之 当时 译码差错一定是有限值 而当L足够大时 译码几乎必定出错 定长编码定理 定理中的公式改写成表明 不等式左边表示长为KL的码字能载荷的最大信息量 右边代表长为L的信源序列平均携带的信息量 所以定长编码定理告诉我们 只要码字传输的信息量大于信源携带的信息量 总可实现几乎无失真编码 定长编码定理 信源熵HL X 就是一个界限 临界值 当编码器输出的信息率超过这个临界值时 就能无失真译码 否则就不行 信源编码定理从理论上说明了编码效率接近于1 即的理想编码器的存在性 代价是在实际编码时取无限长的信源符号 L 进行统一编码 只要 足够小 就可实现几乎无失真译码 若 足够小 编码效率就接近于1 说明 定长编码定理是在平稳无记忆离散信源的条件下论证的 但它同样适用于平稳有记忆信源 只是要求有记忆信源的极限熵和极限方差存在即可 对于平稳有记忆信源 定理中的熵应改为极限熵 定长编码定理 定长编码L计算随机变量I xi I xi 的数学期望M I xi 即H X I xi 的方差 2 X 符号序列长度L 已知编码效率 和译码错误概率 定长编码定理 例 设单符号信源模型为信源熵为 H X 2 55 比特 符号 自信息方差为 2 x 1 323若要求编码效率为90 即译码差错率为 10 6 则由此可见 在差错率和效率要求都不苛刻的情况下 就必须有1600多万个信源符号一起编码 技术实现非常困难 3 3变长编码定理 变长编码定理 单个符号变长编码定理 若一离散无记忆信源的符号熵为H X 每个信源符号用m进制码元进行变长编码 一定存在一种无失真编码方法 其码字平均长度K满足下列不等式 变长编码定理 单符号 证明 若xi按如下不等式取所对应码字的码长为Ki 若为整数 则上述不等式左边取等号 故可得 变长编码定理 单符号 所有码字长度满足Kraft不等式 如何降低平均码长 1 减少信源熵H X 2 增加信道码元数m 变长编码定理 离散平稳无记忆序列变长编码定理 对于平均符号熵为HL X 的离散平稳无记忆信源 必存在一种无失真编码方法 使平均信息率K满足不等式 证明 信源X的L次扩展信源XLXL的信源熵为H XL bit L个信源符号XL所对应码字的码长码符 L个信源符号 变长编码定理 证明 编码效率的下界 码的剩余度 变长编码定理 举例 例 设单符号信源模型为其信息熵为 H X 2 55 比特 符号 这里m 2 log2m 1要求 90 则 结论 与定长编码相比 对同一信源 要求编码效率都达到90 时 变长编码只需L 4进行编码 而等长码则要求L大于1 6875 107 用变长编码时 L不需要很大就可以达到相当高的编码效率而且可实现无失真编码 变长编码定理 举例 例 设离散无记忆信源的概率空间为其信源熵为L 1定长码 x1 0 x2 1 则K 1编码效率 H X K 0 811L 2XLx1x1x1x2x2x1x2x2p XL 9 163 163 161 16H XL 1 622bit 2个符号 变长编码定理 举例 定长码XL00011011KL 2码符 2个信源符号编码效率 H XL KL H X K 0 811变长码Y010110111Ki1233 1 9 16 2 3 16 3 3 16 3 1 16 27 16 1 6875码符 2个信源符号编码效率 H X K 0 811 32 27 0 961当L 3 0 985L 4 0 991 采用扩展信源提高编码效率带来的问题 1 码表迅速扩大 2 需求内存大 3 译码延时 变长编码定理 信息传输效率平均信息率R 平均每个码元所含有的信息量 单位 bit 码元码元传输率 码元速率 RB 每秒钟传输码元的数目 单位 波特 B 码元时间长度 TB TB 1 RB单位 秒 s 平均信息传输率 Rt 平均每秒钟传输的信息量 单位 bit sRt R TB 3 4最佳编码 3 4 1香农编码3 4 2费诺编码3 4 3哈夫曼编码 最佳编码 最佳码 能载荷一定信息量 且码字的平均码长最短 可分离的码字集合 编码思路 对概率大的信息符号编以短码 对概率小的信息符号编以长码 目的 使平均码字长度最短 这种编码方法称为统计编码 熵编码 概率匹配编码 最佳编码 香农编码若单个字符xi按如下不等式取所对应码字的码长为Ki当m 2时 log2m 1 则 香农编码 编码方法 1 将信源符号消息按其出现概率的大小依次排序 p x1 p x2 p xn 2 按如下不等式取所对应码字的码长为Ki 3 计算第个i消息的累加概率 以便获得唯一可译码 4 将累加概率变换为二进制数 5 取二进制数的小数点后Ki位作为符号消息的二进制码字 香农编码 举例 例 xix1x2x3x4x5x6x7p xi 0 200 190 180 170 150 100 01编码过程 香农编码 举例 信源熵 H X 2 61bit 符号平均码长编码效率 费诺编码 编码方法 1 将信源符号消息按其出现概率的大小依次排列 p x1 p x2 p xn 2 将依次排列的信源符号按其概率分为两大组 使两个组的概率之和近似相等 并对各组赋予一个码元0和1 3 按 2 方法将每一大组再分为两组 各组再赋予一个码元0和1 4 如此重复 直至每个组只剩一个信源符号为止 5 信源符号所对应的码字即为Fano码 费诺编码 举例 例 xix1x2x3x4x5x6x7p xi 0 200 190 180 170 150 100 01编码过程 费诺编码 举例 信源熵 H X 2 61bit 符号平均码长编码效率 哈夫曼编码 编码方法 1 将信源符号消息按其出现概率的大小依次排序 p x1 p x2 p xn 2 取两个概率最小的符号分别配以0和1 并将这两个概率相加作为新字母的概率 与未分配的字母重新排序