信息论第十讲

《信息论第十讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章：信源编码（一）离散信源无失真编码§3.1信源及其分类§3.2离散无记忆（简单）信源的等长编码§3.3离散无记忆（简单）信源的不等长编码§3.4最佳不等长编码§3.5算术编码和LZ编码8/10/20211§3.4最佳不等长编码（最佳不等长编码是平均码长最小的不等长编码。本节的结论是：Huffman编码法得到的D元码，是最佳不等长D元编码。鉴于证明的复杂性，以下只证明：Huffman编码法得到的2元码，是最佳不等长2元编码。）寻找最佳不等长编码，就是在唯一可译的前提下，使得2元码的平均码长最小。实际上是求解整数规划问题2§3.4最佳

2、不等长编码补充引理1信源随机变量的最佳2元异字头码，一定是信源随机变量的最佳2元不等长码。证明设最佳2元异字头码的码字长度依次为n1、n2、…、nK。则任意m1、m2、…、mK，满足码字长度依次为m1、m2、…、mK的2元不等长码的平均码长=码字长度依次为m1、m2、…、mK的2元异字头码的平均码长≥码字长度依次为n1、n2、…、nK的2元异字头码的平均码长。得证。3§3.4最佳不等长编码补充引理2设信源随机变量U的2元异字头码S。设事件a的概率qa≤事件b的概率qb；事件a的码字长度na≤事件b的码字长度nb。将事件a与事件b交换码字，

3、则平均码长不增加。证明（1）交换码字前，两个码字对平均码长的贡献为qana+qbnb；（2）交换码字后，两个码字对平均码长的贡献为qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)≥0。这就是说，交换码字前两个码字的贡献≥交换码字后两个码字的贡献；因此，交换码字使平均码长不增加。4§3.4最佳不等长编码补充引理3设信源随机变量U的2元异字头码S。对码S进行如下的变换：（1）取出一个概率最小的事件a；在剩下的事件中取出一个概率最小的事件b。（2）找出一个最长的码字，将该码字与事件a的码字交换位置

4、。此时事件a的码字就是一个最长的码字。（3）在事件a的码字之外找出一个最长的码字，将该码字与事件b的码字交换位置。此时事件b的码字就是一个除了事件a的码字之外最长的码字。对码S进行如上的变换后变成了码T。则码T是2元异字头码，且码T的平均码长≤码S的平均码长。证明补充引理3是补充引理2的简单推论。5§3.4最佳不等长编码补充引理4设信源随机变量U的2元异字头码T，满足有一个概率最小的事件a，其码字最长；除事件a以外剩下的事件中有一个概率最小的事件b，其码字最长。对码T进行如下的变换：如果事件a和事件b的码字长度相等，则不做任何操作；如果事

5、件a的码字长度大于事件b的码字长度，则将事件a的码字截掉尾部，使其与事件b的码字长度相等。对码T进行如上的变换后变成了码V。则码V是2元异字头码，且码V的平均码长≤码T的平均码长。6§3.4最佳不等长编码证明设事件a的码字长度大于事件b的码字长度。现将事件a的码字截掉尾部，使其与事件b的码字长度相等。事件a的新码字是事件a的旧码字的字头，因此它不是其它码字；（即它不是其它码字的假字头）事件a的新码字仍然是最长码字，因此它不是其它码字的真字头；其它码字不是事件a的旧码字的字头，因此其它码字不是事件a的新码字的字头。综上所述，码V是2元异字头

6、码。另外显然有：码V的平均码长≤码T的平均码长。得证。7§3.4最佳不等长编码补充引理5设信源随机变量U的2元异字头码V，满足有两个概率最小的事件a和事件b，它们的码字最长且相等。分以下三种情形对码V进行如下的变换：①如果事件b的码字与事件a的码字仅仅最后一位不同，则不做任何操作；②如果另一个事件c的码字与事件a的码字仅仅最后一位不同，则将事件b的码字与事件c的码字交换；③如果没有一个码字与事件a的码字仅仅最后一位不同，则将事件b的码字换为与事件a的码字仅仅最后一位不同。8§3.4最佳不等长编码对码V进行如上的变换后变成了码W。则：码W是

7、2元异字头码，且码W的平均码长=码V的平均码长。9§3.4最佳不等长编码证明在情形①或情形②之下，结论显然正确。在情形③之下，事件b的新码字不等于其它码字；（即事件b的新码字不是其它码字的假字头，其它码字也不是事件b的新码字的假字头）事件b的新码字仍然是最长码字，因此它不是其它码字的真字头；其它码字不是事件a的码字的真字头，因此其它码字不是事件b的新码字的真字头。综上所述，码W是2元异字头码。此外显然有码W的平均码长=码V的平均码长。得证。10§3.4最佳不等长编码补充引理6设信源随机变量U有K个事件，K≥3。设信源随机变量U的2元异字头

8、码W，满足有两个概率最小的事件a和事件b，它们的码字最长且相等，仅仅最后一位不同。将事件a与事件b合并成一个事件e，e的概率为事件a与事件b的概率之和；而将信源随机变量U的其它事件和其对应的概