第五章 信源编码 信息论和 与编码 课件.pptVIP

例 设有一单符号离散信源 对该信源编二进制费诺码。编码过程如下表。 5.4变长码 二进制费诺编码 信源符号 概率 编码 码字 码长 x 1 0.25 0 00 2 x 2 0.25 0 1 01 2 x 3 0.20 0 10 2 x 4 0.15 0 110 3 x 5 0.10 0 1110 4 x 6 0.05 1 1 1 1 1111 4 大概率用短码 该信源的熵为 平均码长为 编码效率为 本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。 5.4变长码 题中码字还可用码树来表示，如图所示。 5.4变长码 5.4变长码 例 设有一单符号离散信源 对该信源编二进制费诺码。 5.4变长码 平均码长 编码效率 信源熵 H(X)=2.75 bit/sign 每次两分组的概率正好相等 (1) 将信源符号按概率从大到小的顺序排列，令 p(a1)≥ p(a2)≥…≥ p(an) (2) 给两个概率最小的信源符号p(an-1)和p(an)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(q－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 (3)将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(q－2)个符号的缩减信源S2。 (4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 5.4变长码 Huffman编码步骤 例 设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码 在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是唯一可译码。若从前向后读取码字，则码字不是唯一可译码。 将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。 5.4变长码 1 001 011 0101 0100 0000 00010 00011 5.4变长码 信源熵为： 平均码长为 编码效率为 若采用定长编码，码长K=3，则编码效率 可见哈夫曼的编码效率提高了12.7%。 注意：哈夫曼的编法并不惟一。 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长不变，平均码长也不变，所以没有本质区别； 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。 5.4变长码 例：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。 5.4变长码 方法一：合并后的新符号排在其它相同概率符号的后面。 5.4变长码 这两种编码哪一种更好呢，我们来计算一下二者的码长。 方法二：合并后的新符号排在其它相同概率符号的前面。 两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。 定义码字长度的方差σ2： 5.4变长码 可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。 第一种方法编出的5个码字有4种不同的码长； 第二种方法编出的码长只有两种不同的码长； 显然，第二种编码方法更简单、更容易实现，所以更好。 结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。 5.4变长码 5.4变长码 m进制哈夫曼编码 1.编码步骤 同二进制，但需注意两点 (1)每次取最小的m个概率,分别赋以0,1,…,m-1； (2)为使平均码长最短，当对应的码树为非全树时， 第一次采用小于m个概率，此后每次均用m个概率 2.非全树时的编码 (1)全树—— 码树中,每个中间节点的后续枝数必为m (2)非全树——码树中,有些中间节点的后续枝数不足m 三进制满树 （等长码） 三进制全树 （少一根即为非全树） 苗立刚 ligangmiao@ 实验楼417 电话8048018 东北大学秦皇岛分校自动化工程系 2009年3月 第五章 信源编码 信息论基础 第五章 信源编码 5