信息论与编码-第五章(续1)详解.ppt

信息论与编码-信源编码 最佳编码 香农第一定理给除了信源熵与编码后的平均码长之间的关系，同时也指出可已通过编码使平均码长达到极限值，因此，香农第一定理是一个极限定理。但定理中并没有告诉我们如何来构造这种码。 下面我们介绍三种编码方法：香农码、费诺码以及哈夫曼编码。这三种码的平均码长都比较短。 信息论与编码-信源编码 1. 香农(Shannon)编码方法 因为平均码长是各个码的概率平均，可以想象，应该使出现概率大的信源符号编码后码长尽量短一些。三种编码方法的出发点都是如此。 香农第一定理指出，选择每个码字的长度满足下式 就可以得到这种码。这种编码方法称为香农编码。 香农编码是采用信源符号的累计概率分布函数来分配码字。 信息论与编码-信源编码 设信源符号集 ，并设所有的P(x)0， 则香农编码方法如下： (1)将信源消息符号按其出现的概率大小依次排列： (2)确定满足下列不等式的整数码长 ： (3)为了编成唯一可以码，计算第 个消息的累加概率 信息论与编码-信源编码 (4)将累加概率 变换成二进制数。 (5)取 二进制数的小数点后 位即为该消息符号的二进制码字。 可以证明，这样得到的编码一定是唯一可译码，且码长比较短，接近于最佳编码。 信息论与编码-信源编码 例题：设信源共有 7个符号组成，其 概率如表所示， 求其香农码。 信源消息符号 符号概率 0.20 0.19 0.18 0.17 0.15 0.10 0.01 信息论与编码-信源编码 符号概率 累加概率 码字长度 码 字 0.20 0 2.34 3 000 0.19 0.2 2.41 3 001 0.18 0.39 2.48 3 011 0.17 0.57 2.56 3 100 0.15 0.74 2.74 3 101 0.10 0.89 3.34 4 1110 0.01 0.99 6.66 7 1111110 信息论与编码-信源编码 以 为例， 累加概率 ，变成二进制数，为0.1001…， 转换的方法是：用 乘以2，如果整数部分有进位，则小数点后第一位为1，否则为0，将其小数部分再做同样的处理，得到小数点后的第二位，依此类推，直到得到了满足要求的位数，或者没有小数部分了为止。 信息论与编码-信源编码 例如现在 ，乘以2为1.14，整数部分有进位，所以小数点后第一位为1，将小数部分即0.14再乘以2，得0.28，没有整数进位，所以小数点后第二位为0，依此类推，可得到其对应的二进制数为0.1001…。 可以看出，编码所得的码字，没有相同的，所以是非奇异码，也没有一个码字是其它码字的前缀，所以是即时码。唯一可译码。 信息论与编码-信源编码 平均码长为： 平均信息传输率为 香农编码的效率不高，实用意义不大，但对其它编码方法有很好的理论指导意义。 信息论与编码-信源编码 2. 费诺编码方法 费诺编码也不是最佳编码方法，但有时可以得到最佳编码。 费诺编码方法如下： 首先，将信源符号以概率递减的次序排列起来，将排列好的信源符号分成两组，使每一组的概率之和相接近，并各赋予一个二元码符号“0”或者“1”； 信息论与编码-信源编码 然后，将每一组的信源符号再分成两组，使每一小组的符号概率之和也接近相等，并又分别赋予一个二元码符号。 依此下去，直到每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。 例题：信源符号及其概率仍如香农码中的例题所示。编码过程及编码结果如下表所示， 信息论与编码-信源编码 消息符号 符号概率 第一次分组 第二次分组 第三次分组 第四次分组 二元码字 码长 0.20 0 0 00 2 0.19 1 0 010 3 0.18 1 011 3 0.17 1 0 10 2 0.15 1 0 110 3 0.10 1 0 1110 4 0.01 1 1111 4 信息论与编码-信源编码 可以求得，该费诺码的平均码长为 信源熵为 信息传输率为 例题：离散无记忆信源及其符号概率分布如下表所示，求其费诺码。 求费诺码的过程也表示在表中。码的平均长度为 信源的熵为 因此是最佳码。原因是概率分布满足一定的条件。 信息论与编码-信源编码 信息论与编码-信源编码 信源符号 符号概率 第一次分组 第二次分组 第三次分