第11讲信源编码三个基本编码

P ( X X ) 0 x .1 4 , 0 x .1 2 , 0 8 x .3 1 , 0 x .4 1 , 0 x .0 5 , 0 7 x .0 6 0 6 x .0 7 0 5 x .0 8 4
(1) 将信源符号按概率从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
5.1.1 码字唯一可译的条件 5.1.2 香农编码
5.1.3 费诺编码
5.1.4 赫夫曼编码
5.1.5 游程编码 5.1.6 冗余位编码
例:设有一单符号离散信源
P ( X X ) 0 x .3 1 ,
x 2 , 2 0 .2
x 3 , x 4 , 2 0 .18 0 .1
使编码中各个符号出现的概率尽可能地 相等，即概率均匀化。
信源编码的分类：离散信源编码、连续信 源编码和相关信源编码三类。
离散信源编码：独立信源编码，可做到无失真 编码；
连续信源编码：独立信源编码，只能做到限失 真信源编码；
相关信源编码：非独立信源编码。
信源编码的基础是信息论中的两个编码定理： 无失真编码定理只适用于离散信源 限失真编码定理 对于连续信源，只能在失真受限制的情况下进
(2) 信源的第一次缩减信源：给两个概率最小的信源符号 p(xn－1) 和 p(xn) 各分配一个码位“0”和“1”，将这两个信源符号合并成 一个新符号，并用这两个最小的概率之和作为新符号的概率，结
果得到一个只包含 (n－1) 个信源符号的新信源，用 S1 表示。
(3)将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复步骤 (2)，
得到只含 (n－2) 个符号的缩减信源 S2。
(4) 重复上述步骤，直至缩减信源只剩两个符号为止，此时所 剩两个符号的概率之和必为 1。然后从最后一级缩减信源开 始，依编码路径向前返回，就得到各信源符号所对应的码字。
8
信源熵为 H (X) p(xi)lo2p g (xi)2.5(比 5 /符 特 )号
• 计算出给定信源香农码的平均码长
K 0 .2 5 22(0 .20 .1) 5 30 .1 0 40 .0 5 5 2 .7 (码/符 元 ) 号
• 由离散无记忆信源熵定义，可计算出信源熵为：
6
H (X) p(xi)lo2p g (xi)2.4(比 2 /符 特 )号 i 1
i1
对上述信源采用费诺编码的信息率为
R K L lo 2 m g 2 1 .4 lo 2 2 g 2 .4 ( 比 /符 特 这 号 L 1 ,里 m ） 2
编码效率为
H(X)2.359.79% 2
R 2.4
5.1.1 码字唯一可译的条件 5.1.2 香农编码 5.1.3 费诺编码
1 .36
编法二码字长度方差：
2 2 ( 0 . 4 0 . 2 0 . 2 ) 2 ( 2 . 2 ) 2 ( 0 . 1 0 . 1 ) 3 2 ( . 2 ) 2 0 . 1
比较
相同点： • 香农编码、费诺编码、哈夫曼编码属于无失真信源编码。 • 香农编码、费诺编码、哈夫曼编码主要针对无记忆信源。 • 香农码、费诺码、哈夫曼码都考虑了信源的统计特性，
试对该信源编二进制香农码。
二进制香农码的编码步骤如下：
（1）将信源符号按概率从大到小的顺序排列
p(x1)≥ p(x2)≥…≥ p(xn) （2）令 p(x0)=0，用 pa(xj)，j=i+1 表示第 i 个码字的累加概率，则
j1
pa(xj) p(xi),j1,2, ,n i0
xi p(xi) pa(xj) ki 码 字 x1 0.25 0.000 2 00(0.000)2 x2 0.25 0.250 2 01(0.010)2 x3 0.20 0.500 3 100(0.100)2 x4 0.15 0.700 3 101(0.101)2 x5 0.10 0.850 4 1101(0.1101)2 x6 0.05 0.950 5 111110(0.11110)2
6 0 x .0 5 , 8 0 x .0 6 4
对该信源编二进制费诺码。
（1）将概率按从大到小的顺序排列
p(x1)≥ p(x2)≥…≥ p(xn)
（2）按编码进制数将概率分组，使每组概率尽可能接近
或相等。如编二进制码就分成两组，编 m 进制码就分
成 m 组。
信源符号 概率
编码
码字 码长
x1
0.32
0
0
x2
0.22
1
00
2
01
2
x3
0.18
0
10
2
x4
0.16 1
0
110
3
x5
0.08
1
0 1110 4
1
x6
0.04
1 1111 4
（3）给每一组分配一位码元。
（4）将每一分组再按同样原则划分，重复步骤 2 和 3， 直至概率不再可分为止。
信源符号 概率
x1
0.32 0
x2
0.22
x3
平均码长为
i 1
8
K p (x i)k i 0 .4 1 (0 .1 0 8 .1 ) 3 (0 .1 0 .0 0 7 .0) 6 4 (0 .0 0 5 .0) 4 5 i 1
2 .6(码 1/符 元 ) 号
编码效率为
H (X)H (X)2.5 59.7 7 %
[例] ：单符号离散无记忆信源
P(X X) 0 x1 .4 ,
x2, 0.2
x3,， x4,
0.2 0.1
0 x.5 1
用两种不同的方法对其编二进制哈夫曼码。
方法一：合并后的新符号排在其它相同概率符号的后面。
方法二：合并后的新符号排在其它相同概率符号 的前面。
行限失真编码
5.1 离散信源编码
5.1.1 码字唯一可译的条件
5.1.2 香农编码 5.1.3 费诺编码 5.1.4 赫夫曼编码
5.1.5 游程编码 5.1.6 冗余位编码
即时码：如果一个码的任何一个码字都不是其他码字 的前缀，则称该码为前缀码、异前置码也称为即时码。
n
满足克劳夫特不m等 ki 式 1是异前置码 i1
结论：哈夫曼码对信源的统计特性没有特殊要求，编码效
率比较高，对编码设备的要求也比较简单，因此综合性能 优于香农码和费诺码。
作业：5.1 5.2
可见 K1 K2 ，本例两种编法的平均码长相 同，所以编码效率相同。
讨论：
码字长度的方差σ2：长度 ki 与平均码长 K 之差的 平方的数学期望，即
n
2E [k (iK )2] p(xi)k(iK )2 i1
编法一码字长度方差：
1 2 0 .4 ( 1 2 .2 )2 0 .2 (2 2 .2 )2 0 .2 (3 2 .2 )2 (0 .1 0 .1 )4 ( 2 .2 )2
第5章：信源编码
通信系统的性能指标主要是有效性、可 靠性、安全性和经济性，除了经济性外， 这些指标正是信息论研究的对象。
编码的目的是为了优化通信系统，使这 些指标达到最佳；
按不同的编码目的，编码分为三类：信 源编码、信道编码和安全编码/密码。
• 信源编码的基本途径有两个：
使序列中的各个符号尽可能地互相独立， 即解除相关性；
异前置
对离散无记忆信源，消息长度为L，符号熵为H(X),对信 源进行m元变长编码，一定存在无失真的信源编码方法，
其码字平均长度 K 满足：
1LH (X)KLH (X)
lom g
lom g
其码字平均信息率 R 满足：
H (X )R H (X )
5.1.1 码字唯一可译的条件
5.1.2 香农编码
（3）确定满足下列不等式的整数 ki ，并令 ki 为第 i 个码字的 长度
－log2 p(xi) ≤ ki < 1－ log2 p(xi)
（4）将 pa(xj) 用二进制表示，并取小数点后 ki 位作为符号 xi 的编码。
xi p(xi) pa(xj) ki 码 字 x1 0.25 0.000 2 00(0.000)2 x2 0.25 0.250 2 01(0.010)2 x3 0.20 0.500 3 100(0.100)2 x4 0.15 0.700 3 101(0.101)2 x5 0.10 0.850 4 1101(0.1101)2 x6 0.05 0.950 5 111110(0.11110)2
•信息率为
RK Llo2gm是编码后平均 符每 号个 能信 载源 荷的 量最大
R K L lo 2 m g 2 1 .7 lo 2 2 g 2 .7 ( 比 /符 特 号 这 L 1 ,） 里 m 2
•编码效率为信源熵和信息率之比
H(X)2.428.96% 3
R 2.7
R K 2.61
若采用定长编码，码长 K=3，则编码效率
2.5585%
3
编码效率提高了 12.7%。
缩减信源时，若合并后的新符号概率与其他符 号概率相等，从编码方法上来说，这几个符号 的次序可任意排列，编出的码都是正确的，但 得到的码字不相同。不同的编法得到的码字长 度 ki 也不尽相同。
充要条件。
m为码符号数 ki 称为码字长度或简称码长
例
判断以下码字是否可分离？
消息 概率 码A 码B 码C 码D
a1 0.5 0
0
0
0
a2 0.25 0 1 01 10
a3 0.125 1 00 011 110 a4 0.125 10 11 0111 1110
可分离 不可不可可分离 即时码 分离分离有延时