信息论与编码第五章.ppt

课间休息
第五章信源编码
变长编码的概念
香农编码
费诺编码
哈夫曼编码
游程编码(有记忆信源)
§ 香农编码
编码步骤
有关编码的几个问题:
码字长短ki与p(xi)有关
-㏒p(xi) ≦ki≦1-㏒p(xi)
码字序列与累加概率pa(xj)有关
将累加概率变换成二进制小数,取小数点后ki位
数作为第i个符号的码字。
取大于-logp(xi)整数
§ 香农编码
例:对下述信源进行香农编码
信源符号
符号概率
累加概率
-㏒p(si)
码长
码字
S1
S2
S3
S4
S5
S6
S7


+







3
000












4
3
3
3
3
7
001
011
100
101
1110
1111110
+
§ 香农编码
平均码长
信源熵
结论:
香农码是即时码,但冗余度稍大,不是最佳码。
编码效率
§ 费诺编码
编码步骤
应注意
所分各组(组数与进制相同)尽可能相等,以便使平均码长减小。
赋值规律应一致。
例:试将上例信源进行二进制费诺编码
§ 费诺编码
信源
符号
符号
概率
第一次分组
第一次分组
第一次分组
第一次分组
码字
码长
s1

0
0
00
2
s2

1
0
010
3
s3

1
011
3
s4

1
0
10
2
s5

1
0
110
3
s6

1
0
1110
4
s7

1
1111
4
§ 费诺编码
平均码长
信源熵
编码效率
§ 费诺编码
树图
0
0
0
0
0
0
S7(1111)
1
1
1
1
1
1
S2(010)
S3(011)
S4(10)
S5(110)
S6(1110)
S1(00)
§ 哈夫曼编码
一、哈夫曼编码的步骤
二、哈夫曼编码的原则
码字排列一定要从树根开始,此时编出的码
字才是异前置码。
每次分配码元的规律应一致,这样才能得到
可分离的码字。
合并后的新的虚拟符号的概率若与其它符号
的概率相等,则该虚拟符号必须排在这些符
号的前面,以便使码方差最小。