信息论与编码第五章1.ppt

1. 香农（Shannon）编码 (1)将信源消息符号按其出现的概率大小依次排列 (2)确定满足下列不等式的整数码长Ki。 (3)为了编成唯一可译码，计算第i个消息的累加概率 (4)将累加概率Pi变换成二进制数。 (5)取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。 例5.4 设信源共7个符号消息，a1、a2 、 a3 、 a4 、 a5 、 a6 、 a7，概率分别为0.20 、 0.19 、 0.18 、 0.17 、 0.15 、 0.10 、 0.01，求香农编码。 信源熵： 信源符号的平均码长为： 编码效率为： 香农编码方法特点： 由于ki总是进一取整，香农编码方法不一定是最佳的； 码字集合是惟一的，且为即时码； 先有码字的长度再有码字； 对于一些信源，编码效率不高，多余度稍大，因此其实用性受到较大限制。 2. 费诺编码方法 费诺编码属于概率匹配编码 (1)将信源消息符号按其出现的概率大小依次排列： (2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。 (3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。 (4)如此重复，直至每个组只剩下一个信源符号为止。 (5)信源符号所对应的码字即为费诺码。 例5.5 设信源共7个符号消息，a1、a2 、 a3 、 a4 、 a5 、 a6 、 a7，概率分别为0.20 、 0.19 、 0.18 、 0.17 、 0.15 、 0.10 、 0.01，求费诺编码。 信源符号的平均码长为： 编码效率为： 例5.6 有一单符号离散无记忆信源 对该信源用费诺编码方法，求其二进制代码组及其编码效率。 该信源熵为： 平均码长： 编码效率： 费诺编码特点： 概率大，则分解的次数小；概率小, 则分解的次数多。这符合最佳编码原则。 码字集合是惟一可译码，且为即时码； 分解完了，同时可以得到码字和码长。 3. 哈夫曼编码方法 (1)将信源消息符号按其出现的概率大小依次排列， (2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。 (3)对重排后的两个概率最小符号重复步骤(2)的过程。 (4)不断继续上述过程，直到最后两个符号配以0和1为止。 (5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。 例5.7 设信源共7个符号消息，a1、a2 、 a3 、 a4 、 a5 、 a6 、 a7，概率分别为0.20 、 0.19 、 0.18 、 0.17 、 0.15 、 0.10 、 0.01，求哈夫曼编码。 5.2 无失真信源编码 0.20 0.19 0.18 0.17 0.15 0.10 0.01 信源符号的平均码长为： 编码效率为： 哈夫曼编码方法得到的码并非唯一的。 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码，此时将影响码字的长度。 例5.8 设有离散无记忆信源 求哈夫曼编码。 信源符号的平均码长为： 编码效率为： 在实际应用中，选择那种编码方法？ 我们定义码字长度的方差为ki与平均码长之差的平方的数学期望，记为?2 ，即 计算上例中两种码的方差分别得 ?21= 1.36 ?22= 0.16 可见第二种编码方法的码长方差要小许多。这意味着第二种编码方法的码长变化较小，比较接近平均码长。 进行