信息论与编码07-最佳信源编码

《信息论与编码07-最佳信源编码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章　信源编码1.香农编码2.费诺编码3.哈夫曼编码10/6/20211电信学院汪汉新本章节教学内容、基本要求、重点与难点1.教学内容：信源编码的概念。三种最佳的信源编码。2.教学基本要求：掌握香农编码。掌握费诺编码。掌握哈夫曼编码。3.重点与难点：信息率，平均码长和编码效率的计算。多进制哈夫曼编码。10/6/20212电信学院汪汉新引言香农编码定理虽然指出了理想编码器的存在性,但是并没有给出实用码的结构及构造方法；编码理论正是为了解决这一问题而发展起来的科学理论；编码的目的是为了优化通信系统，使通信系统的性能指标有效性、可靠性、安全性和经济性达

2、到最佳；10/6/20213电信学院汪汉新按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码（加密编码）。信源编码：提高信息传输的有效性。通常通过压缩信息的冗余度来实现。信道编码：提高信息传输的可靠性。通常通过增加信息的冗余度来实现。与信源编码正好相反。加密编码：提高通信系统的安全性。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。10/6/20214电信学院汪汉新信源编码信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。香农第一定理（无失真信源编码定理）：是离散信源/数

3、字信号编码的基础；香农第三定理（限失真信源编码定理）：是连续信源/模拟信号编码的基础。信源编码的分类：离散信源编码：可做到无失真编码；连续信源编码：只能做到限失真信源编码；10/6/20215电信学院汪汉新无失真信源编码定理：定长编码定理：一个熵为H(X)的离散无记忆信源X1X2…Xl…XL，对信源长为L的符号序列进行定长编码，设码字是从m个信源符号集内选取K个码元组成Y1Y2…Yk…YK。对于任意ε>0，δ>0只要满足(K/L)log2m≥H(X)+ε则当L足够大时，必可使译码差错小于δ，即译码错误概率能为任意小。变长编码定理：(K/L)log2

4、m≥H(X)+ε，其中K为平均码长。限失真信源编码定理：对于给定的失真D，总可以找到一种信源编码方法，只要传输速率R大于R(D)，就可以在平均失真任意接近D的条件下实现波形重建。说明1：R(D)称为率失真函数，它是单调非增函数，速率越高，平均失真越小。说明2：为了保证在一定速率下的失真，必需采用信源编码，因而会引入编码延时。编码理论10/6/20216电信学院汪汉新香农编码设离散无记忆信源二进制香农码的编码步骤如下(4步)：将信源符号按概率从大到小的顺序排列p(x1)≥p(x2)≥…≥p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i个

5、码字的累加概率确定满足下列不等式的整数ki，并令ki为第i个码字的长度－log2p(xn)≤ki<1－log2p(xn)将pa(xj)用二进制表示，并取小数点后ki位作为符号xi的编码。10/6/20217电信学院汪汉新[例]有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如表所示。10/6/20218电信学院汪汉新香农码的平均码长若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源的等长编码而言有0.3比特/符号的压缩。由离散无记忆信源熵定义，可计算出：对上述信源采用香农编码的信息率为编码效率

6、为信源熵和信息率之比。则可以看出，编码效率并不是很高。10/6/20219电信学院汪汉新费诺编码费诺编码也是一种常见的信源编码方法。编码步骤如下：将概率按从大到小的顺序排列，令p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。10/6/202110电信学院汪汉新[例]与香农编码一样的单符号离散信源对该信源编二进制费诺码。编码过程如表。10/6/202111电信学院汪汉新上述码字

7、还可用码树来表示，如图所示。10/6/202112电信学院汪汉新该信源的熵为平均码长为编码效率为费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。10/6/202113电信学院汪汉新[例]有一单符号离散无记忆信源对该信源编二进制费诺码，编码过程如表。10/6/202114电信学院汪汉新码树图如图信源熵为H(X)=2.75(比特/符号)平均码长为信息率编码效率为η=100%。因为每次所分两组的概率恰好相等。10/6/202115电信学院汪汉新5.4.1编码步骤哈夫曼

8、(Huffman)编码是一种效率比较高的变长无失真信源编码方法。将信源符号按概率从大到小的顺序排列，令p(x1)≥p(x2