信源编码（ 3）
数学与计算机科学学院 朱西平
(xpzhu188@163.com )
离散无记忆（简单）信源的不等长编码
不等长编码的优越性 总体上减少码字的长度。
不等长编码的特殊问题
①唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。
解决方案,适当地编码，使得每个码字都具有识别标记。
（注解：一个唯一可译的、码字长度不超过 N的 D元码，其码字个数小于 D(DN-1)/(D-1)个。这是因为两个码字 c(1)和
c(2) 连接成的字母串 c(1)c(2) 不能是码字）
离散无记忆（简单）信源的不等长编码
② 平均码字长度。设信源随机变量 U的概率分布为 {ak,p(ak),
k=1~K}，事件 ak对应的码字长度为 nk，则平均码字长度为希望 小。
解决方案：概率大的事件用短码字。
③实时译码和容量限制。
K
k
kk apnn
1
)(
n
2005-7-18 4
离散无记忆（简单）信源的不等长编码唯一可译性的两种解决方法
逗点码
①事件与码字一一对应；
②每个码字的开头部分都是一个相同的字母串；
③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。
则称这个字母串为逗号，称此码为 逗点码 。
异字头码
①若事件与码字一一对应；
②每个码字都不是另一个码字的开头部分（字头）。
则称此码为 异字头码 。
离散无记忆（简单）信源的不等长编码注解逗点码显然是唯一可译的，识别码字的方法为：
见到逗号就识别为一个码字的开始。
异字头码也是唯一可译的，识别码字的方法为：
见到一个码字就识别为一个码字。
离散无记忆（简单）信源的不等长编码
D
UHn
lo g
)(? 1
lo g
)(
D
UHn
任一唯一可译的 D元不等长码总满足存在唯一可译的 D元不等长码满足离散无记忆（简单）信源的不等长编码现在对信源随机向量 UL=(U1U2… UL)做唯一可译的 D元不等长码。
此时 UL的事件的个数为 KL。则任一唯一可译的 D元不等长码总满足存在唯一可译的 D元不等长码满足
D
ULH
D
UH
Un
L
L
lo g
)(
lo g
)(
)(
1
l o g
)(
1
l o g
)(
)(


D
ULH
D
UH
Un
L
L
离散无记忆（简单）信源的不等长编码重新定义平均码长：
任一唯一可译的 D元不等长码总满足存在唯一可译的 D元不等长码满足
D
UHn
lo g
)(?
LD
UHn 1
lo g
)(
L
Unn L )(?
离散无记忆（简单）信源的不等长编码定义编码速率 R和编码效率 η分别为任一唯一可译的 D元不等长码总满足存在唯一可译的 D元不等长码满足
DnL DUnR
L
l o gl o g)(
)(UHR?
L
DUHR l o g)(
注解 不等长编码与等长编码具有相似的性质：当 L增大时，对 UL的编码可以使用更短的平均码长，因而更加节省 编码速率。但 节省 编码速率的下限是 H(U)。
R
UH )(
离散无记忆（简单）信源的不等长编码例 做 2元编码。设 ； H(U)=0.811。
U 概率 码字 平均码长 编码速率 编码效率
a1 3/4 0 (1× 3/4+
1× 1/4)/1=1
1 0.811
a2 1/4 1
U2 概率 码字 平均码长 编码速率 编码效率
a1a1 9/16 0 (1× 9/16+
2× 3/16+
3× 3/16+
3× 1/16)/2
=27/32
27/32 0.961
a1a2 3/16 10
a2a1 3/16 110
a2a2 1/16 111
U={3/4,1/4}