27通用编码 分段编码L之砖 二、匹配编码 z4W算法
2.7 通用编码 一、分段编码（LZ码） 二、匹配编码 三、LZW算法
分段编码(LZ码) 特点:编码与符号概率无关。编码效率比较高 分段规则: 使连着的信源符号尽可能少,但不能出现重复段。 yj-yiur (j>i) 两个数可用一个数N;(第j段段的码字)来表示 N: =mitr
一、分段编码（LZ码） • 分段规则： 使连着的信源符号尽可能少，但不能出现重复段。 yj=yiur (j>i) 两个数可用一个数Nj （第j段段的码字）来表示 Nj=mi+r 特点：编码与符号概率无关。编码效率比较高
分段编码(L7码) °第j段码长公式: 13=|1log(N+1) <logmJ 编码步骤: 1.将信源序列分段 2.计算N3及第段码长1; 3.将Nj编成二进制码,取1位为段的码字
一、分段编码（LZ码） • 第j段码长公式： lj = loga ( Nj +1 ) loga m j • 编码步骤： 1.将信源序列分段 2.计算Nj及第j段码长lj 3.将Nj编成二进制码，取lj位为段的码字
【例1设信源符号集U=a0,a1,a2,a3求 序列S=a0a0a2a3a1a1a0a0a0a3 1=logmj l 的LZ编码。 分7段:a0,a0a2,a3,a1,a1a0,a0a3a2 段序号i Nj 码字 r02 0 00 信源序列码字 110 00110001100011000000100011100011 1 40001 4567 ala0 0413 1002 16 510000 0a0 4 500100 a 3a2 14 501110
[例1] 设信源符号集U={a0,a1,a2,a3}，求信源 序列S=a0a0a2a3a1a1a0a0a0a3a2 的LZ编码。 分7段：a0, a0a2, a3, a1, a1a0, a0a0, a3a2 j 段序号 i r Nj lj 码字 1 a0 0 0 0 2 00 2 a0a2 1 2 6 3 110 3 a3 0 3 3 4 0011 4 a1 0 1 1 4 0001 5 a1a0 4 0 16 5 10000 6 a0a0 1 0 4 5 00100 7 a3a2 3 2 14 5 01110 lj = loga m j 信源序列码字： 001 100 011 000 110 000 001 000 111 0
二、段匹配码(LZ78算法) 编码步骤: 1.分段 2.将段号和信源符号分别进行编码, 若组成二元码,段号所需码长=b 每个信源符号所需码长: lbm
二、段匹配码（LZ78算法） • 编码步骤： 1.分段 2.将段号和信源符号分别进行编码， 若组成二元码，段号所需码长 每个信源符号所需码长： l 1 = lbc l 2 = lbm
[例2]设信源符号集U={a0,al,a2,a3},求信源序刻 S=a0a0a2a3 alala0a0a0a3a2的匹配编码。 分7段:a0,a0a2,a3,a1,a1a0,a0a0a3=a2 C=7段号所需码长:=b7=3 m=4信源符号所需码长:=「b41=2 a0 00a1 01a2←>10a3<>11 段号码字00001010011100101110 段号/1234567 符 a0 aOa2 a3 al ala0 a0a0 3a2 码字000010110101000001110 信源序列编码序列: 0000000100100101101101100010010100001101110
[例2] 设信源符号集U={a0,a1,a2,a3}，求信源序列 S=a0a0a2a3a1a1a0a0a0a3a2 的匹配编码。 分7段：a0, a0a2, a3, a1, a1a0, a0a0, a3a2 段号码字 000 001 010 011 100 101 110 段号 1 2 3 4 5 6 7 符号 a0 a0a2 a3 a1 a1a0 a0a0 a3a2 码字 a0 00 a1 01 a2 10 a3 11 C=7 段号所需码长： l 1 = lb7 = 3 m=4 信源符号所需码长： l 1 = lb4 = 2 00 00 10 11 01 01 00 00 00 11 10 信源序列编码序列： 000 000 010 010 010 110 110 110 001 001 010 000 110 111 0
二、段匹配码 平均码长: (lbc]+[lbm 当n很长时:L≈H(U) LZ78码是一种简单的通用编码,编码方法不需要 知道信源的统计概率分布,而且编码方法简单 编译码速度快,又能达到最佳压缩编码效率
二、段匹配码 • 平均码长： • 当n很长时： n c lbc lbm L ( + ) = L H(U) LZ78码是一种简单的通用编码，编码方法不需要 知道信源的统计概率分布，而且编码方法简单， 编译码速度快，又能达到最佳压缩编码效率
三、LZW算法 LZW编码算法步骤: 1.串表初始化:将所有单个字符存入串表中,并给每个符 号赋一个码字值; 2.将第一个输入字符作为“前缀串”P; 3每个新输入的字符作为扩展字符S。 若PS字符串不在串表中,输出P对应的码字,将PS存入 串表并分配一个码字值;S→P; 若PS已在串表中,PS→P 4.重复步骤3,知道完成编码
三、LZW算法 • LZW编码算法步骤： 1.串表初始化：将所有单个字符存入串表中，并给每个符 号赋一个码字值； 2.将第一个输入字符作为“前缀串”P； 3.每个新输入的字符作为扩展字符S。 若PS字符串不在串表中，输出P对应的码字，将PS存入 串表并分配一个码字值；S→P； 若PS已在串表中，PS→P； 4.重复步骤3，知道完成编码
[例3]由三元字符x、Y、Z组成的信源序列为 S= XYXYZYXYXYXXXXXXX求ZW编砖 编码表(串表) 字符申x|2 xy Yx xYz zY YXY YxYx xxxxxxx 码字123 56789101112 输入信源序列 X Y Z YX YXYXXXXXX 输出LW码字12435811011 LZW算法是LZ78算法的使用修正形式,保留了LZ码的自适应性 能,压缩效率大致相同,成为计算机文件压缩的标准算法 且算法硬件实现容易
[例3] 由三元字符X、Y、Z组成的信源序列为： S=XYXYZYXYXYXXXXXXX 求LZW编码。 X 1 Y 2 Z 3 XY 4 YX 5 XYZ 6 ZY 7 YXY 8 YXYX 9 XX 10 字符串 码 字 XXX 11 XXXX 12 输入信源序列 X Y XY Z YX YXY X XX XXX 输出LZW码字 1 2 4 3 5 8 1 10 11 编码表（串表） LZW算法是LZ78算法的使用修正形式，保留了LZ码的自适应性 能，压缩效率大致相同，成为计算机文件压缩的标准算法。 且算法硬件实现容易
本章重点内容 信息量、信息熵、互信息的概念及定义式 克拉夫特不等式 无失真变长信源编码定理(香农第一定理) 主要的编码方法: Huffman码、费诺码、香农 费诺码、算术码、M码、LZ码。 各种编码方法的平均码长和编码效率的计算
本章重点内容 • 信息量、信息熵、互信息的概念及定义式。 • 克拉夫特不等式 • 无失真变长信源编码定理（香农第一定理） • 主要的编码方法：Huffman码、费诺码、香农- 费诺码、算术码、MH码、LZ码。 • 各种编码方法的平均码长和编码效率的计算