第三章 信源编码（一）
离散信源无失真编码
? 3.1信源及其分类
? 3.2离散无记忆信源的等长编码
? 3.3离散无记忆信源的不等长编码
? 3.4最佳不等长编码
3.1 信源及其分类
信源及其分类
? 离散信源
? 连续信源
? 无记忆信源
? 有记忆信源
? 简单信源－独立同分布
? 平稳信源，各态历经源
? M阶记忆源
? 时间离散连续源
? 随机波形源
3.2 离散无记忆源的等长
编码
离散无记忆源
? 字母表 A={a1,…,a K},概率 p1,…,p K,长为 L的源输
出序列 uL={u1,…,uL}，共有 KL种序列
? 码符号字母表 B={b1,…,b D},以码符号表示源输
出序列,D元码
? 等长 D元码，不等长 D元码
? 单义可译码，每个消息都至少有一个码字与之
对应。
? 单义可译码存在充要条件 DN≥KL
N≥LlogK/logD
DMS的等长编码
? NlogD≥LH(U)
? H(U)是统计平均值,L达到无限时，一个具体
的源输出序列的平均每符号的信息量才等于
H(U)
? 选 L足够长，使 NlogD≥L[H(U)+eL]
弱、强 e典型序列集
})()(:{),( eee ????? UHIUHuLT LLU
)})(())((:{),( eee ????? kkkLU apLLapLuLT
信源划分定理
])([])([
])([])([
2|),(|2)1(
2)(2
1)},({
ee
ee
ee
ee
??
????
???
??
???
UHL
U
UHL
UHL
L
UHL
ULr
LT
uP
LTuP
编码速率和等长编码定理
? R=(1/L)logM=(N/L)logD,M为码字总数
? 对于给定信源和编码速率 R以及任意 e?0，若有
L0,以及编译码方法，使得 L>L0,错误概率小于 e，
R是可达的
? 等长编码定理
? R>H(U),R是可达的,R<H(U)是不可达的
? 编码效率 h?H(U)/R
3.3 DMS的不等长编码
平均码长
??
k
kk
napn )(
几个定义
? 唯一可译码
? 逗点码，无逗点码
? 字头或前缀
? 异字头码或异前缀码
? 树码，满树，非满树，全树
? 树码构造异字头码
例子
信源字
母集
概率 码 A 码 B 码 C 码 D
a1
a2
a3
a4
0.5
0.25
0.125
0.125
0
0
1
10
0
1
00
11
0
10
110
111
0
01
011
0111
Shannon－ Fano编码
? D元码
? 每次信源符号化为概率近似相等的 D个子集
? 这样可以保证 D个码元近似等概，每个码字承
载的信息量近似最大，码就近似最短。
? 理想情况 I(ak)=nklogD,p(ak)=D-nk
Kraft不等式
1
1
??
?
?
K
k
n k
D
不等长编码定理
1
lo g
)(
lo g
)(
???
D
UH
n
D
UH
LD
UH
n
D
UH 1
lo g
)(
lo g
)(
???
3.4最佳不等长编码
两个定理
1.对于给定信源，存在最佳唯一二元可译码，最
小概率的两个码字码长相等且最长，他们之间
仅最后一位不同
2,对辅助集为最佳的码，对原始集也是最佳的
Huffman编码
? 例 (0.20,0.19,0.18,0.17,0.15,0.10,0.01)
第三章结束
离散信源无失真编码
? 3.1信源及其分类
? 3.2离散无记忆信源的等长编码
? 3.3离散无记忆信源的不等长编码
? 3.4最佳不等长编码
3.1 信源及其分类
信源及其分类
? 离散信源
? 连续信源
? 无记忆信源
? 有记忆信源
? 简单信源－独立同分布
? 平稳信源，各态历经源
? M阶记忆源
? 时间离散连续源
? 随机波形源
3.2 离散无记忆源的等长
编码
离散无记忆源
? 字母表 A={a1,…,a K},概率 p1,…,p K,长为 L的源输
出序列 uL={u1,…,uL}，共有 KL种序列
? 码符号字母表 B={b1,…,b D},以码符号表示源输
出序列,D元码
? 等长 D元码，不等长 D元码
? 单义可译码，每个消息都至少有一个码字与之
对应。
? 单义可译码存在充要条件 DN≥KL
N≥LlogK/logD
DMS的等长编码
? NlogD≥LH(U)
? H(U)是统计平均值,L达到无限时，一个具体
的源输出序列的平均每符号的信息量才等于
H(U)
? 选 L足够长，使 NlogD≥L[H(U)+eL]
弱、强 e典型序列集
})()(:{),( eee ????? UHIUHuLT LLU
)})(())((:{),( eee ????? kkkLU apLLapLuLT
信源划分定理
])([])([
])([])([
2|),(|2)1(
2)(2
1)},({
ee
ee
ee
ee
??
????
???
??
???
UHL
U
UHL
UHL
L
UHL
ULr
LT
uP
LTuP
编码速率和等长编码定理
? R=(1/L)logM=(N/L)logD,M为码字总数
? 对于给定信源和编码速率 R以及任意 e?0，若有
L0,以及编译码方法，使得 L>L0,错误概率小于 e，
R是可达的
? 等长编码定理
? R>H(U),R是可达的,R<H(U)是不可达的
? 编码效率 h?H(U)/R
3.3 DMS的不等长编码
平均码长
??
k
kk
napn )(
几个定义
? 唯一可译码
? 逗点码，无逗点码
? 字头或前缀
? 异字头码或异前缀码
? 树码，满树，非满树，全树
? 树码构造异字头码
例子
信源字
母集
概率 码 A 码 B 码 C 码 D
a1
a2
a3
a4
0.5
0.25
0.125
0.125
0
0
1
10
0
1
00
11
0
10
110
111
0
01
011
0111
Shannon－ Fano编码
? D元码
? 每次信源符号化为概率近似相等的 D个子集
? 这样可以保证 D个码元近似等概，每个码字承
载的信息量近似最大，码就近似最短。
? 理想情况 I(ak)=nklogD,p(ak)=D-nk
Kraft不等式
1
1
??
?
?
K
k
n k
D
不等长编码定理
1
lo g
)(
lo g
)(
???
D
UH
n
D
UH
LD
UH
n
D
UH 1
lo g
)(
lo g
)(
???
3.4最佳不等长编码
两个定理
1.对于给定信源，存在最佳唯一二元可译码，最
小概率的两个码字码长相等且最长，他们之间
仅最后一位不同
2,对辅助集为最佳的码，对原始集也是最佳的
Huffman编码
? 例 (0.20,0.19,0.18,0.17,0.15,0.10,0.01)
第三章结束
