第五章 无失真源编码13.ppt

A 0 0 1 1 1 0 00 10 11 0 1 010 011 即时码 由此可见： 结论：当进行哈夫曼编码时，为了得到质量好的码，应使合并的信源符号位于缩减信源序列尽可能高的位置，这样可充分利用短码。 r元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只是编码过程中构成缩减信源时，每次将r个概率最小的符号合并，并分别用0，1，…，r-1码元表示。 为了充分利用短码，使哈夫曼码的平均码长最短，必须是最后一个缩减信源有r个信源符号。因此，对于r元哈夫曼码，信源S的符号个数q必须满足 如果信源S的符号个数q不满足上式，则增补一些概率为0的信源符号。 四.r元哈夫曼码 例5-9：有一离散无记忆信源 码元集X=(0,1,2)，对S进行3元哈夫曼编码。 解： 信源符号 概率 编码过程 码字Wi 码长li Si p(Si) S1 S2 Wi li S1 0.4 0.4 0.4 0 1 S2 0.3 0.3 0.3 2 1 S3 0.2 0.2 0.3 10 2 S4 0.05 0.05 12 2 S5 0.025 0.05 110 3 S6 0.025 111 3 S7 0 112 3 2 1 0 2 1 0 2 1 0 霍夫曼编码的特点： 1）由于霍夫曼编码总是以最小概率相加的方法来缩减参与皮埃对的概率个数，因此概率越小，对缩减的贡献越大，其对应消息的码字也越长。 2）最小概率相加的方法使得编码不具有唯一性，尤其是碰到存在几个消息符号有着相同概率的情况，将会有多种路径选择，即既具有多种可能的代码组集合。 3）尽管对同一信源存在着多种结果的霍夫曼编码，但它们的平均码长几乎都是相等的，因为每一种路径选择都是使用最小概率相加的方法，其实质都是遵循最佳编码的原则，因此霍夫曼编码是最佳编码。 霍夫曼编码存在的问题： 1）霍夫曼编码要求信源消息概率已知或可估计。由于初始信源不可能总是统计好了概率，为此编码之前必须先估算信源的统计特性。在信源具有记忆性能并用霍夫曼编码来表示信源的扩展输出时，概率的估计很耗费时间。 2）霍夫曼编码是建立在编码器和译码器都知道码树结构的基础上的，如果信源消息数目变大，则树型结构的大小和算法的复杂性会呈指数规律增加。 五.Lemple-Ziv编码 例5-10： 待编码的字符序列为：abaaaabaabaaabbbbbbbabbbbbaababaababa……..,试用Lemple-Ziv方法给出编码结果。 … aababa aabab bbbb ab bbb bb aabb aaba aab aa b a 码段内容 … 12 11 10 9 8 7 6 5 4 3 2 1 地址 … 11b 5b 8b 1b 7b 2b 4b 4a 3b 1a 0b 0a 编码结果 由此可知：Lemple-Ziv编码利用了已编码信息进行当前的编码，编码结果是等长码，编码过程就是建立码地址和将待编码消息序列分段的过程，所有的码段内容都是不同的。 例5-11：若有一信源： 每秒钟发出2.66个信源符号，将此信源