信息论第十讲

第三章：信源编码（一）

离散信源无失真编码§3.1信源及其分类§3.2离散无记忆（简单）信源的等长编码§3.3离散无记忆（简单）信源的不等长编码§3.4最佳不等长编码§3.5算术编码和LZ编码2023/9/301§3.4最佳不等长编码（最佳不等长编码是平均码长最小的不等长编码。本节的结论是：Huffman编码法得到的D元码，是最佳不等长D元编码。鉴于证明的复杂性，以下只证明：Huffman编码法得到的2元码，是最佳不等长2元编码。）

寻找最佳不等长编码，就是在唯一可译的前提下，使得2元码的平均码长最小。实际上是求解整数规划问题2023/9/302§3.4最佳不等长编码补充引理1信源随机变量的最佳2元异字头码，一定是信源随机变量的最佳2元不等长码。证明设最佳2元异字头码的码字长度依次为n1、n2、…、nK。则任意m1、m2、…、mK，满足码字长度依次为m1、m2、…、mK的2元不等长码的平均码长=码字长度依次为m1、m2、…、mK的2元异字头码的平均码长≥码字长度依次为n1、n2、…、nK的2元异字头码的平均码长。得证。2023/9/303§3.4最佳不等长编码补充引理2设信源随机变量U的2元异字头码S。设事件a的概率qa

≤事件b的概率qb；事件a的码字长度na

≤事件b的码字长度nb。将事件a与事件b交换码字，则平均码长不增加。证明（1）交换码字前，两个码字对平均码长的贡献为qana+qbnb；（2）交换码字后，两个码字对平均码长的贡献为qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)≥0。这就是说，交换码字前两个码字的贡献≥交换码字后两个码字的贡献；因此，交换码字使平均码长不增加。2023/9/304§3.4最佳不等长编码补充引理3设信源随机变量U的2元异字头码S。对码S进行如下的变换：（1）取出一个概率最小的事件a；在剩下的事件中取出一个概率最小的事件b。（2）找出一个最长的码字，将该码字与事件a的码字交换位置。此时事件a的码字就是一个最长的码字。（3）在事件a的码字之外找出一个最长的码字，将该码字与事件b的码字交换位置。此时事件b的码字就是一个除了事件a的码字之外最长的码字。对码S进行如上的变换后变成了码T。则码T是2元异字头码，且码T的平均码长≤码S的平均码长。证明补充引理3是补充引理2的简单推论。2023/9/305§3.4最佳不等长编码补充引理4设信源随机变量U的2元异字头码T，满足有一个概率最小的事件a，其码字最长；除事件a以外剩下的事件中有一个概率最小的事件b，其码字最长。对码T进行如下的变换：如果事件a和事件b的码字长度相等，则不做任何操作；如果事件a的码字长度大于事件b的码字长度，则将事件a的码字截掉尾部，使其与事件b的码字长度相等。对码T进行如上的变换后变成了码V。则码V是2元异字头码，且码V的平均码长≤码T的平均码长。2023/9/306§3.4最佳不等长编码证明设事件a的码字长度大于事件b的码字长度。现将事件a的码字截掉尾部，使其与事件b的码字长度相等。事件a的新码字是事件a的旧码字的字头，因此它不是其它码字；（即它不是其它码字的假字头）事件a的新码字仍然是最长码字，因此它不是其它码字的真字头；其它码字不是事件a的旧码字的字头，因此其它码字不是事件a的新码字的字头。综上所述，码V是2元异字头码。另外显然有：码V的平均码长≤码T的平均码长。得证。2023/9/307§3.4最佳不等长编码补充引理5设信源随机变量U的2元异字头码V，满足有两个概率最小的事件a和事件b，它们的码字最长且相等。分以下三种情形对码V进行如下的变换：①如果事件b的码字与事件a的码字仅仅最后一位不同，则不做任何操作；②如果另一个事件c的码字与事件a的码字仅仅最后一位不同，则将事件b的码字与事件c的码字交换；③如果没有一个码字与事件a的码字仅仅最后一位不同，则将事件b的码字换为与事件a的码字仅仅最后一位不同。2023/9/308§3.4最佳不等长编码对码V进行如上的变换后变成了码W。则：码W是2元异字头码，且码W的平均码长=码V的平均码长。2023/9/309§3.4最佳不等长编码证明在情形①或情形②之下，结论显然正确。在情形③之下，事件b的新码字不等于其它码字；（即事件b的新码字不是其它码字的假字头，其它码字也不是事件b的新码字的假字头）事件b的新码字仍然是最长码字，因此它不是其它码字的真字头；其它码字不是事件a的码字的真字头，因此其它码字不是事件b的新码字的真字头。综上所述，码W是2元异字头码。此外显然有码W的平均码长=码V的平均码长。得证。2023/9/3010§3.4最佳不等长编码补充引理6设信源随机变量U有K个事件，K≥3。设信源随机变量U的2元异字头码W，满足有两个概率最小的事件a和事件b，它们的码字最长且相等，仅仅最后一位不同。将事件a与事件b合并成一个事件e，e的概率为事件a与事件b的概率之和；而将信源随机变量U的其它事件和其对应的概率保持不变。这样得到了新的信源随机变量U’。将事件e的码字定义为事件a的码字去掉最后一位；而将码W中其它事件的码字保持不变。这样得到了U’的2元码X。则码X是U’的2元异字头码，且码X的平均码长=码W的平均码长-事件a的概率-事件b的概率。2023/9/3011§3.4最佳不等长编码证明因为K≥3，所以码W中事件a的码字长度≥2。码X中事件e的码字是码W中事件a的码字的字头，因此它不等于其它码字。（即事件e的码字不是其它码字的假字头，其它码字也不是事件e的码字的假字头）码X中事件e的码字不是其它码字的真字头。（不然的话，码W中事件a的码字或事件b的码字就是那个其它码字的字头了。矛盾）其它码字不是码X中事件e的码字的真字头。（因为码X中事件e的码字的真字头同时又是码W中事件a的码字的真字头）综上所述，码X是U’的2元异字头码。此外显然有码X的平均码长=码W的平均码长-事件a的概率-事件b的概率。2023/9/3012§3.4最佳不等长编码补充定理

设信源随机变量U有K个事件，K≥3。取出两个概率最小的事件：事件a和事件b。将事件a与事件b合并成一个事件e，e的概率为事件a与事件b的概率之和；而将信源随机变量U的其它事件和其对应的概率保持不变。这样得到了新的信源随机变量U’。找到信源随机变量U’的一个最佳2元异字头码Q。将码Q中事件e的码字后面分别添加0和1，分别作为事件a和事件b各自的码字；而将码Q中其它事件的码字保持不变。这样得到了信源随机变量U的2元码R。则：码R是U的最佳2元异字头码。2023/9/3013§3.4最佳不等长编码证明首先说明，码R是U的2元异字头码。码R中，事件a的码字不是事件b的码字的任何字头，事件b的码字也不是事件a的码字的任何字头。（两个码字长度相同，仅仅最后一位不同）事件a的码字或事件b的码字不是任何其它码字的任何字头（因为码Q中事件e的码字不是任何其它码字的任何字头）任何其它码字不是事件a的码字或事件b的码字的任何字头。（因为事件a的码字或事件b的码字的字头，要么是码字本身，要么是码Q中事件e的码字的字头）综上所述，码R是U的2元异字头码。2023/9/3014§3.4最佳不等长编码其次，任取U的