第三章无失真信源编码
无失真编码概述
定长信源编码
变长信源编码
实用的无失真信源编码方法举
例
§ 3.1无失真编码概述 -1
通信中信息传输所要解决的基本问题是：
有效性和可靠性
? 在不失真或允许一定失真条件下，如何用尽
可能烧得符号来传送信源信息以提高信息传
输率－－－信源编码
? 在信道受干扰情况下，如何增加信号的抗干
扰能力同时又使得信息传输率最大 —— 信道
编码
§ 3.1无失真编码概述 -2
离散, 无失真, 无记忆信源编码的一般模型：
总码组合数：总组合数：
Ln Km
入 出
信源
编码X={x1,x2…xn}
Y=(Y1,Y2,.Yk)
Y∈ {y1,y2….ym}
§ 3.1无失真编码概述 -3
问题,能否进行无失真编码, 怎样进行无失真编码
若：不考虑信源统计特性：
应满足条件, 相互矛盾！
??
?
?
?
?
?
KL
L
mn
n
有效：
无失真,Km
l o g
l o g
LK LK nnm
Lm? ? ?
由
? 结论, ① 当 n = m 时, K≥L不有效 。
② 当 K = L 时, m≥n,亦不满足有效性
? 解决办法, 引入信源统计特性 。
§ 3.1无失真编码概述 -4
考察无失真条件,
分别表示等概条件下的消息熵 与码字熵 之比，
考虑信源的实际统计特性（非等概），实际消息熵为：
代入无失真条件得：
此时：即使 m=n,只要 就有可能实现 KL<L。
即无失真与有效性同时满足 。
具体实现 时,定长与变长编码
l o g
l o gL
KL LK nnm
Lm? ? ?
( ) l o gii
i
H X p p?? ?
()lo gLK HXLm?
lo g ( )m H X?
H(X)=logn H(Y)=logm
编码器可以看作这样一个系统，它的输入端为原始信
源 X，其符号集为 ；而信道所能传输的符号集
为 编码器的功能是用符号集 Y中的元素，将
原始信源的符号 x 变换为相应的码字符号,所以编码器
输出端的符号集为
Y 称为 码字, k 为码字 Y 的码元个数，称为码字 的码字
长度简称 码长 。
12{,,...,}qS S S S?
12{,,..,,}rX x x x?
12,{,,...,}qC W W W
iS i
w
{x1,x2…xn}
Y=(Y1,Y2,.Yk)
{y1,y2….ym}
§ 3.2码的分类 -1
1,二元码：
码符号集 X={0,1}，如果要将信源通过二元信道传输，必
须将信源编成二元码，这也是最常用的一种码。
2,等长码：
若一组码中所有码字的长度都相同，称为等长码。
3,变长码：
若一组码中所有码字的长度各不相同，称为变长码。
4,非奇异码：
若一组码中所有码字都不相同，称为非奇异码。
§ 3.2码的分类 -2
5,奇异码：
若一组码中有相同的码字，称为奇异码。
6,唯一可译码：
若码的任意一串有限长的码符号序列只能被唯一的译成
所对应的信源符号序列，则称此码为 唯一可译码 。
最佳码
?唯一可译码的一类
?其平均码长小于其他唯一可译码的平均长度
12,{ (,.,) }i i i iNB B W W W?
§ 3.2码的分类
例 1.唯一可译变长码与及时码
信源符号 出现概率 码 1 码 2 码 3 码 4
x1
x2
x3
x4
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，即可译作 x4x3x1,也可译作
x4x1X3,x1x2x3或 x1x2x1x1；码 3和码 4都是唯一可译的。
但码 3和码 4也不太一样，码 4称作逗点码，只要收到 1，
就可以立即作出译码；而码 3不同，当受到一个或几个码
是，必须参考后面的码才能作出判断。
定义,在唯一可译码中，有一类码，它在译码是无须参
考后面的码字就可以作出判断，这种码称为 即时码 。
7.即时码
即时码的树图构造法
我们可以用树图的形式构造即时码，如
0 1
0
0
1
1
1
1
01
001
0001
码 4的树图
1 0
1
1
0
0
0
0
10
100
1000
码 3的树图
树根 —— 码字的起点
树枝数 —— 码的数
节点数 —— 码字的一部分
节数 —— 码长
端点 —— 码字
满树 —— 等长码
非满树 —— 变长码
克拉夫特（ Kraft）不等式
定理 对于码符号为 的任意唯一可译码，
所对应的码长为,则必定满足：
12{,,...,}qX x x x?
12,,...,qk k k
1
1i
q
k
i
r ?
?
??
反之，若码长满足上式，则一定存在这样的唯一可译
码。
所有的码
非奇异码
唯一可译码
即时码
§ 3.3定长编码定理－ 1-描述
定长 （ 等长 ） 码信源编码定理：
对离散, 无记忆, 平稳, 遍历信源其符号序列,X=(X1,X2 …,.XL)，
可用 KL个符号 Y=(Y1,Y2…,YkL)进行等长编码, 对任意 ε>0,δ>0，
只要满足,(KL/L)logm≥HL(X)+ε
则：当 L足够大时, 可使译码差错小于 δ，
反之, 当 (KL/L)logm≤H(X)-2ε 时, 译码一定出错 。
解释：定长编码定理给出了信源进行等长编码所需码长的理论极限
值 。
§ 3.3定长编码定理－ 2－ AEP物
理意义
任何一个离散随机序列信源当序列长度Ｌ → ∝ 时,信源序列会产
生两极分化,大概率事件集合 与小概率事件集合,即 nL= ∪
对于 有性质,
①
②
(信源熵 ) (大概率事件熵 )
③ (等概率 )
对于 有性质,
由此可见, 信源编码只需对信源中 少数 落入典型大概率事件的集合的符号进
行编码即可 。 而对 大多数 属于非典型小概率事件集合中的信源符号无需
编码,且 。
?A ?A?A ?A
?A
1)A(pL imL ????
' ' '1 2 1 2(,,) ( )k MnH P P P H P P P
??
???? ? M/1PP M1 ?
?A
0)A(pL imL ????
0)( ??AP
信源序列集合
?A
?A
LS
§ 3.3定长编码定理－ 3- 证明
定长编码定理证明思路：
? 将取自 X，长为 L的信源符号序列分为集合 和
? 只对集合 中的序列进行一一对应的等长编码
? 此时的误差为,计算误差
? 可见当,且 (K/L)log m≥H(X)+ε 时，
几个概念：
? 编码信息率,（编码 后 平均 每个信源符号 能载荷的 最大 信息率）
? 编码效率：
（编码 前后 平均每个信源符号能载荷的最大信息率之比）
?A?A
?A
)( ?APPE ? ???? LAPAP 2)(1)( ???
0?EP??L
' lo gLKLRm?
'
()LHX
R? ?
§ 3.3定长编码定理－ 4-物理意义
结论：
? 只要码字传输的信息量大于信源序列携带的信息量，总可以实现几
乎无失真编码
(K/L)log m≥H(X)+ε ()
lo gLLK H XLm??
二元码时,m＝ 2：
()'
()
( ) ( )LL
L
KK
LL
K HX
L H X
H X H X
R ?
?
? ?
? ? ? ? ?
? ? ? ?
?最佳等长码时：
§ 3.3定长编码定理－ 5-举例
例 2：设有一简单离散信源,L=1,n=2
对其进行近似于无失真的等长编码, 若要求其编码效率为 96%,差错率低于
10-5,试求符号联合编码长度 L=？
解：
由编码效率：
即：
再由,
可见,需要 4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的,
一般来说：当 L有限时，高传输效率的等长码往往要引入一定的失真和错误，
它不能象变长编码那样可以实现真正的无失真编码
信源符号）/(811.0lo g)( 2
1
b i tppSH
i
ii ??? ?
?
%96)( )( ???SH SH
034.096.096.0811.0811.0 ????? ??
7522 222 101.410)034.0( 4 7 1 5.0 ??????? ?
?? ???? PLLP
222
()
1
2l o g [ ( ) ] 0,4 7 1 5ii
i
p p H S?
?
? ? ??
???????????????
41
2
4
3
1 ss
p
S
§ 3.4变长编码定理 -1
问题：
? 对于已知信源 X可用码符号 Y进行变长编码，而且对同一信源编成同
一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从
高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的
码字，就是用码长作为选择 准则 。
引入：码的 平均长度 。
离散无记忆平稳信源
信源平均符号熵 码字母表个数为 M，
则码字的平均码长,单个信源符号的平均码长：
1
1
in
in
x x xX
p p pP
???? ?
?????? ??
()LHX
1
()
M
L i i
i
K k p x
?
? ?
LKK
L?
§ 3.4变长信源编码 -2（ 几种类型的信源编码
举例）
信源 概率 pi 编码 Ⅰ 编码
Ⅱ
编码
Ⅲ
编码
Ⅳ
编码
Ⅴ
U1 1/2 00 0 0 0 0
U2 1/4 01 0 1 10 01
U3 1/8 10 1 00 110 011
U4 1/8 11 10 11 111 0111
编码
Ⅰ 唯一可译等长
编码
Ⅱ
奇异
编码
Ⅲ
非奇异
编码
Ⅳ
前缀
编码
Ⅴ 唯一可译不等长
§ 3.4变长编码定理 -3
无失真变长信源编码定理 (即香农第一定理 ),
? 离散无记忆平稳信源 X，其熵为,并有码符号
X={x1,…,xm}。对信源 X进行编码,总可以找到一种编码
方法，构成惟一可译码，使信源 X中 每个信源符号 所需
的平均码长满足,
另一方面,必可以找到前缀码，使其平均码长满足
()LHX
()
lo gL
HXL
mk ?
()
l o g 1
LHXL
mk ??
§ 3.4变长编码定理 -4－ 编码效率
变长码编码效率,?衡量各种编码方法的优略，判断是
否最佳码 。
编码前平均每个信源符号携带的信息量为：
编码后平均每个信源符号携带的最大的信息量为：
定义变长码编码效率为：
mk log
()
lo g
LHX
km? ?
()LHX
§ 3.4变长编码定理－ 输出信息
率－ 5
输出信息率：
R表示每个码元携带的信息量。
若传输一个码符号平均需要 t秒钟，则编码后信道
每秒钟传输的信息量为
()LHX
KR ?
/ /
/
比 特 信 源 符 号单 位 ＝ ＝ 比 特 码 符 号
码 符 号 信 源 符 号
t
R
R
t
?
tR
比较：
定长编码的编码效率：
变长编码的编码效率：
注意到,是指每个信源符号所需的平均码长，而 也
是平均到每个信源符号的码长，所以它们是一致的，
均表示无失真信源编码的效率。
'
( ) ( )
l o g
LL
K L
L
H X H X
R m? ??
()
lo g
LHX
km? ?
K LKL
§ 3.4变长编码定理 -
定长编码与变长编码效率比较：
相比,同一个信源，当要求编码效率达到 96％时，
等长码需要 4100万个信源符号联合编码；
变长码只需 2个符号（二次扩展信源）联合编码；
结论,采用变长编码,L不需要很大就可以达到相当高的
编码效率，而且可以实现无失真编码。且随着 L的增大，
编码效率越来越接近于 1。
§ 3,5实用的无失真信源编码方法举
例－ 1
（ huffman编码）
编码方法：
例 1,=
消息 U 概率 pi 编码 C
U1 1/2 0
1
U2 1/4 10
1/2
U3 1/8 110
1/4
U4 1/8 111
??????pis ??
?
?
?
?
?
?
?
?
?
?
8/18/14/12/1
4321 ssss
0
0
0
1 1
1
§ 3,5实用的无失真信源编码方法举
例－ 2（ huffman编码）
编码规则：
1)将信源消息 U按概率大小排序 （ 由大至小 ） 。
2)从最小两个概率开始编码, 并赋予一定规则, 如下支路小概率为
,1”,上支路大概率为, 0”。 若两支路概率相等, 仍为下支为
,1”上支为, 0”。
3) 将已编码两支路概率合并, 重新排队, 编码 。
4) 重复步骤 3） 直至合并概率归一时为止 。
5) 从概率归一端沿树图路线逆行至对应消息编码, 如 U3为, 110”。
§ 3,5实用的无失真信源编码方法举
例－ 3
（ huffman编码）
例 2：
§ 3,5实用的无失真信源编码方法举
例－ 4
（ huffman编码）
特点：
? 编码不是唯一的
? 保证了概率大的符号对应于短码，概率小的符号对应于长码，
而且短码得到充分利用
? 每次缩减信源的最后二个码字总是最后一位码元不同，前面
各位码元相同（二元码情况）
? 每次缩减信源的最长两个码字具有相同码长
这三个特点保证了所得到 huffman码一定是最佳码
§ 3,5实用的无失真信源编码方
法举例 — 香农编码 -1
? 设离散无记忆信源
? 二进制香农码的编码步骤如下：
? 将信源符号按概率从大到小的顺序排列，为方便起见，令
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 ?
???? ????
???? ?? ?
例 有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如下表所示。
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,5实用的无失真信源编码
方法举例 — 香农编码 -2
二 进制香农编码
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
? 计算出给定信源香农码的平均码长
? 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3
个比特表示。相比较，香农编码对信源进行了压缩。
? 由离散无记忆信源熵定义，可计算出：
? 对上述信源采用香农编码的信息率为
? 编码效率为信源熵和信息率之比。则
? 可以看出，编码效率并不是很高。
1 0, 2 5 2 2 ( 0, 2 0, 1 5 ) 3 0, 1 0 4 0, 0 5 5 2, 7 ( / )K ? ? ? ? ? ? ? ? ? ? ? 比 特 符 号
1 22 2.7' l og l og 2 2.7 1,21KR m L mL? ? ? ? ?这 里
'
( ) 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?? ? ?? 比 特 符 号
§ 3,5实用的无失真信源编码
方法举例 — 香农编码－ 5
§ 3,5实用的无失真信源编
码方法举例 — 费诺编码－ 1
费诺编码也是一种常见的信源编码方法。
编码步骤如下：
将概率按从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
按编码进制数将概率分组，使每组概率尽可能接近或相等。如
编二进制码就分成两组，编 m进制码就分成 m组。
给每一组分配一位码元。
将每一分组再按同样原则划分，重复步骤 2和 3，直至概率不再
可分为止。
§ 3,5实用的无失真信源编码
方法举例 — 费诺编码－ 1
例 设有一单符号离散信源
对该信源编二进制费诺码。编码过程如下表。
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
? ? ? ?? ????
? ? ? ?
§ 3,5实用的无失真信源编码
方法举例 — 费诺编码－ 2
二进制费诺编码
信源符号 概率 编码 码字 码长
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
§ 3,5实用的无失真信源编码方
法举例 — 费诺编码－ 3
该信源的熵为
平均码长为
编码效率为
本例中费诺编码有较高的编码效率。费诺码比较适合于
每次分组概率都很接近 的信源。特别是对每次 分组概率
都相等 的信源进行编码时，可达到理想的编码效率。
6
2
1
( ) ( ) l o g ( ) 2,3 5 ( / )ii
i
H X p x p x
?
? ? ?? 比 特 符 号
6
1
( ) 2.4( / )L i i
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? ? ? ? ? ? ?这 里
作业：
2006-3-30
P48,3-1（ 1,2问不做，但是要会判
断）
3-2
3-8
3-10
无失真编码概述
定长信源编码
变长信源编码
实用的无失真信源编码方法举
例
§ 3.1无失真编码概述 -1
通信中信息传输所要解决的基本问题是：
有效性和可靠性
? 在不失真或允许一定失真条件下，如何用尽
可能烧得符号来传送信源信息以提高信息传
输率－－－信源编码
? 在信道受干扰情况下，如何增加信号的抗干
扰能力同时又使得信息传输率最大 —— 信道
编码
§ 3.1无失真编码概述 -2
离散, 无失真, 无记忆信源编码的一般模型：
总码组合数：总组合数：
Ln Km
入 出
信源
编码X={x1,x2…xn}
Y=(Y1,Y2,.Yk)
Y∈ {y1,y2….ym}
§ 3.1无失真编码概述 -3
问题,能否进行无失真编码, 怎样进行无失真编码
若：不考虑信源统计特性：
应满足条件, 相互矛盾！
??
?
?
?
?
?
KL
L
mn
n
有效：
无失真,Km
l o g
l o g
LK LK nnm
Lm? ? ?
由
? 结论, ① 当 n = m 时, K≥L不有效 。
② 当 K = L 时, m≥n,亦不满足有效性
? 解决办法, 引入信源统计特性 。
§ 3.1无失真编码概述 -4
考察无失真条件,
分别表示等概条件下的消息熵 与码字熵 之比，
考虑信源的实际统计特性（非等概），实际消息熵为：
代入无失真条件得：
此时：即使 m=n,只要 就有可能实现 KL<L。
即无失真与有效性同时满足 。
具体实现 时,定长与变长编码
l o g
l o gL
KL LK nnm
Lm? ? ?
( ) l o gii
i
H X p p?? ?
()lo gLK HXLm?
lo g ( )m H X?
H(X)=logn H(Y)=logm
编码器可以看作这样一个系统，它的输入端为原始信
源 X，其符号集为 ；而信道所能传输的符号集
为 编码器的功能是用符号集 Y中的元素，将
原始信源的符号 x 变换为相应的码字符号,所以编码器
输出端的符号集为
Y 称为 码字, k 为码字 Y 的码元个数，称为码字 的码字
长度简称 码长 。
12{,,...,}qS S S S?
12{,,..,,}rX x x x?
12,{,,...,}qC W W W
iS i
w
{x1,x2…xn}
Y=(Y1,Y2,.Yk)
{y1,y2….ym}
§ 3.2码的分类 -1
1,二元码：
码符号集 X={0,1}，如果要将信源通过二元信道传输，必
须将信源编成二元码，这也是最常用的一种码。
2,等长码：
若一组码中所有码字的长度都相同，称为等长码。
3,变长码：
若一组码中所有码字的长度各不相同，称为变长码。
4,非奇异码：
若一组码中所有码字都不相同，称为非奇异码。
§ 3.2码的分类 -2
5,奇异码：
若一组码中有相同的码字，称为奇异码。
6,唯一可译码：
若码的任意一串有限长的码符号序列只能被唯一的译成
所对应的信源符号序列，则称此码为 唯一可译码 。
最佳码
?唯一可译码的一类
?其平均码长小于其他唯一可译码的平均长度
12,{ (,.,) }i i i iNB B W W W?
§ 3.2码的分类
例 1.唯一可译变长码与及时码
信源符号 出现概率 码 1 码 2 码 3 码 4
x1
x2
x3
x4
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，即可译作 x4x3x1,也可译作
x4x1X3,x1x2x3或 x1x2x1x1；码 3和码 4都是唯一可译的。
但码 3和码 4也不太一样，码 4称作逗点码，只要收到 1，
就可以立即作出译码；而码 3不同，当受到一个或几个码
是，必须参考后面的码才能作出判断。
定义,在唯一可译码中，有一类码，它在译码是无须参
考后面的码字就可以作出判断，这种码称为 即时码 。
7.即时码
即时码的树图构造法
我们可以用树图的形式构造即时码，如
0 1
0
0
1
1
1
1
01
001
0001
码 4的树图
1 0
1
1
0
0
0
0
10
100
1000
码 3的树图
树根 —— 码字的起点
树枝数 —— 码的数
节点数 —— 码字的一部分
节数 —— 码长
端点 —— 码字
满树 —— 等长码
非满树 —— 变长码
克拉夫特（ Kraft）不等式
定理 对于码符号为 的任意唯一可译码，
所对应的码长为,则必定满足：
12{,,...,}qX x x x?
12,,...,qk k k
1
1i
q
k
i
r ?
?
??
反之，若码长满足上式，则一定存在这样的唯一可译
码。
所有的码
非奇异码
唯一可译码
即时码
§ 3.3定长编码定理－ 1-描述
定长 （ 等长 ） 码信源编码定理：
对离散, 无记忆, 平稳, 遍历信源其符号序列,X=(X1,X2 …,.XL)，
可用 KL个符号 Y=(Y1,Y2…,YkL)进行等长编码, 对任意 ε>0,δ>0，
只要满足,(KL/L)logm≥HL(X)+ε
则：当 L足够大时, 可使译码差错小于 δ，
反之, 当 (KL/L)logm≤H(X)-2ε 时, 译码一定出错 。
解释：定长编码定理给出了信源进行等长编码所需码长的理论极限
值 。
§ 3.3定长编码定理－ 2－ AEP物
理意义
任何一个离散随机序列信源当序列长度Ｌ → ∝ 时,信源序列会产
生两极分化,大概率事件集合 与小概率事件集合,即 nL= ∪
对于 有性质,
①
②
(信源熵 ) (大概率事件熵 )
③ (等概率 )
对于 有性质,
由此可见, 信源编码只需对信源中 少数 落入典型大概率事件的集合的符号进
行编码即可 。 而对 大多数 属于非典型小概率事件集合中的信源符号无需
编码,且 。
?A ?A?A ?A
?A
1)A(pL imL ????
' ' '1 2 1 2(,,) ( )k MnH P P P H P P P
??
???? ? M/1PP M1 ?
?A
0)A(pL imL ????
0)( ??AP
信源序列集合
?A
?A
LS
§ 3.3定长编码定理－ 3- 证明
定长编码定理证明思路：
? 将取自 X，长为 L的信源符号序列分为集合 和
? 只对集合 中的序列进行一一对应的等长编码
? 此时的误差为,计算误差
? 可见当,且 (K/L)log m≥H(X)+ε 时，
几个概念：
? 编码信息率,（编码 后 平均 每个信源符号 能载荷的 最大 信息率）
? 编码效率：
（编码 前后 平均每个信源符号能载荷的最大信息率之比）
?A?A
?A
)( ?APPE ? ???? LAPAP 2)(1)( ???
0?EP??L
' lo gLKLRm?
'
()LHX
R? ?
§ 3.3定长编码定理－ 4-物理意义
结论：
? 只要码字传输的信息量大于信源序列携带的信息量，总可以实现几
乎无失真编码
(K/L)log m≥H(X)+ε ()
lo gLLK H XLm??
二元码时,m＝ 2：
()'
()
( ) ( )LL
L
KK
LL
K HX
L H X
H X H X
R ?
?
? ?
? ? ? ? ?
? ? ? ?
?最佳等长码时：
§ 3.3定长编码定理－ 5-举例
例 2：设有一简单离散信源,L=1,n=2
对其进行近似于无失真的等长编码, 若要求其编码效率为 96%,差错率低于
10-5,试求符号联合编码长度 L=？
解：
由编码效率：
即：
再由,
可见,需要 4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的,
一般来说：当 L有限时，高传输效率的等长码往往要引入一定的失真和错误，
它不能象变长编码那样可以实现真正的无失真编码
信源符号）/(811.0lo g)( 2
1
b i tppSH
i
ii ??? ?
?
%96)( )( ???SH SH
034.096.096.0811.0811.0 ????? ??
7522 222 101.410)034.0( 4 7 1 5.0 ??????? ?
?? ???? PLLP
222
()
1
2l o g [ ( ) ] 0,4 7 1 5ii
i
p p H S?
?
? ? ??
???????????????
41
2
4
3
1 ss
p
S
§ 3.4变长编码定理 -1
问题：
? 对于已知信源 X可用码符号 Y进行变长编码，而且对同一信源编成同
一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从
高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的
码字，就是用码长作为选择 准则 。
引入：码的 平均长度 。
离散无记忆平稳信源
信源平均符号熵 码字母表个数为 M，
则码字的平均码长,单个信源符号的平均码长：
1
1
in
in
x x xX
p p pP
???? ?
?????? ??
()LHX
1
()
M
L i i
i
K k p x
?
? ?
LKK
L?
§ 3.4变长信源编码 -2（ 几种类型的信源编码
举例）
信源 概率 pi 编码 Ⅰ 编码
Ⅱ
编码
Ⅲ
编码
Ⅳ
编码
Ⅴ
U1 1/2 00 0 0 0 0
U2 1/4 01 0 1 10 01
U3 1/8 10 1 00 110 011
U4 1/8 11 10 11 111 0111
编码
Ⅰ 唯一可译等长
编码
Ⅱ
奇异
编码
Ⅲ
非奇异
编码
Ⅳ
前缀
编码
Ⅴ 唯一可译不等长
§ 3.4变长编码定理 -3
无失真变长信源编码定理 (即香农第一定理 ),
? 离散无记忆平稳信源 X，其熵为,并有码符号
X={x1,…,xm}。对信源 X进行编码,总可以找到一种编码
方法，构成惟一可译码，使信源 X中 每个信源符号 所需
的平均码长满足,
另一方面,必可以找到前缀码，使其平均码长满足
()LHX
()
lo gL
HXL
mk ?
()
l o g 1
LHXL
mk ??
§ 3.4变长编码定理 -4－ 编码效率
变长码编码效率,?衡量各种编码方法的优略，判断是
否最佳码 。
编码前平均每个信源符号携带的信息量为：
编码后平均每个信源符号携带的最大的信息量为：
定义变长码编码效率为：
mk log
()
lo g
LHX
km? ?
()LHX
§ 3.4变长编码定理－ 输出信息
率－ 5
输出信息率：
R表示每个码元携带的信息量。
若传输一个码符号平均需要 t秒钟，则编码后信道
每秒钟传输的信息量为
()LHX
KR ?
/ /
/
比 特 信 源 符 号单 位 ＝ ＝ 比 特 码 符 号
码 符 号 信 源 符 号
t
R
R
t
?
tR
比较：
定长编码的编码效率：
变长编码的编码效率：
注意到,是指每个信源符号所需的平均码长，而 也
是平均到每个信源符号的码长，所以它们是一致的，
均表示无失真信源编码的效率。
'
( ) ( )
l o g
LL
K L
L
H X H X
R m? ??
()
lo g
LHX
km? ?
K LKL
§ 3.4变长编码定理 -
定长编码与变长编码效率比较：
相比,同一个信源，当要求编码效率达到 96％时，
等长码需要 4100万个信源符号联合编码；
变长码只需 2个符号（二次扩展信源）联合编码；
结论,采用变长编码,L不需要很大就可以达到相当高的
编码效率，而且可以实现无失真编码。且随着 L的增大，
编码效率越来越接近于 1。
§ 3,5实用的无失真信源编码方法举
例－ 1
（ huffman编码）
编码方法：
例 1,=
消息 U 概率 pi 编码 C
U1 1/2 0
1
U2 1/4 10
1/2
U3 1/8 110
1/4
U4 1/8 111
??????pis ??
?
?
?
?
?
?
?
?
?
?
8/18/14/12/1
4321 ssss
0
0
0
1 1
1
§ 3,5实用的无失真信源编码方法举
例－ 2（ huffman编码）
编码规则：
1)将信源消息 U按概率大小排序 （ 由大至小 ） 。
2)从最小两个概率开始编码, 并赋予一定规则, 如下支路小概率为
,1”,上支路大概率为, 0”。 若两支路概率相等, 仍为下支为
,1”上支为, 0”。
3) 将已编码两支路概率合并, 重新排队, 编码 。
4) 重复步骤 3） 直至合并概率归一时为止 。
5) 从概率归一端沿树图路线逆行至对应消息编码, 如 U3为, 110”。
§ 3,5实用的无失真信源编码方法举
例－ 3
（ huffman编码）
例 2：
§ 3,5实用的无失真信源编码方法举
例－ 4
（ huffman编码）
特点：
? 编码不是唯一的
? 保证了概率大的符号对应于短码，概率小的符号对应于长码，
而且短码得到充分利用
? 每次缩减信源的最后二个码字总是最后一位码元不同，前面
各位码元相同（二元码情况）
? 每次缩减信源的最长两个码字具有相同码长
这三个特点保证了所得到 huffman码一定是最佳码
§ 3,5实用的无失真信源编码方
法举例 — 香农编码 -1
? 设离散无记忆信源
? 二进制香农码的编码步骤如下：
? 将信源符号按概率从大到小的顺序排列，为方便起见，令
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 ?
???? ????
???? ?? ?
例 有一单符号离散无记忆信源
对该信源编二进制香农码。其编码过程如下表所示。
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,5实用的无失真信源编码
方法举例 — 香农编码 -2
二 进制香农编码
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
? 计算出给定信源香农码的平均码长
? 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3
个比特表示。相比较，香农编码对信源进行了压缩。
? 由离散无记忆信源熵定义，可计算出：
? 对上述信源采用香农编码的信息率为
? 编码效率为信源熵和信息率之比。则
? 可以看出，编码效率并不是很高。
1 0, 2 5 2 2 ( 0, 2 0, 1 5 ) 3 0, 1 0 4 0, 0 5 5 2, 7 ( / )K ? ? ? ? ? ? ? ? ? ? ? 比 特 符 号
1 22 2.7' l og l og 2 2.7 1,21KR m L mL? ? ? ? ?这 里
'
( ) 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?? ? ?? 比 特 符 号
§ 3,5实用的无失真信源编码
方法举例 — 香农编码－ 5
§ 3,5实用的无失真信源编
码方法举例 — 费诺编码－ 1
费诺编码也是一种常见的信源编码方法。
编码步骤如下：
将概率按从大到小的顺序排列，令
p(x1)≥ p(x2)≥…≥ p(xn)
按编码进制数将概率分组，使每组概率尽可能接近或相等。如
编二进制码就分成两组，编 m进制码就分成 m组。
给每一组分配一位码元。
将每一分组再按同样原则划分，重复步骤 2和 3，直至概率不再
可分为止。
§ 3,5实用的无失真信源编码
方法举例 — 费诺编码－ 1
例 设有一单符号离散信源
对该信源编二进制费诺码。编码过程如下表。
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
? ? ? ?? ????
? ? ? ?
§ 3,5实用的无失真信源编码
方法举例 — 费诺编码－ 2
二进制费诺编码
信源符号 概率 编码 码字 码长
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
§ 3,5实用的无失真信源编码方
法举例 — 费诺编码－ 3
该信源的熵为
平均码长为
编码效率为
本例中费诺编码有较高的编码效率。费诺码比较适合于
每次分组概率都很接近 的信源。特别是对每次 分组概率
都相等 的信源进行编码时，可达到理想的编码效率。
6
2
1
( ) ( ) l o g ( ) 2,3 5 ( / )ii
i
H X p x p x
?
? ? ?? 比 特 符 号
6
1
( ) 2.4( / )L i i
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? ? ? ? ? ? ?这 里
作业：
2006-3-30
P48,3-1（ 1,2问不做，但是要会判
断）
3-2
3-8
3-10
