0101
00010
00011
H (X ) 2 .5 5 (b it/sig n ) K 2.61
H(X) 97.7% K
若采用定长编码，码长K3,则编码效率
＝2.55＝85％
3 可见，哈夫曼编码的效率提高了12.7％。
例 设有离散无记忆信源
P(X X)0 a.1 4
a2 0.2
a3 0.2
a4 0.1
4 把pa(aj )用二进制表示，用小数
点 后 的 k位 作 为 ai的 码 字
例
设有一单符号离散无记忆信源
P(X X) 0.a2 1 50a .2 2 50 a.3 20a .1 4 50 a.5 10a .0 6 5
试对该信源编二进制香农码。
编码过程
（1）
j1
pa(aj ) p(ai )
a 6 0.04
00 01 10
0
0 1
1
110 1110 1111
H (X ) 2 .3 5 (b it/sig n )
6
K p(ai)ki 2.4 i1
H(X)H(X)97.92%
RK
费诺码比较适合于每次分组概率都很接近 的信源。
5.1.3 赫夫曼编码
1 将信源符号按概率由大到小顺序排队； 2 给两个概率最小的符号各分配一个码位，
将其概率相加后合并作为一个新的符号， 与剩下的符号一起，称为缩减信源；
3 将缩减信源符号仍按概率由大到小顺序 排队；
4 重复步骤2、3直至概率和为1。
例 设有一单符号离散无记忆信源
P (X X ) 0 a .1 40 a .1 2 8 0 a .3 10 a .4 10 a .0 5 7 0 a .0 60 a .6 0 7 5 0 a .0 8 4
1 按信源符号的概率从大到小的顺序排队.)
2 令p(a0) 0，用pa(aj ),j i 1 j1 表 示 第 i个 码 字 的 累 加 pa(a概 j ) 率p(ai ) 1 i1
3 lo 2 p ( a g i) k i 1 lo 2 p ( a g i)
试对该信源编二进制哈夫曼码。
a 1 0 .4
a 2 0 . 18
a 3 0 .1 a 4 0 .1
a 5 0 . 07 a 6 0 . 06
ax 77 0 . 05
a 8 0 . 04
编码过程
0.6
0.37 0
0.23
1
0.19
0
1
0.13
0
1
0
0.09
1
0
1
0
1
0
11
001
011 0000
0100
组合编码可获得较高的编码效率：
游程编码
赫夫曼编码
5.1.6 冗余位编码
冗余位 信源序列中不携带信息的符号。 多元信源序列： x 1 ,x 2 , ,x m 1 ,y , ,y ,x m 1 1 , ,x m 2 ,y ,
6
K p(ai)ki 2.7 i1
H (X)H (X)89.63%
RK
5.1.2 费诺编码
1 按信源符号的概率从大到小的顺序排队
不妨设 p (a 1 ) p (a 2 ) ...... p ( a n )
2 对概率按m进行分组，使每组概率尽 可能相等
3 给每个分组分配一个码元 4 对每个分组重复2、3步，直到不可分
5.1.5 游程编码
游程：指数字序列中连续出现相同符号的一 段。在二元信源中，连续的一段‘0’称为一 个‘0’游程，‘0’的个数称为此游程的长度， 同样，也有‘1’游程。
游程序列：用交替出现的‘0’游程、‘1’ 游程的长度，来表示任意二元序列而产生的一 个新序列。它和二元序列是一个一一对应的变 换。
i0
pa (a j ) ki 码字
a 1 0 .25
0
2 00
a 2 0 .25 0 .25 2 01
a 3 0 .2 0 .5 3 100
a 4 0 .15 0 .7 3 101
a 5 0 .1 0 .85 4 1101
a 6 0 .05 0 .95 5 11110
H(X)2.42
K R Llog2mK
第1 第2章：信源熵 第3章：信道容量
第5章：信源编码
第7章：密码体制的安全性测度
信源编码
➢ 信源编码是以提高通信的有效性为目的 编码。
➢ 通常通过压缩信源的冗余度来实现。
➢ 采用的一般方法是压缩每个信源符号的 平均比特数或信源的码率。同样多的信 息用较少的码率来传送，使单位时间内 传送的平均信息量增加，从而提高通信 的有效性。
为止
例
设有一单符号离散无记忆信源
P (X X ) 0a .3 1 20a .2 2 20a .1 3 80a .1 4 60a .0 5 80a .0 6 4
试对该信源编二进制费诺码。
编码过程
a 1 0.32
0
a 2 0.22 0 1
a 3 0.18
0
a 4 0.16
a 5 0.08 1 1
a5 0.1
用两种不同的方法对其编二进制huffman码
方法一 方法二
两种不同的编码方法得到的码字和码长的对比
信源符号 ai a1 a2 a3 a4 a5
概率p(ai) 码字Wi1 码长Ki1 码字Wi2 码长K’i2
0.4 1
1 00
2
0.2 01
2 10
2
0.2 000
3 11
2
0.1 0010
信源编码的基本途径有两个：
➢使序列中的各个符号尽可能地互相 独立，即解除相关性；
➢使编码中各个符号出现的概率尽可 能地相等，即概率均匀化。
5.1.2 香农编码
设有离散无记忆信源
å 轾 犏 a1
犏 臌 p(a1)
a2 ..... p(a2) .....
p(aann),i= n1p(ai)=1
香农编码方法的步骤
0001……
31132131……
➢若已知二元序列以0起始，从游程序列很容易
恢复成原来的二元序列
➢游程序列是多元序列，各长度可按赫夫曼编
码或其它方法处理以达到压缩码率的目的。
➢游程编码只适用于二元序列，对于多元信源，
一般不能直接利用游程编码
因为游程变换是一一对应的可逆 变换，所以游程变换后，熵不变。
4 010
3
0.1 0011
4 011
3
平均码长和编码效率
7
K p(ai)ki 2.2 i1
H(X) 96.5%
K
两种编码方法编出的码字的码长方差比较
7
l2E[(kiK)2] p(ai)(kiK)2 i1
2 l1
1.36
2 l2
0.16
结论：
进行赫夫曼编码时，为得到码方差最小的 码，应使合并的信源符号位于缩减信源序 列尽可能高的位置上，以减少再次合并的 次数，充分利用短码。