信息论基础 第三章 数据压缩与信源编码I.pptVIP

信息论基础 杜春娟 ducj@scnu.edu.cn QQTel第三章 数据压缩和信源编码  练习：有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F, 求这些码中哪些是唯一可译码； 求哪些码是即时码； 对所有唯一可译码求出其平均码长 几种编码方法 1. 香农编码 2. 费诺编码 3. 哈夫曼编码 最佳码: 定义:能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合. 香农指出，选择每个码字的长度 K i满足下式 I (xi )≤ K i＜I(xi)+1， 就可以得到这种码。这种编码方法称为香农编码。 编码方法如下： (1) 将信源消息符号按其出现的概率大小依次排列  p(x1)≥p(x2)≥…≥p (xn)  (2) 确定满足下列不等式的整数码长K i：  (3) 为了编成唯一可译码，计算第i个消息的累加概率  (4) 将累加概率Pi变换成二进制数。 (5) 取Pi二进数的小数点后K i位即为该消息符号的二进制码字。 1.香农编码方法 例1：设信源共7个符号消息，其概论和累加概率如图所示。以i＝4为例， －log0.17≤K4 ≤ －log0.17+1 2.56≤K4 ≤3.56 则K4＝3 则累加概率P4＝0.57, 变换为二进制为：0.1001…… 故第四个消息的编码码字为100 其他码字可类似求出，见下页图 1.香农编码方法 1.香农编码方法 各码字之间至少有一位数字不同，故是唯一可译码； 7个码字都不是延长码，故是即时码 这里L＝1，m＝2 平均码长为： 平均信息传输率为： 1.香农编码方法 香农码实用性如何？ 例2 设信源有3个符号，概率分布为（0.10.5, 0.4, 0.1） 根据香农编码方法求出各个符号的码长分别为：？ 码字分别为？ 1.香农编码方法 计算得码长分别为（1，2，4） 概率分布分别为（0，10，1110） 但实际上直观可看出（0，10，11）是更短的码，也是惟一可译码 所以，由此可知，香农编码的冗余度稍大，实际应用价值不强，但由于它是从编码定理直接得来，具有理论意义 另外当 左边等号成立时，编码效率比较高 2.费诺编码方法 编码过程如下：  (1) 将信源消息符号按其出现的概率大小依次排列： p(x1)≥p(x2)≥…≥p(xn)。 (2) 将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。 (3) 将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。 (4) 如此重复，直至每个组只剩下一个信源符号为止。 (5) 信源符号所对应的码字即为费诺码。 2.费诺编码方法 例 3 对例1的信源进行费诺编码，过程见下页表 平均码长为： 平均信息传输率为： 显然费诺要比香农的平均码长小 消息的传输速率大，说明编码效率高。 2.费诺编码方法 3.哈夫曼编码方法 编码过程如下： (1) 将n个信源消息符号按其出现的概率大小依次排列， p(x1)≥p(x2)≥…≥p(xn) (2) 取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。 (3) 对重排后的两个概率最小符号重复步骤(2)的过程。 (4) 不断继续上述过程，直到最后两个符号配以0和1为止。 (5) 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。 3.哈夫曼编码方法 3.哈夫曼编码方法 哈夫曼编码方法得到的码并非是唯一的。造成非唯一的原因如下： 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差 3.哈夫曼编码方法 例4 设有离散无记忆信源 3.哈夫曼编码方法 香农-费诺-埃利斯编码 将香农编码中的累加概率换成修正累加概率即可得到相应的香农-费诺-埃利斯编码： (1) 计算出各个信源符号的修正累加概率 (2) 按下式计算第