第四章 无失真信源编码
第一节 引言
第二节 码的分类
第三节 等长信源编码定理
第四节 变长信源编码定理
第八节 游程编码、算术编码、冗长编码
第六节 费诺编码
第七节 霍夫曼编码
第五节 香农编码
? 信源编码,以 提高通信有效性 为目的的编码。通常通过压缩信
源的冗余度来实现。采用的一般方法是压缩每个信源符号的平
均比特数或信源的码率。即同样多的信息用较少的码率传送，
使单位时间内传送的平均信息量增加，从而提高通信的有效性。
? 信道编码,是以 提高信息传输的可靠性 为目的的编码。通常通
过增加信源的冗余度来实现。采用的一般方法是增大码率 /带宽。
与信源编码正好相反。
? 密码,是以 提高通信系统的安全性 为目的的编码。通常通过加
密和解密来实现。从信息论的观点出发，“加密”可视为增熵
的过程，“解密”可视为减熵的过程。
第一节 引言
? 信源编码理论是信息论的一个重要分支，其理论基础是信源编
码的两个定理。
? 无失真信源编码定理,是离散信源 /数字信号编码的基础；
? 限失真信源编码定理,是连续信源 /模拟信号编码的基础。
? 信源编码的分类：离散信源编码、连续信源编码和相关信源编
码三类。
? 离散信源编码,独立信源编码，可做到无失真编码；
? 连续信源编码,独立信源编码，只能做到限失真信源编码；
? 相关信源编码,非独立信源编码。
第一节 引言
第二节 码的分类
编码器可以看作这样一个系统，它的输入端为原始信
源 S，其符号集为 ；而信道所能传输的符号集
为 编码器的功能是用符号集 X中的元素，将
原始信源的符号 变换为相应的码字符号,所以编码器
输出端的符号集为
称为 码字, 为码字 的码元个数，称为码字 的码字
长度，简称 码长 。
12{,,...,}qS S S S?
12{,,..,,}rX x x x?
12{,,...,}qS S S S?
12{,,..,,}rX x x x?
编码器
12,{,,...,}qC W W W
12,{,,...,}qC W W W
iS i
w
iw iL iw iw
1,二元码：
码符号集 X={0,1}，如果要将信源通过二元信道传输，必
须将信源编成二元码，这也是最常用的一种码。
2,等长码：
若一组码中所有码字的长度都相同，称为等长码。
3,变长码：
若一组码中所有码字的长度各不相同，称为变长码。
4,非奇异码：
若一组码中所有码字都不相同，称为非奇异码。
第二节 码的分类
5,奇异码：
若一组码中有相同的码字，称为奇异码。
6,码的 N次扩展：
若码, 码 则称码 B为
码 C的 N次扩展码。
7,唯一可译码：
若码的任意一串有限长的码符号序列只能被唯一的译成
所对应的信源符号序列，则称此码为 唯一可译码 。
12,{,,...,}qC W W W 12,{ (,.,) }i i i iNB B W W W?
第二节 码的分类
例：如果有四个信源符号 {s1,s2,s3,s4}，采用二元编
码,l=2，则可以编成 s1=00,s2=01,s3=10,s4=11。
第三节 等长信源编码定理
如果我们要对信源的 N次扩展信源进行编码，也必须满足
,两边取对数得：Nlqr? lo g
lo g
lq
Nr?
表示平均每个信源符号所需的码符号个数。lN
若对信源进行等长编码，则必须满足
其中,l是码长,r是码符号集中的码元数,q信源符号个数。
lqr?
第二节 等长码
例：对英文电报得 32个符号进行二元编码，根据上述关系：
l o g 3 2 5
l o g 2l ??
我们继续讨论上面得例子，我们已经知道英文的极限
熵是 1.4bit,远小于 5bit，也就是说,5个二元码符号只携带
1.4bit的信息量，实际上,5个二元符号最多可以携带 5bit
信息量。我们可以做到让平均码长缩短，提高信息传输率
第二节 等长码
我们举例说明：
设信源
31 2 4
1 2 3 4( ) ( ) ( ) ( ) ( )
ss s sS
P s P s P s P s P s
???? ? ????
?? ??
4
1
( ) 1i
i
Ps
?
??
而其依赖关系为：
2 1 1 2 4 3 3 4( / ) ( / ) ( / ) ( / ) 1,( / ) 0jiP s s P s s P s s P s s P s s? ? ? ? ?其余
第二节 等长码
若不考虑符号间的依赖关系，可得码长 l＝ 2
若考虑符号间的依赖关系，则对此信源作二次扩展
2
3 4 4 31 2 2 1
2 1 2 2 1 3 4 4 3( ) ( ) ( ) ( )()
s s s ss s s sS
P s s P s s P s s P s sPs
?? ????? ??
????
( ) 1ij
ij
P s s ??
可见，由于符号间依赖关系的存在，扩展后许多符号出
现的概率为 0，此信源只有 4个字符，可得码长,
但平均每个信源符号所需码符号为
' 2l ?
' 1l
N ?
第二节 等长码
我们仍以英文电报为例，在考虑了英文字母间的相关性
之后，我们对信源作 N次扩展，在扩展后形成的信源（也
就是句子）中，有些句子是有意义的，而有些句子是没有
意义的，我们可以只对有意义的句子编码，而对那些没有
意义的句子不进行编码，这样就可以缩短每个信源符号所
需的码长。
等长信源编码定理给出了进行等长信源编码所需码长的
极限值。
定理 4.3（等长信源编码定理） 一个熵为 H(S)的离散无记
忆信源，若对其 N次扩展信源进行等长 r元编码，码长为 l，
对于任意 大于 0，只要满足?
()
lo g
l H S
Nr
???
当 N无穷大时，则可以实现几乎无失真编码，反之，若：
( ) 2
lo g
l H S
Nr
???
则不可能实现无失真编码，当 N趋向于无穷大是，译码错
误率接近于 1。
第三节 等长信源编码定理
?定理 4.3的条件式可写成,lo g ( )l r N H S?
左边表示长为 的码符号所能载荷的最大信息量，
而右边代表长为 N的序列平均携带的信息量。因此，
只要码字传输的信息量大于信源序列携带的信息量，
总可以实现无失真编码 。
l
第三节 等长信源编码定理
?定理 4.3的条件式也可写成,l o g ( )l r H SN ???
令：
' lo glRr
N?
称之为 编码信息率 。可见，编码信息
率大于信源的熵，才能实现无失真编码。
最佳编码效率为：
'
( ) ( )
()
H S H S
R H S? ??? ?
1 ()HS??
?
??
第三节 等长信源编码定理
为了衡量编码效果，引进
'
( ) ( )
l o g
H S H S
lR r
N
? ?? 称为 编码效率 。
例：设离散无记忆信源：
12
31()
44
ssS
Ps
????
?????
????
??
1 3 4( ) l o g 4 l o g 0, 8 1 14 4 3HS ? ? ?
2 2 2 2 2 2
1
1 3 4[ ( ) ] ( l og ) [ ( ) ] ( l og 4) ( l og ) 0.8 11 0.4 715
4 4 3i i iiD I s p p H S?? ? ? ? ? ??
若采用等长二元编码，要求编码效率,允许错误率0.96? ?
510? ??,则,74,1 3 1 0N ??
也就是长度要达到 4130万以上。
第三节 等长信源编码定理
1、唯一可译变长码与及时码
信源符号 出现概率 码 1 码 2 码 3 码 4
s1
s2
s3
s4
1/2
1/4
1/8
1/8
0
11
00
11
0
10
00
01
1
10
100
1000
1
01
001
0001
第四节 变长信源编码定理
第五节 变长码
码 1是一个奇异码，不是唯一可译码；码 2也不是唯一
可译码，因为收到一串序列是，无法唯一译出对应的原符
号序列，如 0100，即可译作 s4s3s1,也可译作
s4s1s3,s1s2s3或 s1s2s1s1；码 3和码 4都是唯一可译的。
但码 3和码 4也不太一样，码 4称作逗点码，只要收到 1，
就可以立即作出译码；而码 3不同，当受到一个或几个码
是，必须参考后面的码才能作出判断。
定义,在唯一可译码中，有一类码，它在译码是无须参
考后面的码字就可以作出判断，这种码称为 即时码 。
定义,如果一个码组中的任一个码字都不是另一个码字的续
长，或者说，任何一个码字后加上若干码元后都不是码组中
另一个码字，则称为 即时码 。
所有的码
非奇异码
唯一可译码
即时码
第四节 变长信源编码定理
2、即时码的树图构造法
我们可以用树图的形式构造即时码，如
0 1
0
0
1
1
1
1
01
001
0001
码 4的树图
1 0
1
1
0
0
0
0
10
100
1000
码 3的树图
第四节 变长信源编码定理
树根 ——码字的起点
树枝数 ——码的数
节点数 ——码字的一部分
节数 ——码长
端点 ——码字
满树 ——等长码
非满树 ——变长码
在每个节点上都有 r个分枝的树称为 整树,否则称为 非
整树 。
即时码的树图还可以用来译码
第四节 变长信源编码定理
3、克拉夫特（ Kraft）不等式
定理 4.4 对于码符号为 的任意即时码，
所对应的码长为,则必定满足：
12{,,...,}qX x x x?
12,,...,ql l l
1
1i
q
l
i
r ?
?
??
反之，若码长满足上式，则一定存在这样的即时码 。
可以根据即时码的树图构造法来证明。
后来,B.McMillan证明了对于唯一可译码也必须满足
上面的不等式，
第四节 变长信源编码定理
定理 4.6 若存在一个码长为 唯一可译码，则一
定存在一个同样长度的即时码。
这说明，其他唯一可译码在码长方面并不比即时码
占优。所以在讨论唯一可译码时，只需要讨论即时码就
可以了。
12,,,ql l l
第四节 变长信源编码定理
设信源
12
12
...
...
q
n
a a xX
p p pP
???? ?
?????? ??
编码后的码字为：
12,,...,qW W W 码长为,12,,...,ql l l
则这个码的平均长度为：
1
()
q
ii
i
L P S l
?
? ?
平均每个码元携带的信息量即编码后的信息传输率为,()HSR
L?
若有一个唯一可译码，它的平均码长小于其他唯一可译码的
长度，则称此码为 紧致码 或 最佳码,无失真信源编码的基本
问题就是寻找紧致码。
第四节 变长信源编码定理
定理 4.8 无失真变长信源编码定理（香农第一定理）
离散无记忆信源 S的 N次扩展信源,其熵为,并且
编码器的码元符号集为 A,对信源 进行编码，
总可以找到一种编码方法，构成单义可译码，使信源 S中每
个符号 si所需要的平均码长满足
NS ()NHS
12{,,...,}q? ? ?
NS
( ) ( ) 1
l o g l o g
NH S L H S
r N r N? ? ?
li m ( )rN L H S?? ?当 则得：N??
第四节 变长信源编码定理
这个定理是香农信息论中非常重要得一个定理，它指
出，要做到无失真得信源编码，信源每个符号所需要的平
均码元数就是信源的熵值，如果小于这个值，则唯一可译
码不存在，可见,熵是无失真信源编码的极限值 。定理还
指出，通过对扩展信源进行编码，当 N趋向于无穷时，平
均码长可以趋进该极限值。
还可以证明，如果我们不确切知道信源的概率分布，
我们用估计的概率分布去进行编码时，平均码长会加长，
但是如果估计的偏差不大的话，平均码长也不会增加太多
（定理 4.9的内容）。
第四节 变长信源编码定理
( ) ( ) 1
l o g l o g
NH S L H S
r N r N? ? ?由
得,( ) l o g ( )NLH S r H S
N?? ? ?
logNL rN
就是编码后每个信源符号所携带的平均信息量
' lo gNLRr
N?
第一定理可以表述如下：若 就存在唯一可译
变长码，若 则不存在唯一可译变长码。
' ()R H S?
' ()R H S?
第四节 变长信源编码定理
定义：
若从信道角度讲，信道的信息传输率 ()HSR
L?因为：
()
logN
L HSL
Nr?? 所以 logRr?
当平均码长达到极限值时，编码后信道的信息传输率为,logRr?
无噪信道编码定理 若信道的信息传输率 R不大于信道容
量 C，总能对信源的输出进行适当的编码，使的在无噪无
损信道上能无差错的以最大信息传输率 C传输信息，若 R
小于 C，则无差错传输是不可能的。
第四节 变长信源编码定理
编码效率,()rHs
L? ?
码的剩余度,1 ??
在二元无噪无损信道中,()Hs
L? ?
在二元无噪无损信道中信息传输率,()HsR
L ???
例：
12
() 3 / 4 1 / 4
ssS
PS
???? ?
?????? ??
其熵为,H(S)=0.811我们令 s1=0,s2=1，这时平均码长,编码的
效率为 。
1L?
0.811? ?
第四节 变长信源编码定理
二次扩展信源进行编码,即时码
s1s1 9/16 0
s1s2 3/16 10
s2s1 3/16 110
s2s2 1/16 111
i? ()iP?
2 9 / 16 *1 3 / 16 * 2 3 / 16 * 3 1 / 16 * 3 27 / 16L ? ? ?＋＋
2 2 7 / 3 22LL ?? 0.961? ?
第五节 香农编码
? 设离散无记忆信源
? 二进制香农码的编码步骤如下：
? 将信源符号按概率从大到小的顺序排列，为方便起见，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 令 p(x0)=0，用 pa(xj),j=i+1表示第 i个码字的累加概率，则：
? 确定满足下列不等式的整数 ki,并令 ki为第 i个码字的长度
? － log2 p(xn)≤ki<－ log2 p(xn)+1
? 将 pa(xj) 用二进制表示，并取小数点后 ki 位作为符号 xi的编码。
1
0
( ) ( ),1,2,,ja j i
i
p x p x j n?
?
???
12
112
,,,,,,( ) 1
( ),( ),,( ),,( )()
nin
i
iin
x x x xX px
p x p x p x p xPX ?
???? ????
???? ?? ?
第五节 香农编码
例 有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如下表所示。
二 进制香农编码
x i p ( x i ) p a ( x j ) k i 码字
x 1 0, 2 5 0, 0 0 0 2 0 0 (0, 0 0 0 ) 2
x 2 0, 2 5 0, 2 5 0 2 0 1 (0, 0 1 0 ) 2
x 3 0, 2 0 0, 5 0 0 3 1 0 0 (0, 1 0 0 ) 2
x 4 0, 1 5 0, 7 0 0 3 1 0 1 (0, 1 0 1 ) 2
x 5 0, 1 0 0, 8 5 0 4 1 1 0 1 (0, 1 1 0 1 ) 2
x 6 0, 0 5 0, 9 5 0 5 1 1 1 1 1 0 (0, 1 1 1 1 0 ) 2
1 2 3 4 5 6,,,,,
( ) 0, 2 5 0, 2 5 0, 2 0 0, 1 5 0, 1 0 0, 0 5
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
第五节 香农编码
? 计算出给定信源香农码的平均码长
? 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3
个比特表示。相比较，香农编码对信源进行了压缩。
? 由离散无记忆信源熵定义，可计算出：
? 对上述信源采用香农编码的信息率为
? 编码效率为信源熵和信息率之比。则
? 可以看出，编码效率并不是很高。
0.25 2 2 ( 0.2 0.15 ) 3 0.10 4 0.05 5 2.7 ( / )K ? ? ? ? ? ? ? ? ? ? ? 比特 符号
22
2, 7l o g l o g 2 2, 7 1,2
1
KR m L m
L? ? ? ? ?这里
( ) 2, 4 2 8 9, 6 3 %
2, 7
HX
R? ? ? ?
6
21( ) ( ) l o g ( ) 2,4 2 ( / )iiiH X p x p x?? ? ?? 比特 符号
第六节 费诺编码
费诺编码也是一种常见的信源编码方法。
编码步骤如下：
? 将概率按从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 按编码进制数将概率分组，使每组概率尽可能接近或相等。如
编二进制码就分成两组，编 m进制码就分成 m组。
? 给每一组分配一位码元。
? 将每一分组再按同样原则划分，重复步骤 2和 3，直至概率不再
可分为止。
第六节 费诺编码
例 设有一单符号离散信源
? 对该信源编二进制费诺码。编码过程如下表。
二进制费诺编码
信源符号 概率 编码 码字 码长
x 1 0, 3 2 0 00 2
x 2 0, 2 2
0
1 01 2
x 3 0, 1 8 0
10 2
x 4 0, 1 6 0 1 1 0 3
x 5 0, 0 8 0 1 1 1 0 4
x 6 0, 0 4
1
1
1
1 1111 4
1 2 3 4 5 6,,,,,
( ) 0, 3 2 0, 2 2 0, 1 8 0, 1 6 0, 0 8 0, 0 4
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
第六节 费诺编码
? 该信源的熵为
? 平均码长为
? 编码效率为
? 本例中费诺编码有较高的编码效率。费诺码比较适合于
每次分组概率都很接近 的信源。特别是对每次 分组概率
都相等 的信源进行编码时，可达到理想的编码效率。
6
2
1
( ) ( ) l o g ( ) 2,3 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
6
1
( ) 2.4( / )ii
i
K p x k
?
??? 比特 符号
2.422 1
( ) 2,3 5 2,3 5 9 7,9 2 % 1,2
l o g l o g 2 2,4KL
HX Lm
m? ? ? ? ? ? ?这里
第六节 费诺编码
? 题中码字还可用码树来表示，如图所示。
第七节 霍夫曼编码
霍夫曼 (Huffman)编码是一种效率比较高的变长
无失真信源编码方法。
? 编码步骤
? 二进制哈夫曼编码
? m进制哈夫曼编码
第七节 霍夫曼编码 —— 编码步骤
? 将信源符号按概率从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 给两个概率最小的信源符号 p(xn-1)和 p(xn)各分配一个码位,0”和,1”，
将这两个信源符号合并成一个新符号，并用这两个最小的概率之和
作为新符号的概率，结果得到一个只包含 (n－ 1)个信源符号的新信源。
称为 信源的第一次缩减信源,用 S1表示。
? 将缩减信源 S1的符号仍按概率从大到小顺序排列，重复步骤 2，得到
只含 (n－ 2)个符号的缩减信源 S2。
? 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符
号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径向
前返回，就得到各信源符号所对应的码字。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
例 设单符号离散无记忆信源如下，要求对信源编二进制
霍夫曼码。编码过程如下图（后页）。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
? 在图中读取码字的时候，一定要从后向前读，此时编出
来的码字才是可分离的异前置码。若从前向后读取码字，
则码字不可分离。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
第七节 霍夫曼编码 —— 二进制哈夫曼编码
? 将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。
? 信源熵为：
? 平均码长为
? 编码效率为
? 若采用定长编码，码长 K=3，则编码效率
? 可见哈夫曼的编码效率提高了 12.7%。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
8
2
1
( ) ( ) l o g ( ) 2,5 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
8
1
( ) 0,4 1 ( 0,1 8 0,1 ) 3 ( 0,1 0 0,0 7 0,0 6 ) 4 ( 0,0 5 0,0 4 ) 5 2,6 1 ( / )ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
( ) ( ) 2, 5 52, 6 1 9 7, 7 %H X H XR K? ? ? ? ?
2.553 85%? ??
第七节 霍夫曼编码 —— 二进制哈夫曼编码
注意, 哈夫曼的编法并不惟一 。
? 每次对缩减信源两个概率最小的符号分配,0”和,1”码元是任意的，
所以可得到不同的码字。只要 在各次缩减信源中保持码元分配的一致
性, 即能得到可分离码字。
? 不同的码元分配，得到的具体码字不同，但码长 ki不变，平均码长
也不变，所以没有本质区别；
? 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方
法上来说,这几个符号的次序可任意排列，编出的码都是正确的，但
得到的 码字不相同 。 不同的编法得到的 码字长度 ki也不尽相同 。
K
例,单符号离散无记忆信源,用
两种不同的方法对其编二进制哈夫曼码。
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
方法一,合并后的新符号排在其它相同概率符号的后面。
1 2 3 4 5,,,,,
( ) 0, 4 0, 2 0, 2 0, 1 0, 1
X x x x x x
PX
? ? ? ?? ????
? ? ? ?
第七节 霍夫曼编码 —— 二进制哈夫曼编码
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
这两种编码哪一种更好呢，我们来计算一下二者的码长。
方法二,合并后的新符号排在其它相同概率符号的前面。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
两种编码的平均码长是一样的，都是 2.2，那一种更好呢，
我们可以计算一下平均码长的方差。
5
1
1
( ) 0.4 1 0.2 2 0.2 3 0.1 4 0.1 4 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
5
2
1
( ) 0.4 2 0.2 2 0.2 2 0.1 3 0.1 3 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
2 2 2
1
[ ( ) ] ( ) ( )qi i i
i
E l L P s l L?
?
? ? ? ??
522
11
1
( ) ( ) 1.36ii
i
P s l L?
?
? ? ??
522
1
( ) ( ) 0,1 6ii
i
P s l L?
?
? ? ??
定义码字长度的方差 σ2：
第七节 霍夫曼编码 —— 二进制哈夫曼编码
第七节 霍夫曼编码 —— 二进制哈夫曼编码
? 可见：第二种编码方法的码长方差要小许多。意味着第二种
编码方法的码长变化较小，比较接近于平均码长。
? 第一种方法编出的 5个码字有 4种不同的码长；
? 第二种方法编出的码长只有两种不同的码长；
? 显然,第二种编码方法更简单、更容易实现，所以更好 。
结论, 在哈夫曼编码过程中，对缩减信源符号按概率由大到小
的顺序重新排列时，应 使合并后的新符号尽可能排在靠前的
位置,这样可使合并后的新符号重复编码次数减少，使短码
得到充分利用。
第七节 霍夫曼编码 —— m进制哈夫曼编码
“全树”概念
? 定义：码树图中每个中间节点后续的枝数为 m时称为 全树 ；若
有些节点的后续枝数不足 m，就称为 非全树 。
? 二进制码不存在非全树的情况，因为后续枝数是一时，这个枝
就可以去掉使码字长度缩短。
? 对 m进制编码：若所有码字构成全树，可分离的码字数（信源
个数）必为 m+k(m－ 1)。 k为信源缩减次数。
? 若信源所含的符号数 n不能构成 m进制全树，必须增加 s个不用
的码字形成全树。显然 s<m－ 1，若 s=m－ 1，意味着某个中间
节点之后只有一个分枝，为了节约码长，这一分枝可以省略。
第七节 霍夫曼编码 —— m进制哈夫曼编码
? 在编 m进制哈夫曼码时为了使平均码长最短，必须使最
后一步缩减信源有 m个信源符号。非全树时，有 s个码字
不用：
? 第一次对最小概率符号分配码元时就只取 (m－ s)个，
分别配以 0,1,…,m－ s－ 1，把这些符号的概率相加作
为一个新符号的概率，与其它符号一起重新排列。
? 以后每次就可以取 m个符号，分别配以 0,1,…,m－
1； … ；如此下去，直至所有概率相加得 1为止，即得
到各符号的 m进制码字。
第七节 霍夫曼编码 —— m进制哈夫曼编码
例：对如下单符号离散无记忆信源 (例 5.4.1)编三进制哈夫
曼码。
这里,m=3,n=8
? 令 k=3,m+k(m－ 1)=9，则 s=9－ n=9－ 8=1
? 所以第一次取 m－ s=2个符号进行编码。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
第七节 霍夫曼编码 —— m进制哈夫曼编码
第七节 霍夫曼编码 —— m进制哈夫曼编码
? 平均码长为：
? 信息率为：
? 编码效率为：
? 可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。
5
1
1
( ) 0.4 1 ( 0.1 8 0.1 0.0 7 0.0 6) 2 ( 0.0 5 0.0 4) 3 1.6 9( /)ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
22
1, 6 9l o g 3 l o g 3 2, 6 8 ( / )
1
KR
L? ? ? 比特 符号
( ) 2, 5 5 9 5, 2 %
2, 6 8
HX
R? ? ? ?
一些结论
? 香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出
现的信源符号对应较短的码字，使信源的平均码长缩短，从而实
现了对信源的压缩；
? 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不
是很高；
? 费诺码和哈夫曼码的编码方法都不惟一；
? 费诺码比较适合于对分组概率相等或接近的信源编码；
? 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对
编码设备的要求也比较简单，因此综合性能优于香农码和费诺码 。
第八节 游程编码、算术编码
? 香农编码、费诺编码、哈夫曼编码主要是针对无
记忆信源。当信源有记忆时上述编码效率不高；
? 游程编码对 相关信源 编码更有效；
? 香农编码、费诺编码、哈夫曼编码属于 无失真信
源编码 ；
? 游程编码属于 限失真信源编码 。
第八节 游程编码、算术编码、冗余编码
? 游程,数字序列中连续出现相同符号的一段。
? 二元序列的游程：只有,0”和,1”两种符号。
? 连,0”这一段称为,0”游程，它的长度称为 游程长度 L(0)；
? 连,1”这一段称为,1”游程，它的游程长度用 L(1)表示。
游
程
编
码
① 二元独立序列游程长度概率
? 若规定二元序列总是从,0”开始。
? 对于随机序列，游程长度是随机的其取值可为 1,2,3,…,直至无穷。
? 游程长度序列 /游程序列：用交替出现的,0”游程和,1”游程长度表示任意二
元序列。
? 游程变换,是一种一一对应的变换，也是可逆变换。
例如：二元序列,000101110010001…,可变换成如下游程序列,31132131
第八节 游程编码、算术编码、冗余编码
? 游程变换减弱了原序列符号间的相关性。
? 游程变换 将二元序列变换成了多元序列 ；这样就适合于用
其他方法，如哈夫曼编码，进一步压缩信源，提高通信效
率。
? 编码方法：
? 首先测定,0”游程长度和,1”游程长度的概率分布，即
以游程长度为元素，构造一个新的信源 ；
? 对新的信源（游程序列）进行哈夫曼编码。
游
程
编
码
第八节 游程编码、算术编码、冗余编码
② 二元独立序列游程长度的熵
? 若二元序列的概率特性已知，由于二元序列与游程变换序列
的一一对应性，可计算出游程序列的概率特性。
? 令,0”和,1”的概率分别为 p0和 p1，则,0”游程长度 L(0)的概
率为
p[L(0)]=p0L(0)－ 1p1 式中 L(0)=1,2,…,
? 在计算 p[L(0)]时必然已有,0”出现，否则就不是,0”游程，若
下一个符号是,1”，则游程长度为 1，其概率是 p1 =1－ p0；若
下一个符号为,0”、再下一个符号为,1”，则游程长度为 2，
其概率将为 p0p1 ；依此类推。
游
程
编
码
第八节 游程编码、算术编码、冗余编码
游
程
编
码
? 游程长度至少是 1，理论上，游程长度可以是无穷，但
很长的游程实际出现的概率非常小。
? 同理可得,1”游程长度 L(1)的概率为：
P[L(1)]=p1L(1)-1p0
?,0”游程长度的熵：
02
( 0 ) 1 1
()[ ( 0)] [ ( 0)] l og [ ( 0)]
L
HpH L p L p L
p
?
?
? ? ??
第八节 游程编码、算术编码、冗余编码
③ 二元独立序列的平均游程长度
?, 0”游程序列的平均游程长度
? 同理可得,1”游程长度的熵和平均游程长度
( 0 ) 1
0 0 1
( 0 ) 1 ( 0 ) 1
( 0 )
10
( 0 ) 1 01
1 2 3 4
[ ( 0 ) ] ( 0 ) [ ( 0 ) ] ( 0 )
1
( 1 ) 1
L
LL
L
L
l E L L p L L p p
d
pp
d p p
x x x x x
??
?
??
?
?
?
? ? ?
??
? ? ? ? ? ? ?
??
?
0
1
00
() 1[ ( 1 ) ] [ ( 1 ) ]HpH L l E L
pp? ? ?
游
程
编
码
第八节 游程编码、算术编码、冗余编码
游
程
编
码
④ 二元独立序列的熵
?, 0”游程序列的熵与,1”游程长度的熵之和除以它们的平均游程
长度之和，即为对应原二元序列的熵 H(X)
? 游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，
所以变换后熵值不变。
01
01
[ ( 0 ) ] [ ( 1 ) ]( ) ( ) ( )H L H LH X H p H p
ll
?? ? ?
?
第八节 游程编码、算术编码、冗余编码
? 游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编
码可获得较高的编码效率。
? 假设,0”游程长度的哈夫曼编码效率为 η0，,1”游程长度的哈
夫曼编码效率为 η1，由编码效率的定义和式 (5.4.9)可得对应二
元序列的编码效率（信源熵和信息率之比为编码效率 η=H(X)/R）
? 当,0”游程和,1”游程的编码效率都很高时，采用游程编码的
效率也很高，至少不会低于较小的那个效率。要想编码效率尽
可能高，应尽可能提高熵值较大的游程编码效率。
01
[ ( 0 ) ] [ ( 1 ) ]
0 1 0 1
[ ( 0) ] [ ( 1 ) ]
H L H L
H L H L
??
?
? ? ? ? ?
?
?
?
? ? ?假设,则有
游
程
编
码
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 算术编码不同于哈夫曼码，它 是非分组（非块）码 。它
从全序列出发，考虑符号之间的关系来进行编码。
? 算术编码利用了 累积概率 的概念。
? 算术码主要的编码方法是 计算输入信源符号序列所对应
的区间 。
? 因为在编码过程中，每输入一个符号要进行乘法和加法
运算，所以称此编码方法为算术编码。
? 二元序列的算术编码可用于黑白图像的编码，例如传真。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 设信源符号集 A={a1,a2,…,an}，其相应概率分布为 P (ai)，
P (ai) >0(i=1,2,…,n)
? 信源符号的累积分布函数为：
所得累积分布函数为每台级的下界值，则其区间为 [0,1)左闭
右开区间。
F (a1)=0
F (a2)=P (a1)
F (a3)=P (a1)+P (a2)
…
? 当 A={0,1}二元信源 时,F (0)= 0,F (1)=P (0)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 计算 二元无记忆信源序列 的累积分布函数
? 初始时：在 [0,1)区间内由 F (1)划分成二个子区间
[0,F (1))和 [F (1),1),F (1)= P (0)。
? 子区间 [0,F (1))的宽度为 A(0)= P (0)，对应于信源符号, 0”；
? 子区间 [F (1),1)的宽度为 A(1)= P (1)，对应于信源符号, 1”；
? 若输入符号序列的第一个符号为 s=“0”，落入 [0,F (1))区间，
得累积分布函数 F (s=“0”)= F (0)=0；
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 输入第二个符号为, 1”,s=“01”
? s=“01”所对应的区间是在区间 [0,F (1))中进行分割；
? 符号序列, 00”对应的区间宽度为,
A(00)=A(0)P (0)=P (0)P (0)=P (00)；
? 对应的区间为 [0,F (s=“01”))。
? 符号序列, 01”对应的区间宽度为
A(01)=A(0)P (1)=P (0)P (1)=P (01)= A(0)－ A(00)；
? 对应的区间为 [F (s=“01”),F (1))。
? 累积分布函数 F (s=“01”)=P (00)= P (0)P (0)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
第八节 游程编码、算术编码、冗余编码
算
术
编
码
输入第三个符号为, 1”：
? 输入序列可记做 s1=“011”（若第三个符号输入为, 0”，可记做
s0=“010”）；
? 现在，输入序列 s1=“011”对应的区间是对区间 [F(s),F(1))进行分割；
? 序列 s0=“010”对应的区间宽度为
A(s=“010”)=A(s=“01”)?P(0)=A(s)?P(0)
其对应的区间为 [F(s),F(s)+ A(s)?P(0))；
? 序列 s1=“011”对应的区间宽度为
A(s=“011”)=A(s)?P(1)=A(s=“01”)－ A(s=“010”)= A(s )－ A(s0)
其对应的区间为 [F(s)+A(s)?P(0),F(1))；
? 符号序列 s1=“011”的累积分布函数为 F(s1)=F(s)+A(s)?P(0)；
? 若第三个符号输入为, 0”，符号序列 s0=“010”的区间下界值仍为 F(s)，
得符号序列 s0=“010”的累积分布函数为 F(s0)=F(s)。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 归纳
? 当已知前面输入符号序列为 s，若接着再输入一个符号, 0”，
序列 s0的累积分布函数为,F(s0)=F(s)
? 对应区间宽度为,A(s0)=A(s)?P(0)
? 若接着输入的一个符号是, 1”，序列的累积分布函数为：
F(s1)=F(s)+A(s)?P(0)
? 对应区间宽度为,A(s1)=A(s)?P(1)=A(s)－ A(s0)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 符号序列对应的区间宽度
A(s=“0”)=P(0)
A(s=“1”)=1－ A(s=“0”)=P(1)
A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)
A(s=“01”)=A(s=“0”)－ A(s=“00”)=P(01)=A(0)P(1)=P(0)P(1)
A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)
A(s=“11”)=A(s=“1”)－ A(s=“10”)=P(11)= A(s=“1”)?P(1)=P(1)P(1)
A(s=“010”)=A(s=“01”)?P(0)=P(01)P(0)＝ P(010)
A(s=“011”)=A(s=“01”)-A(s=“010”)=A(s=“01”)?P(1)=P(01)P(1)=P(011)
信源符号序列 s所对应区间的宽度等于符号序列 s的概率 P(s)。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 二元信源符号序列的累积分布函数的递推公式
? F(sr)=F(s)+P(s)?F(r) (r=0,1)
? sr表示已知前面信源符号序列为 s，接着再输入符号为 r
F(0)=0,F(1)=P(0)
F(s0)=F(s)
F(s1)=F(s)+P(s)?F(1)= F(s)+P(s)?P(0)
? A(sr)=P(sr)=P(s)?P(r) (r=0,1)
A(s0)=P(s0)=P(s)?P(0)
A(s1)=P(s1)=P(s)?P(1)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 举例：已输入二元符号序列为 s=“011”，接着再输入符号为, 1”，得
序列累积分布函数为：
F(s1)=F(0111)=F(s=“011”)+P(011)?P(0)
=F(s=“01”)+P(01)?P(0)+P(011)?P(0)
=F(s=“0”)+P(0)?P(0) +P(01)?P(0)+P(011)?P(0)
=0+P(00)+P(010)+P(0110)
对应的区间宽度为
A(s1)=P(s=“011”)?P(1)=P(011)P(1)=P(0111)
? 上述整个分析过程可用图 5.6.1描述
? 式 (5.6.1)和 (5.6.2)是可递推运算，在实际中，只需两个存储器，把 P(s)
和 F(s)存下来，然后，根据输入符号和式 (5.6.1),(5.6.2)更新两个存
储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和
加法运算，所以称为 算术编码 。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
( s 0 ) ( s )
( s 1 ) ( s ) ( s ) ( 0 )
( s 0 ) ( s 0 ) ( s ) ( 0 )
( s 1 ) ( s 1 ) ( s ) (1 )
FF
F F P P
A P P P
A P P P
?
??
??
??
第八节 游程编码、算术编码、冗余编码
算
术
编
码
通过关于信源符号序列的累积分布函数的计算，把区间分割成许
多小区间，不同的信源符号序列对应不同的区间为
[F(s),F(s)+P(s)) 。可取小区间内的一点来代表这序列。
? 编码方法, 将符号序列的累积分布函数写成二进位的小数，取
小数点后 k位，若后面有尾数，就进位到第 k位，这样得到的一个
数 C，并使 k满足
? 举例
? ?2
1 2 1 2
1l og
( s )
0,{ 0,1 },sk k k
k
P
C z z z z z z z
??
? ??????
??
代表大于或等于的最小整数
设 得符号序列 的码字为 。
1( s ) 0.10 110 001 ( s ) 3
7
0.11 0 s 110
F P k
C
? ? ?
?
则
得, 的码字为 。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 编码效率
? 这样选取的数值 C，一般根据二进小数截去尾数的影响得
C－ F(s)<1/2k，当在 l以后没有尾数时 C=F(s)。
F(s)+ 1/2k>C
? 而 P(s)≥1/2k
? 信源符号序列对应区间的上界为 F(s)+P(s)≥F(s)+1/2k>C
? 可见，数值在区间 [F(s),F(s)+P(s))内。而信源符号序列对应
的不同区间（左封右开）是不重叠的，所以编得的码是即时
码。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
2
22
s s s
1
l og
( s )
( s ) l og ( s ) ( s ) ( s ) ( s ) l og ( s ) 1
( ) ( ) 1
( ) ( )
LL
L
k
P
P P K P k P p
H S K H S
H S L H S
L L L L
??
? ??
??
? ? ? ? ? ?
? ? ? ?
? ? ?
由于 得
平均每个符号的码长为
,若信源是无记忆，
2
1( ) ( ) l o gKKH S R H S R m
L L L
??? ? ? ? ???
??
? 算术编码的编码效率很高。当信源符号序列很长时，
L很大时，平均码长接近信源的熵。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
译码就是一系列比较过程，每一步比较 C－ F (s)与 (s)P (0)。
F (s0)=F (s) F (s1)=F (s)+P (s)?P (0)
? s为前面已译出的序列串；
? P (s)是序列串 s对应的宽度；
? F (s)是序列串 s的累积分布函数，即为 s对应区间的下界；
? P (s)P (0)是此区间内下一个输入为符号, 0”所占的子区
间宽度；
? 若 C－ F (s)<P (s)P (0)则译输出符号为, 0”；
若 C－ F (s)>P (s)P (0)则译输出符号为, 1”。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
例：设二元无记忆信源 S={0,1}，其 P (0)=1/4,P (1)=3/4。对二元序 列
11111100做算术编码。
解,P (s=11111100)=P 2(0)P 6(1)=(3/4)6(1/4)2
F (sr)=F (s)+P (s)?F (r)
F (s0)=F (s) F (s1)=F (s)+P (s)?F (1)= F (s)+P (s)?P (0)
F (s)=P (0)+P (1)P (0)+P (1)2P (0)+P (1)3P(0)+P (1)4P (0)+P (1)5P (0)
=0.82202=0.110100100111
得 C＝ 0.1101010 得 s的码字为 1101010。
编码效率
2
1l o g 7
( s)k P
??????
( ) ( ) 0, 8 1 1 92%
7 / 8/
H s H s
R KL? ? ? ? ?
第八节 游程编码、算术编码、冗余编码
? 我们学习了 6种信源编码,香农编码, 费诺编码, 哈夫
曼编码, 游程编码, 算术编码 。
? 游程编码和算术编码是非分组编码；
? 游程编码是限失真信源编码。
? 本章介绍的都是离散信源变长编码。
? 优点,提高编码效率 ；
? 缺点,需要大量缓冲设备来存储这些变长码，然后再以恒定的
码率进行传送；在传输的过程中如果出现了误码，容易引起错
误扩散，所以要求有优质的信道。
? 有时为了得到较高的编码效率，先采用某种正交变换，
解除或减弱信源符号间的相关性，然后再进行信源编码；
有时则利用信源符号间的相关性直接编码。
信
源
编
码
总
结
第一节 引言
第二节 码的分类
第三节 等长信源编码定理
第四节 变长信源编码定理
第八节 游程编码、算术编码、冗长编码
第六节 费诺编码
第七节 霍夫曼编码
第五节 香农编码
? 信源编码,以 提高通信有效性 为目的的编码。通常通过压缩信
源的冗余度来实现。采用的一般方法是压缩每个信源符号的平
均比特数或信源的码率。即同样多的信息用较少的码率传送，
使单位时间内传送的平均信息量增加，从而提高通信的有效性。
? 信道编码,是以 提高信息传输的可靠性 为目的的编码。通常通
过增加信源的冗余度来实现。采用的一般方法是增大码率 /带宽。
与信源编码正好相反。
? 密码,是以 提高通信系统的安全性 为目的的编码。通常通过加
密和解密来实现。从信息论的观点出发，“加密”可视为增熵
的过程，“解密”可视为减熵的过程。
第一节 引言
? 信源编码理论是信息论的一个重要分支，其理论基础是信源编
码的两个定理。
? 无失真信源编码定理,是离散信源 /数字信号编码的基础；
? 限失真信源编码定理,是连续信源 /模拟信号编码的基础。
? 信源编码的分类：离散信源编码、连续信源编码和相关信源编
码三类。
? 离散信源编码,独立信源编码，可做到无失真编码；
? 连续信源编码,独立信源编码，只能做到限失真信源编码；
? 相关信源编码,非独立信源编码。
第一节 引言
第二节 码的分类
编码器可以看作这样一个系统，它的输入端为原始信
源 S，其符号集为 ；而信道所能传输的符号集
为 编码器的功能是用符号集 X中的元素，将
原始信源的符号 变换为相应的码字符号,所以编码器
输出端的符号集为
称为 码字, 为码字 的码元个数，称为码字 的码字
长度，简称 码长 。
12{,,...,}qS S S S?
12{,,..,,}rX x x x?
12{,,...,}qS S S S?
12{,,..,,}rX x x x?
编码器
12,{,,...,}qC W W W
12,{,,...,}qC W W W
iS i
w
iw iL iw iw
1,二元码：
码符号集 X={0,1}，如果要将信源通过二元信道传输，必
须将信源编成二元码，这也是最常用的一种码。
2,等长码：
若一组码中所有码字的长度都相同，称为等长码。
3,变长码：
若一组码中所有码字的长度各不相同，称为变长码。
4,非奇异码：
若一组码中所有码字都不相同，称为非奇异码。
第二节 码的分类
5,奇异码：
若一组码中有相同的码字，称为奇异码。
6,码的 N次扩展：
若码, 码 则称码 B为
码 C的 N次扩展码。
7,唯一可译码：
若码的任意一串有限长的码符号序列只能被唯一的译成
所对应的信源符号序列，则称此码为 唯一可译码 。
12,{,,...,}qC W W W 12,{ (,.,) }i i i iNB B W W W?
第二节 码的分类
例：如果有四个信源符号 {s1,s2,s3,s4}，采用二元编
码,l=2，则可以编成 s1=00,s2=01,s3=10,s4=11。
第三节 等长信源编码定理
如果我们要对信源的 N次扩展信源进行编码，也必须满足
,两边取对数得：Nlqr? lo g
lo g
lq
Nr?
表示平均每个信源符号所需的码符号个数。lN
若对信源进行等长编码，则必须满足
其中,l是码长,r是码符号集中的码元数,q信源符号个数。
lqr?
第二节 等长码
例：对英文电报得 32个符号进行二元编码，根据上述关系：
l o g 3 2 5
l o g 2l ??
我们继续讨论上面得例子，我们已经知道英文的极限
熵是 1.4bit,远小于 5bit，也就是说,5个二元码符号只携带
1.4bit的信息量，实际上,5个二元符号最多可以携带 5bit
信息量。我们可以做到让平均码长缩短，提高信息传输率
第二节 等长码
我们举例说明：
设信源
31 2 4
1 2 3 4( ) ( ) ( ) ( ) ( )
ss s sS
P s P s P s P s P s
???? ? ????
?? ??
4
1
( ) 1i
i
Ps
?
??
而其依赖关系为：
2 1 1 2 4 3 3 4( / ) ( / ) ( / ) ( / ) 1,( / ) 0jiP s s P s s P s s P s s P s s? ? ? ? ?其余
第二节 等长码
若不考虑符号间的依赖关系，可得码长 l＝ 2
若考虑符号间的依赖关系，则对此信源作二次扩展
2
3 4 4 31 2 2 1
2 1 2 2 1 3 4 4 3( ) ( ) ( ) ( )()
s s s ss s s sS
P s s P s s P s s P s sPs
?? ????? ??
????
( ) 1ij
ij
P s s ??
可见，由于符号间依赖关系的存在，扩展后许多符号出
现的概率为 0，此信源只有 4个字符，可得码长,
但平均每个信源符号所需码符号为
' 2l ?
' 1l
N ?
第二节 等长码
我们仍以英文电报为例，在考虑了英文字母间的相关性
之后，我们对信源作 N次扩展，在扩展后形成的信源（也
就是句子）中，有些句子是有意义的，而有些句子是没有
意义的，我们可以只对有意义的句子编码，而对那些没有
意义的句子不进行编码，这样就可以缩短每个信源符号所
需的码长。
等长信源编码定理给出了进行等长信源编码所需码长的
极限值。
定理 4.3（等长信源编码定理） 一个熵为 H(S)的离散无记
忆信源，若对其 N次扩展信源进行等长 r元编码，码长为 l，
对于任意 大于 0，只要满足?
()
lo g
l H S
Nr
???
当 N无穷大时，则可以实现几乎无失真编码，反之，若：
( ) 2
lo g
l H S
Nr
???
则不可能实现无失真编码，当 N趋向于无穷大是，译码错
误率接近于 1。
第三节 等长信源编码定理
?定理 4.3的条件式可写成,lo g ( )l r N H S?
左边表示长为 的码符号所能载荷的最大信息量，
而右边代表长为 N的序列平均携带的信息量。因此，
只要码字传输的信息量大于信源序列携带的信息量，
总可以实现无失真编码 。
l
第三节 等长信源编码定理
?定理 4.3的条件式也可写成,l o g ( )l r H SN ???
令：
' lo glRr
N?
称之为 编码信息率 。可见，编码信息
率大于信源的熵，才能实现无失真编码。
最佳编码效率为：
'
( ) ( )
()
H S H S
R H S? ??? ?
1 ()HS??
?
??
第三节 等长信源编码定理
为了衡量编码效果，引进
'
( ) ( )
l o g
H S H S
lR r
N
? ?? 称为 编码效率 。
例：设离散无记忆信源：
12
31()
44
ssS
Ps
????
?????
????
??
1 3 4( ) l o g 4 l o g 0, 8 1 14 4 3HS ? ? ?
2 2 2 2 2 2
1
1 3 4[ ( ) ] ( l og ) [ ( ) ] ( l og 4) ( l og ) 0.8 11 0.4 715
4 4 3i i iiD I s p p H S?? ? ? ? ? ??
若采用等长二元编码，要求编码效率,允许错误率0.96? ?
510? ??,则,74,1 3 1 0N ??
也就是长度要达到 4130万以上。
第三节 等长信源编码定理
1、唯一可译变长码与及时码
信源符号 出现概率 码 1 码 2 码 3 码 4
s1
s2
s3
s4
1/2
1/4
1/8
1/8
0
11
00
11
0
10
00
01
1
10
100
1000
1
01
001
0001
第四节 变长信源编码定理
第五节 变长码
码 1是一个奇异码，不是唯一可译码；码 2也不是唯一
可译码，因为收到一串序列是，无法唯一译出对应的原符
号序列，如 0100，即可译作 s4s3s1,也可译作
s4s1s3,s1s2s3或 s1s2s1s1；码 3和码 4都是唯一可译的。
但码 3和码 4也不太一样，码 4称作逗点码，只要收到 1，
就可以立即作出译码；而码 3不同，当受到一个或几个码
是，必须参考后面的码才能作出判断。
定义,在唯一可译码中，有一类码，它在译码是无须参
考后面的码字就可以作出判断，这种码称为 即时码 。
定义,如果一个码组中的任一个码字都不是另一个码字的续
长，或者说，任何一个码字后加上若干码元后都不是码组中
另一个码字，则称为 即时码 。
所有的码
非奇异码
唯一可译码
即时码
第四节 变长信源编码定理
2、即时码的树图构造法
我们可以用树图的形式构造即时码，如
0 1
0
0
1
1
1
1
01
001
0001
码 4的树图
1 0
1
1
0
0
0
0
10
100
1000
码 3的树图
第四节 变长信源编码定理
树根 ——码字的起点
树枝数 ——码的数
节点数 ——码字的一部分
节数 ——码长
端点 ——码字
满树 ——等长码
非满树 ——变长码
在每个节点上都有 r个分枝的树称为 整树,否则称为 非
整树 。
即时码的树图还可以用来译码
第四节 变长信源编码定理
3、克拉夫特（ Kraft）不等式
定理 4.4 对于码符号为 的任意即时码，
所对应的码长为,则必定满足：
12{,,...,}qX x x x?
12,,...,ql l l
1
1i
q
l
i
r ?
?
??
反之，若码长满足上式，则一定存在这样的即时码 。
可以根据即时码的树图构造法来证明。
后来,B.McMillan证明了对于唯一可译码也必须满足
上面的不等式，
第四节 变长信源编码定理
定理 4.6 若存在一个码长为 唯一可译码，则一
定存在一个同样长度的即时码。
这说明，其他唯一可译码在码长方面并不比即时码
占优。所以在讨论唯一可译码时，只需要讨论即时码就
可以了。
12,,,ql l l
第四节 变长信源编码定理
设信源
12
12
...
...
q
n
a a xX
p p pP
???? ?
?????? ??
编码后的码字为：
12,,...,qW W W 码长为,12,,...,ql l l
则这个码的平均长度为：
1
()
q
ii
i
L P S l
?
? ?
平均每个码元携带的信息量即编码后的信息传输率为,()HSR
L?
若有一个唯一可译码，它的平均码长小于其他唯一可译码的
长度，则称此码为 紧致码 或 最佳码,无失真信源编码的基本
问题就是寻找紧致码。
第四节 变长信源编码定理
定理 4.8 无失真变长信源编码定理（香农第一定理）
离散无记忆信源 S的 N次扩展信源,其熵为,并且
编码器的码元符号集为 A,对信源 进行编码，
总可以找到一种编码方法，构成单义可译码，使信源 S中每
个符号 si所需要的平均码长满足
NS ()NHS
12{,,...,}q? ? ?
NS
( ) ( ) 1
l o g l o g
NH S L H S
r N r N? ? ?
li m ( )rN L H S?? ?当 则得：N??
第四节 变长信源编码定理
这个定理是香农信息论中非常重要得一个定理，它指
出，要做到无失真得信源编码，信源每个符号所需要的平
均码元数就是信源的熵值，如果小于这个值，则唯一可译
码不存在，可见,熵是无失真信源编码的极限值 。定理还
指出，通过对扩展信源进行编码，当 N趋向于无穷时，平
均码长可以趋进该极限值。
还可以证明，如果我们不确切知道信源的概率分布，
我们用估计的概率分布去进行编码时，平均码长会加长，
但是如果估计的偏差不大的话，平均码长也不会增加太多
（定理 4.9的内容）。
第四节 变长信源编码定理
( ) ( ) 1
l o g l o g
NH S L H S
r N r N? ? ?由
得,( ) l o g ( )NLH S r H S
N?? ? ?
logNL rN
就是编码后每个信源符号所携带的平均信息量
' lo gNLRr
N?
第一定理可以表述如下：若 就存在唯一可译
变长码，若 则不存在唯一可译变长码。
' ()R H S?
' ()R H S?
第四节 变长信源编码定理
定义：
若从信道角度讲，信道的信息传输率 ()HSR
L?因为：
()
logN
L HSL
Nr?? 所以 logRr?
当平均码长达到极限值时，编码后信道的信息传输率为,logRr?
无噪信道编码定理 若信道的信息传输率 R不大于信道容
量 C，总能对信源的输出进行适当的编码，使的在无噪无
损信道上能无差错的以最大信息传输率 C传输信息，若 R
小于 C，则无差错传输是不可能的。
第四节 变长信源编码定理
编码效率,()rHs
L? ?
码的剩余度,1 ??
在二元无噪无损信道中,()Hs
L? ?
在二元无噪无损信道中信息传输率,()HsR
L ???
例：
12
() 3 / 4 1 / 4
ssS
PS
???? ?
?????? ??
其熵为,H(S)=0.811我们令 s1=0,s2=1，这时平均码长,编码的
效率为 。
1L?
0.811? ?
第四节 变长信源编码定理
二次扩展信源进行编码,即时码
s1s1 9/16 0
s1s2 3/16 10
s2s1 3/16 110
s2s2 1/16 111
i? ()iP?
2 9 / 16 *1 3 / 16 * 2 3 / 16 * 3 1 / 16 * 3 27 / 16L ? ? ?＋＋
2 2 7 / 3 22LL ?? 0.961? ?
第五节 香农编码
? 设离散无记忆信源
? 二进制香农码的编码步骤如下：
? 将信源符号按概率从大到小的顺序排列，为方便起见，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 令 p(x0)=0，用 pa(xj),j=i+1表示第 i个码字的累加概率，则：
? 确定满足下列不等式的整数 ki,并令 ki为第 i个码字的长度
? － log2 p(xn)≤ki<－ log2 p(xn)+1
? 将 pa(xj) 用二进制表示，并取小数点后 ki 位作为符号 xi的编码。
1
0
( ) ( ),1,2,,ja j i
i
p x p x j n?
?
???
12
112
,,,,,,( ) 1
( ),( ),,( ),,( )()
nin
i
iin
x x x xX px
p x p x p x p xPX ?
???? ????
???? ?? ?
第五节 香农编码
例 有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如下表所示。
二 进制香农编码
x i p ( x i ) p a ( x j ) k i 码字
x 1 0, 2 5 0, 0 0 0 2 0 0 (0, 0 0 0 ) 2
x 2 0, 2 5 0, 2 5 0 2 0 1 (0, 0 1 0 ) 2
x 3 0, 2 0 0, 5 0 0 3 1 0 0 (0, 1 0 0 ) 2
x 4 0, 1 5 0, 7 0 0 3 1 0 1 (0, 1 0 1 ) 2
x 5 0, 1 0 0, 8 5 0 4 1 1 0 1 (0, 1 1 0 1 ) 2
x 6 0, 0 5 0, 9 5 0 5 1 1 1 1 1 0 (0, 1 1 1 1 0 ) 2
1 2 3 4 5 6,,,,,
( ) 0, 2 5 0, 2 5 0, 2 0 0, 1 5 0, 1 0 0, 0 5
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
第五节 香农编码
? 计算出给定信源香农码的平均码长
? 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3
个比特表示。相比较，香农编码对信源进行了压缩。
? 由离散无记忆信源熵定义，可计算出：
? 对上述信源采用香农编码的信息率为
? 编码效率为信源熵和信息率之比。则
? 可以看出，编码效率并不是很高。
0.25 2 2 ( 0.2 0.15 ) 3 0.10 4 0.05 5 2.7 ( / )K ? ? ? ? ? ? ? ? ? ? ? 比特 符号
22
2, 7l o g l o g 2 2, 7 1,2
1
KR m L m
L? ? ? ? ?这里
( ) 2, 4 2 8 9, 6 3 %
2, 7
HX
R? ? ? ?
6
21( ) ( ) l o g ( ) 2,4 2 ( / )iiiH X p x p x?? ? ?? 比特 符号
第六节 费诺编码
费诺编码也是一种常见的信源编码方法。
编码步骤如下：
? 将概率按从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 按编码进制数将概率分组，使每组概率尽可能接近或相等。如
编二进制码就分成两组，编 m进制码就分成 m组。
? 给每一组分配一位码元。
? 将每一分组再按同样原则划分，重复步骤 2和 3，直至概率不再
可分为止。
第六节 费诺编码
例 设有一单符号离散信源
? 对该信源编二进制费诺码。编码过程如下表。
二进制费诺编码
信源符号 概率 编码 码字 码长
x 1 0, 3 2 0 00 2
x 2 0, 2 2
0
1 01 2
x 3 0, 1 8 0
10 2
x 4 0, 1 6 0 1 1 0 3
x 5 0, 0 8 0 1 1 1 0 4
x 6 0, 0 4
1
1
1
1 1111 4
1 2 3 4 5 6,,,,,
( ) 0, 3 2 0, 2 2 0, 1 8 0, 1 6 0, 0 8 0, 0 4
X x x x x x x
PX
? ? ? ?? ????
? ? ? ?
第六节 费诺编码
? 该信源的熵为
? 平均码长为
? 编码效率为
? 本例中费诺编码有较高的编码效率。费诺码比较适合于
每次分组概率都很接近 的信源。特别是对每次 分组概率
都相等 的信源进行编码时，可达到理想的编码效率。
6
2
1
( ) ( ) l o g ( ) 2,3 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
6
1
( ) 2.4( / )ii
i
K p x k
?
??? 比特 符号
2.422 1
( ) 2,3 5 2,3 5 9 7,9 2 % 1,2
l o g l o g 2 2,4KL
HX Lm
m? ? ? ? ? ? ?这里
第六节 费诺编码
? 题中码字还可用码树来表示，如图所示。
第七节 霍夫曼编码
霍夫曼 (Huffman)编码是一种效率比较高的变长
无失真信源编码方法。
? 编码步骤
? 二进制哈夫曼编码
? m进制哈夫曼编码
第七节 霍夫曼编码 —— 编码步骤
? 将信源符号按概率从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
? 给两个概率最小的信源符号 p(xn-1)和 p(xn)各分配一个码位,0”和,1”，
将这两个信源符号合并成一个新符号，并用这两个最小的概率之和
作为新符号的概率，结果得到一个只包含 (n－ 1)个信源符号的新信源。
称为 信源的第一次缩减信源,用 S1表示。
? 将缩减信源 S1的符号仍按概率从大到小顺序排列，重复步骤 2，得到
只含 (n－ 2)个符号的缩减信源 S2。
? 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符
号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径向
前返回，就得到各信源符号所对应的码字。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
例 设单符号离散无记忆信源如下，要求对信源编二进制
霍夫曼码。编码过程如下图（后页）。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
? 在图中读取码字的时候，一定要从后向前读，此时编出
来的码字才是可分离的异前置码。若从前向后读取码字，
则码字不可分离。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
第七节 霍夫曼编码 —— 二进制哈夫曼编码
? 将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。
? 信源熵为：
? 平均码长为
? 编码效率为
? 若采用定长编码，码长 K=3，则编码效率
? 可见哈夫曼的编码效率提高了 12.7%。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
8
2
1
( ) ( ) l o g ( ) 2,5 5 ( / )ii
i
H X p x p x
?
? ? ?? 比特 符号
8
1
( ) 0,4 1 ( 0,1 8 0,1 ) 3 ( 0,1 0 0,0 7 0,0 6 ) 4 ( 0,0 5 0,0 4 ) 5 2,6 1 ( / )ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
( ) ( ) 2, 5 52, 6 1 9 7, 7 %H X H XR K? ? ? ? ?
2.553 85%? ??
第七节 霍夫曼编码 —— 二进制哈夫曼编码
注意, 哈夫曼的编法并不惟一 。
? 每次对缩减信源两个概率最小的符号分配,0”和,1”码元是任意的，
所以可得到不同的码字。只要 在各次缩减信源中保持码元分配的一致
性, 即能得到可分离码字。
? 不同的码元分配，得到的具体码字不同，但码长 ki不变，平均码长
也不变，所以没有本质区别；
? 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方
法上来说,这几个符号的次序可任意排列，编出的码都是正确的，但
得到的 码字不相同 。 不同的编法得到的 码字长度 ki也不尽相同 。
K
例,单符号离散无记忆信源,用
两种不同的方法对其编二进制哈夫曼码。
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
方法一,合并后的新符号排在其它相同概率符号的后面。
1 2 3 4 5,,,,,
( ) 0, 4 0, 2 0, 2 0, 1 0, 1
X x x x x x
PX
? ? ? ?? ????
? ? ? ?
第七节 霍夫曼编码 —— 二进制哈夫曼编码
si li Wi 概率
s1
s2
s3
s4
s5
1
2
3
4
4
1
01
000
0010
0011
0.4
0.2
0.2
0.1
0.1
0.4
0.2
0.2
0.2
0.4
0.4
0.2
0.6
0.4
0
1
0
1
0
1
这两种编码哪一种更好呢，我们来计算一下二者的码长。
方法二,合并后的新符号排在其它相同概率符号的前面。
第七节 霍夫曼编码 —— 二进制哈夫曼编码
两种编码的平均码长是一样的，都是 2.2，那一种更好呢，
我们可以计算一下平均码长的方差。
5
1
1
( ) 0.4 1 0.2 2 0.2 3 0.1 4 0.1 4 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
5
2
1
( ) 0.4 2 0.2 2 0.2 2 0.1 3 0.1 3 2.2ii
i
L P s l
?
? ? ? ? ? ? ? ? ? ? ? ??
2 2 2
1
[ ( ) ] ( ) ( )qi i i
i
E l L P s l L?
?
? ? ? ??
522
11
1
( ) ( ) 1.36ii
i
P s l L?
?
? ? ??
522
1
( ) ( ) 0,1 6ii
i
P s l L?
?
? ? ??
定义码字长度的方差 σ2：
第七节 霍夫曼编码 —— 二进制哈夫曼编码
第七节 霍夫曼编码 —— 二进制哈夫曼编码
? 可见：第二种编码方法的码长方差要小许多。意味着第二种
编码方法的码长变化较小，比较接近于平均码长。
? 第一种方法编出的 5个码字有 4种不同的码长；
? 第二种方法编出的码长只有两种不同的码长；
? 显然,第二种编码方法更简单、更容易实现，所以更好 。
结论, 在哈夫曼编码过程中，对缩减信源符号按概率由大到小
的顺序重新排列时，应 使合并后的新符号尽可能排在靠前的
位置,这样可使合并后的新符号重复编码次数减少，使短码
得到充分利用。
第七节 霍夫曼编码 —— m进制哈夫曼编码
“全树”概念
? 定义：码树图中每个中间节点后续的枝数为 m时称为 全树 ；若
有些节点的后续枝数不足 m，就称为 非全树 。
? 二进制码不存在非全树的情况，因为后续枝数是一时，这个枝
就可以去掉使码字长度缩短。
? 对 m进制编码：若所有码字构成全树，可分离的码字数（信源
个数）必为 m+k(m－ 1)。 k为信源缩减次数。
? 若信源所含的符号数 n不能构成 m进制全树，必须增加 s个不用
的码字形成全树。显然 s<m－ 1，若 s=m－ 1，意味着某个中间
节点之后只有一个分枝，为了节约码长，这一分枝可以省略。
第七节 霍夫曼编码 —— m进制哈夫曼编码
? 在编 m进制哈夫曼码时为了使平均码长最短，必须使最
后一步缩减信源有 m个信源符号。非全树时，有 s个码字
不用：
? 第一次对最小概率符号分配码元时就只取 (m－ s)个，
分别配以 0,1,…,m－ s－ 1，把这些符号的概率相加作
为一个新符号的概率，与其它符号一起重新排列。
? 以后每次就可以取 m个符号，分别配以 0,1,…,m－
1； … ；如此下去，直至所有概率相加得 1为止，即得
到各符号的 m进制码字。
第七节 霍夫曼编码 —— m进制哈夫曼编码
例：对如下单符号离散无记忆信源 (例 5.4.1)编三进制哈夫
曼码。
这里,m=3,n=8
? 令 k=3,m+k(m－ 1)=9，则 s=9－ n=9－ 8=1
? 所以第一次取 m－ s=2个符号进行编码。
1 2 3 4 5 6 7 8,,,,,
( ) 0, 4 0, 1 8 0, 1 0, 1 0, 0 7 0, 0 6 0, 0 5 0, 0 4
X x x x x x x x x
PX
? ? ? ?? ????
? ? ? ?
第七节 霍夫曼编码 —— m进制哈夫曼编码
第七节 霍夫曼编码 —— m进制哈夫曼编码
? 平均码长为：
? 信息率为：
? 编码效率为：
? 可见：哈夫曼的编码效率相当高，对编码器的要求也简单得多。
5
1
1
( ) 0.4 1 ( 0.1 8 0.1 0.0 7 0.0 6) 2 ( 0.0 5 0.0 4) 3 1.6 9( /)ii
i
K p x k
?
? ? ? ? ? ? ? ? ? ? ? ?? 比特 符号
22
1, 6 9l o g 3 l o g 3 2, 6 8 ( / )
1
KR
L? ? ? 比特 符号
( ) 2, 5 5 9 5, 2 %
2, 6 8
HX
R? ? ? ?
一些结论
? 香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出
现的信源符号对应较短的码字，使信源的平均码长缩短，从而实
现了对信源的压缩；
? 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不
是很高；
? 费诺码和哈夫曼码的编码方法都不惟一；
? 费诺码比较适合于对分组概率相等或接近的信源编码；
? 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对
编码设备的要求也比较简单，因此综合性能优于香农码和费诺码 。
第八节 游程编码、算术编码
? 香农编码、费诺编码、哈夫曼编码主要是针对无
记忆信源。当信源有记忆时上述编码效率不高；
? 游程编码对 相关信源 编码更有效；
? 香农编码、费诺编码、哈夫曼编码属于 无失真信
源编码 ；
? 游程编码属于 限失真信源编码 。
第八节 游程编码、算术编码、冗余编码
? 游程,数字序列中连续出现相同符号的一段。
? 二元序列的游程：只有,0”和,1”两种符号。
? 连,0”这一段称为,0”游程，它的长度称为 游程长度 L(0)；
? 连,1”这一段称为,1”游程，它的游程长度用 L(1)表示。
游
程
编
码
① 二元独立序列游程长度概率
? 若规定二元序列总是从,0”开始。
? 对于随机序列，游程长度是随机的其取值可为 1,2,3,…,直至无穷。
? 游程长度序列 /游程序列：用交替出现的,0”游程和,1”游程长度表示任意二
元序列。
? 游程变换,是一种一一对应的变换，也是可逆变换。
例如：二元序列,000101110010001…,可变换成如下游程序列,31132131
第八节 游程编码、算术编码、冗余编码
? 游程变换减弱了原序列符号间的相关性。
? 游程变换 将二元序列变换成了多元序列 ；这样就适合于用
其他方法，如哈夫曼编码，进一步压缩信源，提高通信效
率。
? 编码方法：
? 首先测定,0”游程长度和,1”游程长度的概率分布，即
以游程长度为元素，构造一个新的信源 ；
? 对新的信源（游程序列）进行哈夫曼编码。
游
程
编
码
第八节 游程编码、算术编码、冗余编码
② 二元独立序列游程长度的熵
? 若二元序列的概率特性已知，由于二元序列与游程变换序列
的一一对应性，可计算出游程序列的概率特性。
? 令,0”和,1”的概率分别为 p0和 p1，则,0”游程长度 L(0)的概
率为
p[L(0)]=p0L(0)－ 1p1 式中 L(0)=1,2,…,
? 在计算 p[L(0)]时必然已有,0”出现，否则就不是,0”游程，若
下一个符号是,1”，则游程长度为 1，其概率是 p1 =1－ p0；若
下一个符号为,0”、再下一个符号为,1”，则游程长度为 2，
其概率将为 p0p1 ；依此类推。
游
程
编
码
第八节 游程编码、算术编码、冗余编码
游
程
编
码
? 游程长度至少是 1，理论上，游程长度可以是无穷，但
很长的游程实际出现的概率非常小。
? 同理可得,1”游程长度 L(1)的概率为：
P[L(1)]=p1L(1)-1p0
?,0”游程长度的熵：
02
( 0 ) 1 1
()[ ( 0)] [ ( 0)] l og [ ( 0)]
L
HpH L p L p L
p
?
?
? ? ??
第八节 游程编码、算术编码、冗余编码
③ 二元独立序列的平均游程长度
?, 0”游程序列的平均游程长度
? 同理可得,1”游程长度的熵和平均游程长度
( 0 ) 1
0 0 1
( 0 ) 1 ( 0 ) 1
( 0 )
10
( 0 ) 1 01
1 2 3 4
[ ( 0 ) ] ( 0 ) [ ( 0 ) ] ( 0 )
1
( 1 ) 1
L
LL
L
L
l E L L p L L p p
d
pp
d p p
x x x x x
??
?
??
?
?
?
? ? ?
??
? ? ? ? ? ? ?
??
?
0
1
00
() 1[ ( 1 ) ] [ ( 1 ) ]HpH L l E L
pp? ? ?
游
程
编
码
第八节 游程编码、算术编码、冗余编码
游
程
编
码
④ 二元独立序列的熵
?, 0”游程序列的熵与,1”游程长度的熵之和除以它们的平均游程
长度之和，即为对应原二元序列的熵 H(X)
? 游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，
所以变换后熵值不变。
01
01
[ ( 0 ) ] [ ( 1 ) ]( ) ( ) ( )H L H LH X H p H p
ll
?? ? ?
?
第八节 游程编码、算术编码、冗余编码
? 游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编
码可获得较高的编码效率。
? 假设,0”游程长度的哈夫曼编码效率为 η0，,1”游程长度的哈
夫曼编码效率为 η1，由编码效率的定义和式 (5.4.9)可得对应二
元序列的编码效率（信源熵和信息率之比为编码效率 η=H(X)/R）
? 当,0”游程和,1”游程的编码效率都很高时，采用游程编码的
效率也很高，至少不会低于较小的那个效率。要想编码效率尽
可能高，应尽可能提高熵值较大的游程编码效率。
01
[ ( 0 ) ] [ ( 1 ) ]
0 1 0 1
[ ( 0) ] [ ( 1 ) ]
H L H L
H L H L
??
?
? ? ? ? ?
?
?
?
? ? ?假设,则有
游
程
编
码
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 算术编码不同于哈夫曼码，它 是非分组（非块）码 。它
从全序列出发，考虑符号之间的关系来进行编码。
? 算术编码利用了 累积概率 的概念。
? 算术码主要的编码方法是 计算输入信源符号序列所对应
的区间 。
? 因为在编码过程中，每输入一个符号要进行乘法和加法
运算，所以称此编码方法为算术编码。
? 二元序列的算术编码可用于黑白图像的编码，例如传真。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 设信源符号集 A={a1,a2,…,an}，其相应概率分布为 P (ai)，
P (ai) >0(i=1,2,…,n)
? 信源符号的累积分布函数为：
所得累积分布函数为每台级的下界值，则其区间为 [0,1)左闭
右开区间。
F (a1)=0
F (a2)=P (a1)
F (a3)=P (a1)+P (a2)
…
? 当 A={0,1}二元信源 时,F (0)= 0,F (1)=P (0)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 计算 二元无记忆信源序列 的累积分布函数
? 初始时：在 [0,1)区间内由 F (1)划分成二个子区间
[0,F (1))和 [F (1),1),F (1)= P (0)。
? 子区间 [0,F (1))的宽度为 A(0)= P (0)，对应于信源符号, 0”；
? 子区间 [F (1),1)的宽度为 A(1)= P (1)，对应于信源符号, 1”；
? 若输入符号序列的第一个符号为 s=“0”，落入 [0,F (1))区间，
得累积分布函数 F (s=“0”)= F (0)=0；
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 输入第二个符号为, 1”,s=“01”
? s=“01”所对应的区间是在区间 [0,F (1))中进行分割；
? 符号序列, 00”对应的区间宽度为,
A(00)=A(0)P (0)=P (0)P (0)=P (00)；
? 对应的区间为 [0,F (s=“01”))。
? 符号序列, 01”对应的区间宽度为
A(01)=A(0)P (1)=P (0)P (1)=P (01)= A(0)－ A(00)；
? 对应的区间为 [F (s=“01”),F (1))。
? 累积分布函数 F (s=“01”)=P (00)= P (0)P (0)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
第八节 游程编码、算术编码、冗余编码
算
术
编
码
输入第三个符号为, 1”：
? 输入序列可记做 s1=“011”（若第三个符号输入为, 0”，可记做
s0=“010”）；
? 现在，输入序列 s1=“011”对应的区间是对区间 [F(s),F(1))进行分割；
? 序列 s0=“010”对应的区间宽度为
A(s=“010”)=A(s=“01”)?P(0)=A(s)?P(0)
其对应的区间为 [F(s),F(s)+ A(s)?P(0))；
? 序列 s1=“011”对应的区间宽度为
A(s=“011”)=A(s)?P(1)=A(s=“01”)－ A(s=“010”)= A(s )－ A(s0)
其对应的区间为 [F(s)+A(s)?P(0),F(1))；
? 符号序列 s1=“011”的累积分布函数为 F(s1)=F(s)+A(s)?P(0)；
? 若第三个符号输入为, 0”，符号序列 s0=“010”的区间下界值仍为 F(s)，
得符号序列 s0=“010”的累积分布函数为 F(s0)=F(s)。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 归纳
? 当已知前面输入符号序列为 s，若接着再输入一个符号, 0”，
序列 s0的累积分布函数为,F(s0)=F(s)
? 对应区间宽度为,A(s0)=A(s)?P(0)
? 若接着输入的一个符号是, 1”，序列的累积分布函数为：
F(s1)=F(s)+A(s)?P(0)
? 对应区间宽度为,A(s1)=A(s)?P(1)=A(s)－ A(s0)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 符号序列对应的区间宽度
A(s=“0”)=P(0)
A(s=“1”)=1－ A(s=“0”)=P(1)
A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)
A(s=“01”)=A(s=“0”)－ A(s=“00”)=P(01)=A(0)P(1)=P(0)P(1)
A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)
A(s=“11”)=A(s=“1”)－ A(s=“10”)=P(11)= A(s=“1”)?P(1)=P(1)P(1)
A(s=“010”)=A(s=“01”)?P(0)=P(01)P(0)＝ P(010)
A(s=“011”)=A(s=“01”)-A(s=“010”)=A(s=“01”)?P(1)=P(01)P(1)=P(011)
信源符号序列 s所对应区间的宽度等于符号序列 s的概率 P(s)。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 二元信源符号序列的累积分布函数的递推公式
? F(sr)=F(s)+P(s)?F(r) (r=0,1)
? sr表示已知前面信源符号序列为 s，接着再输入符号为 r
F(0)=0,F(1)=P(0)
F(s0)=F(s)
F(s1)=F(s)+P(s)?F(1)= F(s)+P(s)?P(0)
? A(sr)=P(sr)=P(s)?P(r) (r=0,1)
A(s0)=P(s0)=P(s)?P(0)
A(s1)=P(s1)=P(s)?P(1)
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 举例：已输入二元符号序列为 s=“011”，接着再输入符号为, 1”，得
序列累积分布函数为：
F(s1)=F(0111)=F(s=“011”)+P(011)?P(0)
=F(s=“01”)+P(01)?P(0)+P(011)?P(0)
=F(s=“0”)+P(0)?P(0) +P(01)?P(0)+P(011)?P(0)
=0+P(00)+P(010)+P(0110)
对应的区间宽度为
A(s1)=P(s=“011”)?P(1)=P(011)P(1)=P(0111)
? 上述整个分析过程可用图 5.6.1描述
? 式 (5.6.1)和 (5.6.2)是可递推运算，在实际中，只需两个存储器，把 P(s)
和 F(s)存下来，然后，根据输入符号和式 (5.6.1),(5.6.2)更新两个存
储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和
加法运算，所以称为 算术编码 。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
( s 0 ) ( s )
( s 1 ) ( s ) ( s ) ( 0 )
( s 0 ) ( s 0 ) ( s ) ( 0 )
( s 1 ) ( s 1 ) ( s ) (1 )
FF
F F P P
A P P P
A P P P
?
??
??
??
第八节 游程编码、算术编码、冗余编码
算
术
编
码
通过关于信源符号序列的累积分布函数的计算，把区间分割成许
多小区间，不同的信源符号序列对应不同的区间为
[F(s),F(s)+P(s)) 。可取小区间内的一点来代表这序列。
? 编码方法, 将符号序列的累积分布函数写成二进位的小数，取
小数点后 k位，若后面有尾数，就进位到第 k位，这样得到的一个
数 C，并使 k满足
? 举例
? ?2
1 2 1 2
1l og
( s )
0,{ 0,1 },sk k k
k
P
C z z z z z z z
??
? ??????
??
代表大于或等于的最小整数
设 得符号序列 的码字为 。
1( s ) 0.10 110 001 ( s ) 3
7
0.11 0 s 110
F P k
C
? ? ?
?
则
得, 的码字为 。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
? 编码效率
? 这样选取的数值 C，一般根据二进小数截去尾数的影响得
C－ F(s)<1/2k，当在 l以后没有尾数时 C=F(s)。
F(s)+ 1/2k>C
? 而 P(s)≥1/2k
? 信源符号序列对应区间的上界为 F(s)+P(s)≥F(s)+1/2k>C
? 可见，数值在区间 [F(s),F(s)+P(s))内。而信源符号序列对应
的不同区间（左封右开）是不重叠的，所以编得的码是即时
码。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
2
22
s s s
1
l og
( s )
( s ) l og ( s ) ( s ) ( s ) ( s ) l og ( s ) 1
( ) ( ) 1
( ) ( )
LL
L
k
P
P P K P k P p
H S K H S
H S L H S
L L L L
??
? ??
??
? ? ? ? ? ?
? ? ? ?
? ? ?
由于 得
平均每个符号的码长为
,若信源是无记忆，
2
1( ) ( ) l o gKKH S R H S R m
L L L
??? ? ? ? ???
??
? 算术编码的编码效率很高。当信源符号序列很长时，
L很大时，平均码长接近信源的熵。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
译码就是一系列比较过程，每一步比较 C－ F (s)与 (s)P (0)。
F (s0)=F (s) F (s1)=F (s)+P (s)?P (0)
? s为前面已译出的序列串；
? P (s)是序列串 s对应的宽度；
? F (s)是序列串 s的累积分布函数，即为 s对应区间的下界；
? P (s)P (0)是此区间内下一个输入为符号, 0”所占的子区
间宽度；
? 若 C－ F (s)<P (s)P (0)则译输出符号为, 0”；
若 C－ F (s)>P (s)P (0)则译输出符号为, 1”。
第八节 游程编码、算术编码、冗余编码
算
术
编
码
例：设二元无记忆信源 S={0,1}，其 P (0)=1/4,P (1)=3/4。对二元序 列
11111100做算术编码。
解,P (s=11111100)=P 2(0)P 6(1)=(3/4)6(1/4)2
F (sr)=F (s)+P (s)?F (r)
F (s0)=F (s) F (s1)=F (s)+P (s)?F (1)= F (s)+P (s)?P (0)
F (s)=P (0)+P (1)P (0)+P (1)2P (0)+P (1)3P(0)+P (1)4P (0)+P (1)5P (0)
=0.82202=0.110100100111
得 C＝ 0.1101010 得 s的码字为 1101010。
编码效率
2
1l o g 7
( s)k P
??????
( ) ( ) 0, 8 1 1 92%
7 / 8/
H s H s
R KL? ? ? ? ?
第八节 游程编码、算术编码、冗余编码
? 我们学习了 6种信源编码,香农编码, 费诺编码, 哈夫
曼编码, 游程编码, 算术编码 。
? 游程编码和算术编码是非分组编码；
? 游程编码是限失真信源编码。
? 本章介绍的都是离散信源变长编码。
? 优点,提高编码效率 ；
? 缺点,需要大量缓冲设备来存储这些变长码，然后再以恒定的
码率进行传送；在传输的过程中如果出现了误码，容易引起错
误扩散，所以要求有优质的信道。
? 有时为了得到较高的编码效率，先采用某种正交变换，
解除或减弱信源符号间的相关性，然后再进行信源编码；
有时则利用信源符号间的相关性直接编码。
信
源
编
码
总
结
