第5章_信源编码.ppt

第*页 * (2) 基于字典的编码方法 根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？ 是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。 5.7 LZ (Lempel-Ziv ) 码 第*页 * (3) LZ 码的原理 LZ78 的基本算法：将长度不同的符号串编成一个个新的短语（单词），形成短语字典的索引表，短语字典由前面已见到的文本定义，是一个潜在的无限列表。 LZ78 的编码算法： 设信源符号集 A={a0,a1,a2,…,aq－1}共 q 个符号 设输入信源序列 为 s1,s2,s3,…,sn si∈A 将此序列分成不同的 C 段。分段规则：尽可能取最少个连着的信源符号，并保证各段都不相同。 不同段内的信源符号可看成一短语，可得不同段对应的短语字典表. 5.7 LZ (Lempel-Ziv ) 码 第*页 * (3) LZ 码的原理 LZ78 的编码算法： 码字组成：段号＋后面一个符号 二元码：段号码长： ，每个信源符号码长： 单符号码字的段号为 0。 n—信源序列的输入长度 C(n)—输入长度为 n 的信源序列被分解成字符片段的数目 5.7 LZ (Lempel-Ziv ) 码 第*页 * (4) 举例 设 q=4，信源序列为：a0a0a2a3a1a1a0a0a0a3a2… 分段为：a0,a0a2,a3,a1,a1a0,a0a0,a3a2 共 7 段 编码字典如下表：字典共 7 段，段号 l=3 位二元码符号；q=4，每个符号需要 2 位二元码符号：a0?00，a1?01，a2?10，a3?11。 得序列符号： 00000001100001100001100000010001110 5.7 LZ (Lempel-Ziv ) 码 码符号序列译码：一边译码一边又建成字典表，字典表无需传送。 在本例中，二元序列共 35 位，似乎比不编码还坏。当序列 n 增长时段内短语的符号数也增长，尤其是某些符号重复出现的话，编码效率将会提高。 第*页 * (5) 计算 LZ78 码的平均码长的界限 信源符号序列长度 n； 段的数目：C(n)； 每段二元码符号长度： 每个信源符号码长： 每段二元码符号数： n 长信源符号序列数： 平均每个信源符号所需码长： 因此： 5.7 LZ (Lempel-Ziv ) 码 第*页 * (5) 计算 LZ78 码的平均码长的界限 设长度为 k 的段有 qk 种，最长的段的长度为 K，所有长度≤K 的段型都存在，则： 5.7 LZ (Lempel-Ziv ) 码 第*页 * (5) 计算 LZ78 码的平均码长的界限 平稳无记忆 m 元信源序列，设信源 pi(i=0,1,2…,q－1) 当 K 很大时，典型段中 ai 出现 piK 个，这种段型有 NK 种，则： 5.7 LZ (Lempel-Ziv ) 码 第*页 * (5) 计算 LZ78 码的平均码长的界限 结论：LZ78 码的平均码长仍以信源熵为极限，当 n 很长时（即 K 很大时），平均码长渐进地接近信源的熵。 5.7 LZ (Lempel-Ziv ) 码 第*页 * (1) 什么是 LZW 码？ LZW 算法是韦尔奇（T.A.Welch）对 LZ 算法的一种修正，它保留了 LZ 算法原有的自适应性。为了使长短不一的“单词”更便于处理，专门为“单词”建立了一种通用的格式。 (2) LZW 码的格式规定 每个“单词”均由前缀字符串和尾字符串两部分组成。 前缀字符串为字典中已有的“单词”，尾字符是本“单词”的最后一个字符。 对本身已经是单节的“单词”，没有前缀词时则在前面加上一个空前缀，并规定字典最后一个“单词”为“空”。 5.8 LZW 码 第*页 * (3) LZW 码的编码方法 “单词”的内容用3个字节表示：前缀字符串(2字节)＋尾字符(1字节) 5.8 LZW 码 第*页 * (3) LZW 码的编码方法 初始化时将字典的前256个单元依次分给 0x00 至 0xFF 的256个字节字符; 每读入一个字符 W1，先在字典中查找，若这个字符字典已有，则更新当前词为 W1，且以当前词 W1 做前缀，再读入一个字符 W2 做尾字符，组成一个单词 W1W2，再次在字典中查找，若字典中没有 W1W2，则输出 W1位置码，并将 W1W2 添加到字典中。 然后将 W2 做当前词，重复以上步骤，直到没有字符读入时，完成编码. LZW 算法在储存压缩文件时，不需要保存字典，是一种自适应的算法。 5.8 LZW 码 第*页 * (4) LZW 码的译码 LZW 的译码算法同样