第三章离散信源无失真编码上课用

定义：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。
惟一可译码
延长码（前缀码）
某些码字是其他 码字的前缀，或 者说，某些码字 后面增加一些码 元就可以变成其 他码字
延长码不全是惟一可译码 非延长码一定是惟一可译码
非延长码 （异前缀码）
码中的任何一个 码字都不是其他 码字的前缀，或 者说，任一个码 字后面增加一些 信道符号（码元） 都不可能变成另 一个码字
内容提要
用尽可能少的符号来传输信源消息，目的是提高传输效 率，这是信源编码应考虑的问题，这章讨论在不允许失真情况 下的信源编码。等长编码定理给出了等长编码条件下，其码长 的下限值，变长编码定理（香农第一定理）给出了信源无失真 变长编码时其码长的上、下限值。本章还介绍了三种通用信源 编码方法：香农编码法、费诺编码法和霍夫曼编码法。
2, …, M）都是一个D进制符号串，设c1，c2，…，cM 对应的码 长分别是n1，n2，…，nM，则存在惟一可译码的充要条件是
M
Dni
1
（克拉夫特不等式）
i 1
克拉夫特不等式所说的充要条件是对于码长组合而言的，而不是 对于码字本身。也就是说，满足克拉夫特不等式的码长组合一定 能构成惟一可译码，但满足克拉夫特不等式的码不一定是惟一可 译码。
如： 中 0022 01101 01101 11001 11001 国 0948
二．码的分类
信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符 号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度 为n的码字。对于同一个信源，编码方法是多种的。
【例3.1.2】 用{ a, b, c, d }表示信源的四个消息，码符号集为{0,1}，下表列
出了该信源的几种不同编码。

序列 x1x1 x1x2 x2x1 x2x2
序列概率 9/16 3/16 3/16 1/16
即时码 0 10 110 111
这个码的码字平均长度
lN
9 1
3 2
3 3
1 3 27
码元/ 信源序列
16 16 16 16 16
单个符号的平均码长
l
l
N
lN
27
码元 / 符号
N 2 32
编码效率
c
H(X)
例1：设有一简单DMS信源：
U
p
u1 1 2
u2 1 22
u3 1 23
u4 u5 u6 u7
111
1
24 25 26 26
用码元表X＝{0,1}对U的单个符号进行编码(N=1)，即对U
的单个符号进行2进制编码。
解：用X的两个码元对U的7个符号进行编码，单 个对应的定长码长：
l lN log q log 7 2.8 码元 / 符号 N log r log 2
j 1
log r
1 qN
r l j
ln 2
P(a j ) ln
j 1
P(aj )
1 qN
r l j
ln 2 j1 P(a j )( P(a j ) 1)
(ln z z 1)
qN
qN
rlj P(a j )
j 1
j 1
ln 2
11 0 (Kraft不等式和概率完备性质) ln 2
（2）根据信源的自信息量来选取与之对应的码长：
【说明】
霍夫曼编码是真正意义上的最佳编码，对给定的信源，平 均码长达到最小，编码效率最高，费诺编码次之，香农编码 效率最低。

第三章 离散信源无失真编码3.2离散无记忆信源，熵为H[x]，对信源的L 长序列进行等长编码，码字是长为n 的D 进制符号串，问：（1）满足什么条件，可实现无失真编码。

（2）L 增大，编码效率 也会增大吗？ 解：（1）当log ()n D LH X ≥时，可实现无失真编码；（2）等长编码时，从总的趋势来说，增加L 可提高编码效率，且当L →∞时，1η→。

但不一定L 的每次增加都一定会使编码效率提高。

3.3变长编码定理指明，对信源进行变长编码，总可以找到一种惟一可译码，使码长n 满足D X H log )(≤n <D X H log )(+L 1,试问在n >D X H log )(+L1时，能否也找到惟一可译码？ 解：在n >D X H log )(+L1时，不能找到惟一可译码。

证明：假设在n >D X H log )(+L1时，能否也找到惟一可译码，则由变长编码定理当n 满足D X H log )(≤n <D X H log )(+L 1，总可以找到一种惟一可译码知：在n ≥DX H log )( ① 时，总可以找到一种惟一可译码。

由①式有：Ln ≥L X H )(logD ② 对于离散无记忆信源，有H(x)=LX H )( 代入式②得：n L≥ D x H log )(即在nL≥Dx H log )(时，总可以找到一种惟一可译码；而由定理给定熵H （X ）及有D 个元素的码符号集，构成惟一可译码，其平均码长满足D X H log )(≤n L <DX H log )(+1 两者矛盾，故假设不存在。

所以，在n >D X H log )(+L1时，不能找到惟一可译码。

3.7对一信源提供6种不同的编码方案：码1~码6，如表3-10所示（1） 这些码中哪些是惟一可译码？ （2） 这些码中哪些是即时码？（3） 对所有唯一可译码求出其平均码长。

解：码1： 其二次扩展码是奇异码，如u1u2和u5u1对应的码字均为010；码2： 是惟一可译码，非奇异等长码是惟一可译码，且是即时码，平均码长为3； 码3： 是延长码，是惟一可译码，但不是即时码，平均码长为n =∑=71iii n p =3.06 码4： 是非延长码，故是惟一可译码，也是即时码；平均码长n =∑=71iii n p =3.06 码5： 是数码，即非延长码，因此是即时码；平均码长n =∑=71iii n p =2.625 码6：是非延长码，故是惟一可译码，也是即时码；平均码长n =∑=71iii n p =3.125 综上所述，码2~6均为惟一可译码，码2、4、5、6是即时码。

a3 a4
p(a2)
p(a3) p(a4)
01
10 11
01
001 111
2 码的类型
码
{
非分组码
分组码
{
奇异码 非奇异码
{
非唯一可译码 非即时码 唯一可译码 即时码（非延长码）
{
2.1 码符号集中符号数r＝2称为二元码，r＝3称为三元码 2.2 若分组码中的码长都相同则称为等长码，否则称为变长码
1 信源编码： 信源消息U=(u1,u2,…, uq) 码符号集X=(x1,x2,…, xr)
将 ui
Wi ＝（ w1,w2,…,wq）其中某一码字 wi∈{x1,x2,…xr}
这种一一对应变换称为信源编码。
若Li为码字Wi中的码元个数，则 Li称为码字Wi的长度， 简称码长。
分组码定义：
将信源消息分成若干组，即符号序列ui， ui=(ui1,ui2,…,uil,…,uiL) 序列中的每个符号取自于同一个符号集A， uil∈(a1,a2,…,an)。 而每个符号序列ui依照固定的码表映射成一个码字Wi，这 样的码称为分组码。只有分组码有对应的码表。
－Ki -1 -2 -3 -3 2 =2 +2 +2 +2 =1 i＝1 4
存在这种Ki的唯一可译码。
0 0 1 1
a1 a2
0
1
a1: 1 a2: 01 a3: 000 a4: 001
a3
a4
注意：克劳夫特（Kraft）不等式只是用来说明唯一可译码是否 存在，并不能作为判断哪些码是唯一可译码的依据。 如码字（0，10，010，111）满足克劳夫特不等式，但它不是 唯一可译码
如果每次只传送一个符号，即序列长度L＝1 ui=ui1∈(a1,a2,…,an) 要将这样 的符号进行传输，常采用二元信道，码符号集X为