第四章：无失真信源编码杨杰无失真信源编码无失真编码概述定长信源编码变长信源编码实用的无失真信源编码方法举例
§ 4.1无失真编码概述－ 1
离散,无失真,无记忆信源编码的一般模型：
总码组合数：
)( 1 LSSS )( 1 KCCC
总组合数：
Ln Km
入 出信源编码
§ 4.1无失真编码概述－ 2
问题,能否进行无失真编码,怎样进行无失真编码若：不考虑信源统计特性：
应满足条件,相互矛盾！
KL
L
mn
n
有效：
无失真,Km
m
n
L
Kmn KL
lo g
lo g由
结论,① 当 n = m 时,K≥L 不有效 。
② 当 K = L 时,m≥n,亦不满足有效性
解决办法,引入信源统计特性 。
§ 4.1无失真编码概述－ 3
考察无失真条件,
分别表示等概条件下的消息熵 与码字熵 之比，
考虑信源的实际统计特性（非等概），实际消息熵为：
代入无失真条件得：
此时：即使 m=n,只要 就有可能实现 K<L。
即无失真与有效性同时满足 。
具体实现 时,定长与变长编码
m
n
L
Kmn KL
lo g
lo g
mnloglog nSH log)(? mCH lo g)(?
i ii ppSH lo g)(
mSHLK log )(?
)(lo g SHm?
定长编码定理
描述
证明
物理意义
实际应用中的问题
§ 4.2定长编码定理－ 1
渐进等分割性
– 描述
– 证明
– 物理意义
– 应用
§ 4.2定长编码定理－ 2-描述定长 （ 等长 ） 码信源编码定理：
对离散,无记忆,平稳,遍历信源其符号序列,S =(S1,S2 …,.SL)，
可用 K个符号 C=(C1,C2…,Ck) 进行等长编码,对任意 ε>0,δ>0，
只要满足,(K/L)log m≥H(S)+ε
则：当 L足够大时,可使译码差错小于 δ，
反之,当 (K/L)log m≤H(S)-2ε 时,译码一定出错 。
解释：定长编码定理给出了信源进行等长编码所需码长的理论极限值 。
§ 4.2定长编码定理－ 2-进一步理解若要求变得的等长码是唯一可译的，则必须：
若 L＝ 1，则：
结论,对于唯一可译码，每个信源符号至少需要用 个码符号来变换。
当采用二元码编码时,m＝ 2，则：
结论,对信源进行二元等长编码时，每个信源符号所需码长的极限值为
m
n
L
Kmn KL
lo g
lo g
m
n
log
log
m
nK
lo g
lo g?
)(lo glo g 1 b itnKnLK L
)(log bitn
例 1：英文电报有 32个符号（ 26＋ 6），即 n=32，
若 m=2,L＝ 1（即对信源的逐个符号进行二元编码），
则：
解释,每个英文电报符号至少需要用 5位二元符号编码问题,第三章：在考虑符号出现的概率和符号间相关性前提下,每个英文符号平均携带的信息量是 1.4bit/符号（ ）,<<5bit/符号，
等长编码效率极低，如何提高效率？如何体现有效性？
532lo glo g nK Bit/符号
bitH 4.1
解决方法：
考察,字母个数为 n，字母出现非等概，且字母之间相关长度为 L的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着 L的增加，这种无意义序列的总数越来越大。
方法,进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 <<,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。
问题,会引入一定的误差，当 L足够长后，误差可以任意小。
Ln
Ln
§ 4.2定长编码定理－ 3－证明考察离散、随机序列信源的统计特性
－－渐进等分割性（ AEP）
AEP描述：
渐进等分割定理,（熵定理，遍历性定理）
设 是离散无记忆信源输出的一个特定序列，
则任给 和,总可以找到一个整数,使当时，有：
Nssss,..21?
0 0 0N
0NN?
1}|)({| )(l o g SHP N sP
引入：渐进等分割性（ AEP）
§ 4.2定长编码定理 － 4－ AEP物理意义任何一个离散随机序列信源当序列长度Ｌ → ∝ 时,信源序列会产生两极分化,大概率事件集合 与小概率事件集合,即 nL= ∪
对于 有性质,
①
②
(信源熵 ) (大概率事件熵 )
③ (等概率 )
对于 有性质,
由此可见,信源编码只需对信源中 少数 落入典型大概率事件的集合的符号进行编码即可 。 而对 大多数 属于非典型小概率事件集合中的信源符号无需编码,且 。
A?A?A?A
A
1)A(pL imL
)PP(H)P,P,P(H M2'n'2'1 k
M/1PP M1?
A
0)A(pL imL
0)(AP
信源序列集合
A
A
LS
§ 4.2定长编码定理－ 5 － AEP证明集合 和 中的序列分别称为 典型序列和 非典型序列可以证明：对于任意小的正数,,当 L足够大时，
表示 中所有 典型序列的集合表示 集合中序列的 个数还可以证明：对于任意小的正数,,当 L足够大时，
表示序列 出现的 概率由切比雪夫不等式可得：
表示 S中每个符号携带的信息量的方差
A?
A
00
])([])([ 2||||2)1( SHLSHL A
A?
||||?A
LS
A
0 Ai?
])([])([ 2)(2 SHLiSHL P )(
iP? i
LAP
21)(
2?
AEP结论：当 L足够大时，
所有 典型序列出现的概率近似相等，即 典型序列为 渐进等概 序列
可粗略认为 典型序列出现的概率为
所有 典型序列的概率和接近为 1，即
AEP应用：
提出、证明都是基于离散无记忆序列信源
平稳遍历信源有类似结果
体现信源统计特性
用以证明定长编码定理
1)(Ap
)(2 SLH?
§ 4.2定长编码定理－ 5 － 证明定长编码定理证明思路：
将取自 S，长为 L的信源符号序列分为集合 和
只对集合 中的序列进行一一对应的等长编码
此时的误差为,计算误差
可见当,且 (K/L)log m≥H(S)+ε时，
几个概念：
编码信息率,（编码 后 平均 每个信源符号 能载荷的 最大 信息率）
编码效率：
（编码 前后 平均每个信源符号能载荷的最大信息率之比）
A?
A
A
)(?APPE LAPAP 2)(1)(
0?EPL
mR LK lo g?
RSH )(
§ 4.2定长编码定理 － 6（ 物理意义）
结论：
可推广至离散、非平稳无记忆信源和有记忆信源情况
只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码
(K/L)log m≥H(S)+ε
mSHLK l o g )(
二元码时,m＝ 2：
)(
)(
)()(
SH
SH
L
K
L
K
L
K
R
SHSH
最佳等长码时：
§ 4.2定长编码定理 － 7（ 实际应用问题）
编译码同步问题
问题：如何使译码端知道码字起点
解决办法,1、每个码字加短同步前缀
2、每若干码字加较长同步前缀分组长度与编译码复杂性、编译码延时等等关系
问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加
解决办法：目前没有理想到解决办法定长信源编码的 理论意义 远大于其 实用价值
§ 4.2定长编码定理 － 8（ 举例 )
例 2：设有一简单离散信源,L=1,n=2
对其进行近似于无失真的等长编码,若要求其编码效率为 96%,差错率低于
10-5,试求符号联合编码长度 L=？
解：
由编码效率：
即：
再由,
可见,需要 4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的,
一般来说：当 L有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码信源符号）/(811.0lo g)( 2
1
b itppSH
i
ii
%96)( )(SH SH
034.096.096.0811.0811.0
7522 222 101.410)034.0( 4 7 1 5.0
PLLP
4 7 1 5.0)]([lo g 22
1
)(2 2
SHpp
i
ii?
41
2
4
3
1 ss
p
S
§ 4.3变长信源编码 -1
几个码类的概念
非奇异码（奇异码、单义码）
唯一可译码
前缀码（即时码、非延长码、异前置码）
最佳码（紧致码）
Kraft定理唯一可译码存在定理变长编码定理（香农第一定理）
§ 4.3变长信源编码 -2(几个码类的概念 )
非奇异码：
每一个码字仅对应信源中的一个信源符号（序列）。
编码是单义的。
反之为奇异码或非单义码。
§ 4.3变长信源编码 -3(几个码类的概念 )
唯一可译码
编码单义、译码单义
对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。
§ 4.3变长信源编码 -4(几个码类的概念 )
前缀码
是一类唯一可译码
在一个变长码中，没有任何一个码字是其他码字的前缀。
译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。
又称即时码、非延时码
§ 4.3变长信源编码 -5(几个码类的概念 )
最佳码
唯一可译码的一类
其平均码长小于其他唯一可译码的平均长度所有的码非奇异码唯一可译码前缀码
§ 4.3变长信源编码 -6（ 几种类型的信源编码 举例）
例 3：
信源 概率 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
编码 Ⅰ 唯一可译等长编码 Ⅱ 奇异编码 Ⅲ 非奇异编码 Ⅳ 前缀编码 Ⅴ 唯一可译不等长
§ 4.3变长信源编码 -7(Kraft定理 )
引出码树
Kraft定理描述
Kraft定理证明－略
§ 4.3变长信源编码 -8(Kraft定理引出 )
问题,寻求 实时唯一可译码方法：研究实时唯一可译码的码字可分离条件引入：,码树,概念（直观）
结论：通过 Kraft定理给出 实时唯一可译码（ 前缀码）存在的条件码树－－ 变长码的树图表示将变长码与码树建立,一一对应,关系：
树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码
§ 4.3变长信源编码 -9(Kraft定理 )
问题：
比较简单信源，码树方法可直接且直观构造前缀码
较复杂信源，直接画码树复杂且困难解决方法：
为分析起来特别对含有很多符号种类的复杂信源更方便寻找一种与上述,树图,等效的解析式表达式 ----Kraft不等式 。
结论：
Kraft定理给出码字可分离或前缀码存在的充要条件
§ 4.3变长信源编码 -10(Kraft定理 )
定理：长度为 Ki（ i=1,2,…,n） 的 m （ 码字母表长度 ） 进制前缀码存在的充要条件为：
证明：略物理意义：
给定信源个数 N和码字数 M,只要允许码字长度可以足够长,就总可以满足 Kraft不等式,从而得到前缀码
1
1
n
i
k im
§ 4.3变长信源编码 -11(唯一可译码定理 )
Kraft不等式给出的限制也是所有唯一可译码都必须满足的。
定理描述：
任何唯一可译码均满足 Kraft不等式。
结论：
对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码
§ 4.3变长编码定理－ 12
问题：
对于已知信源 S可用码符号 X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择 准则 。
引入：码的 平均长度 。
离散无记忆平稳信源信源熵率为 码字母表个数为 M，
则前缀码平均码长：
ni
ni
ppp
sSsSsS
P
S
1
1
)(SH?
)(
1
i
M
i
i apkk?
§ 4.3变长编码定理－ 13
无失真变长信源编码定理 (即香农第一定理 ),
离散无记忆平稳信源 S，其熵率为,并有码符号
X={x1,…,xm}。对信源 S进行编码,总可以找到一种编码方法，
构成惟一可译码，使信源 S中 每个信源符号 所需的平均码长满足,
另一方面,必可以找到前缀码，使其平均码长满足
)(SH?
m
SHk
l o g
)(
1l o g )( mSHk
§ 4.3变长编码定理－ 14
定理证明－略物理意义：
又称 无噪信道编码定理
编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大
要做到无失真编码，变换每个信源符号平均所需最少的 m元码元数就是信源的熵率（以 m进制信息量单位测度）
信源的熵率是描述信源每个符号平均所需最少的比特数定理说明：
是存在性定理－－具有理论指导意义
是构造性定理－－设计出多种具体编码方法
§ 4.3变长编码定理－ 15－ 编码效率变长码编码效率,?衡量各种编码方法的优略，判断是否最佳码 。
编码前平均每个信源符号携带的信息量为：
编码后平均每个信源符号携带的最大的信息量为：
定义变长码编码效率为：
另一种理解：
最佳码（极限时） 每个信源符号 的平均码长为：
某一方法得到的 每个信源符号 的 平均码长为：
定义变长码编码效率为：
mklog
k
SH
mk
SH m )(
l o g
)(
)(SH?
)(l o g )( SHk mmSH
'k
''
)(
k
SH
k
k m
比较：
定长编码的编码效率：
变长编码的编码效率：
注意到,是指每个信源符号所需的平均码长，而 也是平均到每个信源符号的码长，所以它们是一致的，均表示无失真信源编码的效率。
K SLHmSHR SH mLK )(l o g )()(
k
SH
mk
SH m )(
l o g
)(
k LK
例 4,p160例 4.4
一离散无记忆信源
41
2
4
3
1 ss
p
S
其 熵 为,信源符号）比特 /(811.0l o g4l o g)( 344341SH
用二元符号（ 0,1； m=2）构造一个 前缀码,1,0 21 ss
此时 每个信源符号 平均码长 为,1?k
8 1 1.0)( k SH?编码效率 为：
为提高编码效率，对 S的 2次扩展信源进行 2维联合编码：
构造一个扩展信源 S2的前缀码：
前缀码
s1s2 9/16 0
s1s2 3/16 10
s1s2 3/16 110
s1s2 1/16 111
i? )( iP?
此时 平均码长 为：
16272?k
此时信源 S中每个符号对应的 平均码长 为：
32271627 2k
编码效率 为,961.0)(2
k SH?
同样可得,985.0)(3
k SH? 991.0)(4 k SH?
定长编码与变长编码效率比较：
例 4与例 2相比,同一个信源，当要求编码效率达到 96％时，
等长码需要 4100万个信源符号联合编码；
变长码只需 2个符号（二次扩展信源）联合编码；
结论,采用变长编码,L不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着 L的增大，编码效率越来越接近于 1。
§ 4.4实用的无失真信源编码方法举例－
1
（ huffman编码）
Huffman编码
编码方法
特点
应用
问题
§ 4.3实用的无失真信源编码方法举例－
2
（ huffman编码）
编码方法：
例?,=
消息 U 概率 pi 编码 C
U1 1/2 0 0
1 0
U2 1/4 0 10
1/21
U3 1/8 0 110
1/4 1
U4 1/8 1 111
pis
8/18/14/12/1
4321 ssss
§ 4.3实用的无失真信源编码方法举例－
3（ huffman编码）
编码规则：
1)将信源消息 U按概率大小排序 （ 由大至小 ） 。
2)从最小两个概率开始编码,并赋予一定规则,如下支路小概率为,1”,上支路大概率为,0”。 若两支路概率相等,仍为下支为,1”上支为,0”。
3) 将已编码两支路概率合并,重新排队,编码 。
4) 重复步骤 3） 直至合并概率归一时为止 。
5) 从概率归一端沿树图路线逆行至对应消息编码,如 U3为,110”。
§ 4.3实用的无失真信源编码方法举例－
4
（ huffman编码）
例 2：
§ 4.3实用的无失真信源编码方法举例－
5
（ huffman编码）
特点：
编码不是唯一的
保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用
每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元码情况）
每次缩减信源的最长两个码字具有相同码长这三个特点保证了所得到 huffman码一定是最佳码
§ 4.3实用的无失真信源编码方法举例－
6
（ huffman编码）
应用,
在不同领域得到广泛应用。
例,International digital facsimile coding standard(1980)US HDTV(1995)
问题：
误差扩散
速率匹配
要求了解信源的统计分布；
算法复杂度随着信源符号串长度的增加而迅速增长。
解决：
工程上克服误差扩散的方法有两种：一是限制哈夫曼码仅能应用于优质信道 （ <=10-6）
以限制扩散的可能性；二是采用定期清洗,防止扩散区域增大 。 但是它是靠牺牲有效性换取的 。
工程上解决速率匹配问题的方法是在两者之间加一个类似与水库的缓存器，它变速入，恒速出，以解决两者速率的匹配。
信源统计特性未知时可采用所谓通用编码的方法来解决
算法复杂度问题考虑采用算术编码方法解决。
§ 4.1无失真编码概述－ 1
离散,无失真,无记忆信源编码的一般模型：
总码组合数：
)( 1 LSSS )( 1 KCCC
总组合数：
Ln Km
入 出信源编码
§ 4.1无失真编码概述－ 2
问题,能否进行无失真编码,怎样进行无失真编码若：不考虑信源统计特性：
应满足条件,相互矛盾！
KL
L
mn
n
有效：
无失真,Km
m
n
L
Kmn KL
lo g
lo g由
结论,① 当 n = m 时,K≥L 不有效 。
② 当 K = L 时,m≥n,亦不满足有效性
解决办法,引入信源统计特性 。
§ 4.1无失真编码概述－ 3
考察无失真条件,
分别表示等概条件下的消息熵 与码字熵 之比，
考虑信源的实际统计特性（非等概），实际消息熵为：
代入无失真条件得：
此时：即使 m=n,只要 就有可能实现 K<L。
即无失真与有效性同时满足 。
具体实现 时,定长与变长编码
m
n
L
Kmn KL
lo g
lo g
mnloglog nSH log)(? mCH lo g)(?
i ii ppSH lo g)(
mSHLK log )(?
)(lo g SHm?
定长编码定理
描述
证明
物理意义
实际应用中的问题
§ 4.2定长编码定理－ 1
渐进等分割性
– 描述
– 证明
– 物理意义
– 应用
§ 4.2定长编码定理－ 2-描述定长 （ 等长 ） 码信源编码定理：
对离散,无记忆,平稳,遍历信源其符号序列,S =(S1,S2 …,.SL)，
可用 K个符号 C=(C1,C2…,Ck) 进行等长编码,对任意 ε>0,δ>0，
只要满足,(K/L)log m≥H(S)+ε
则：当 L足够大时,可使译码差错小于 δ，
反之,当 (K/L)log m≤H(S)-2ε 时,译码一定出错 。
解释：定长编码定理给出了信源进行等长编码所需码长的理论极限值 。
§ 4.2定长编码定理－ 2-进一步理解若要求变得的等长码是唯一可译的，则必须：
若 L＝ 1，则：
结论,对于唯一可译码，每个信源符号至少需要用 个码符号来变换。
当采用二元码编码时,m＝ 2，则：
结论,对信源进行二元等长编码时，每个信源符号所需码长的极限值为
m
n
L
Kmn KL
lo g
lo g
m
n
log
log
m
nK
lo g
lo g?
)(lo glo g 1 b itnKnLK L
)(log bitn
例 1：英文电报有 32个符号（ 26＋ 6），即 n=32，
若 m=2,L＝ 1（即对信源的逐个符号进行二元编码），
则：
解释,每个英文电报符号至少需要用 5位二元符号编码问题,第三章：在考虑符号出现的概率和符号间相关性前提下,每个英文符号平均携带的信息量是 1.4bit/符号（ ）,<<5bit/符号，
等长编码效率极低，如何提高效率？如何体现有效性？
532lo glo g nK Bit/符号
bitH 4.1
解决方法：
考察,字母个数为 n，字母出现非等概，且字母之间相关长度为 L的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着 L的增加，这种无意义序列的总数越来越大。
方法,进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 <<,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。
问题,会引入一定的误差，当 L足够长后，误差可以任意小。
Ln
Ln
§ 4.2定长编码定理－ 3－证明考察离散、随机序列信源的统计特性
－－渐进等分割性（ AEP）
AEP描述：
渐进等分割定理,（熵定理，遍历性定理）
设 是离散无记忆信源输出的一个特定序列，
则任给 和,总可以找到一个整数,使当时，有：
Nssss,..21?
0 0 0N
0NN?
1}|)({| )(l o g SHP N sP
引入：渐进等分割性（ AEP）
§ 4.2定长编码定理 － 4－ AEP物理意义任何一个离散随机序列信源当序列长度Ｌ → ∝ 时,信源序列会产生两极分化,大概率事件集合 与小概率事件集合,即 nL= ∪
对于 有性质,
①
②
(信源熵 ) (大概率事件熵 )
③ (等概率 )
对于 有性质,
由此可见,信源编码只需对信源中 少数 落入典型大概率事件的集合的符号进行编码即可 。 而对 大多数 属于非典型小概率事件集合中的信源符号无需编码,且 。
A?A?A?A
A
1)A(pL imL
)PP(H)P,P,P(H M2'n'2'1 k
M/1PP M1?
A
0)A(pL imL
0)(AP
信源序列集合
A
A
LS
§ 4.2定长编码定理－ 5 － AEP证明集合 和 中的序列分别称为 典型序列和 非典型序列可以证明：对于任意小的正数,,当 L足够大时，
表示 中所有 典型序列的集合表示 集合中序列的 个数还可以证明：对于任意小的正数,,当 L足够大时，
表示序列 出现的 概率由切比雪夫不等式可得：
表示 S中每个符号携带的信息量的方差
A?
A
00
])([])([ 2||||2)1( SHLSHL A
A?
||||?A
LS
A
0 Ai?
])([])([ 2)(2 SHLiSHL P )(
iP? i
LAP
21)(
2?
AEP结论：当 L足够大时，
所有 典型序列出现的概率近似相等，即 典型序列为 渐进等概 序列
可粗略认为 典型序列出现的概率为
所有 典型序列的概率和接近为 1，即
AEP应用：
提出、证明都是基于离散无记忆序列信源
平稳遍历信源有类似结果
体现信源统计特性
用以证明定长编码定理
1)(Ap
)(2 SLH?
§ 4.2定长编码定理－ 5 － 证明定长编码定理证明思路：
将取自 S，长为 L的信源符号序列分为集合 和
只对集合 中的序列进行一一对应的等长编码
此时的误差为,计算误差
可见当,且 (K/L)log m≥H(S)+ε时，
几个概念：
编码信息率,（编码 后 平均 每个信源符号 能载荷的 最大 信息率）
编码效率：
（编码 前后 平均每个信源符号能载荷的最大信息率之比）
A?
A
A
)(?APPE LAPAP 2)(1)(
0?EPL
mR LK lo g?
RSH )(
§ 4.2定长编码定理 － 6（ 物理意义）
结论：
可推广至离散、非平稳无记忆信源和有记忆信源情况
只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码
(K/L)log m≥H(S)+ε
mSHLK l o g )(
二元码时,m＝ 2：
)(
)(
)()(
SH
SH
L
K
L
K
L
K
R
SHSH
最佳等长码时：
§ 4.2定长编码定理 － 7（ 实际应用问题）
编译码同步问题
问题：如何使译码端知道码字起点
解决办法,1、每个码字加短同步前缀
2、每若干码字加较长同步前缀分组长度与编译码复杂性、编译码延时等等关系
问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加
解决办法：目前没有理想到解决办法定长信源编码的 理论意义 远大于其 实用价值
§ 4.2定长编码定理 － 8（ 举例 )
例 2：设有一简单离散信源,L=1,n=2
对其进行近似于无失真的等长编码,若要求其编码效率为 96%,差错率低于
10-5,试求符号联合编码长度 L=？
解：
由编码效率：
即：
再由,
可见,需要 4100万个信源符号联合编码,才能达到上述要求,这显然是不现实的,
一般来说：当 L有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码信源符号）/(811.0lo g)( 2
1
b itppSH
i
ii
%96)( )(SH SH
034.096.096.0811.0811.0
7522 222 101.410)034.0( 4 7 1 5.0
PLLP
4 7 1 5.0)]([lo g 22
1
)(2 2
SHpp
i
ii?
41
2
4
3
1 ss
p
S
§ 4.3变长信源编码 -1
几个码类的概念
非奇异码（奇异码、单义码）
唯一可译码
前缀码（即时码、非延长码、异前置码）
最佳码（紧致码）
Kraft定理唯一可译码存在定理变长编码定理（香农第一定理）
§ 4.3变长信源编码 -2(几个码类的概念 )
非奇异码：
每一个码字仅对应信源中的一个信源符号（序列）。
编码是单义的。
反之为奇异码或非单义码。
§ 4.3变长信源编码 -3(几个码类的概念 )
唯一可译码
编码单义、译码单义
对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。
§ 4.3变长信源编码 -4(几个码类的概念 )
前缀码
是一类唯一可译码
在一个变长码中，没有任何一个码字是其他码字的前缀。
译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。
又称即时码、非延时码
§ 4.3变长信源编码 -5(几个码类的概念 )
最佳码
唯一可译码的一类
其平均码长小于其他唯一可译码的平均长度所有的码非奇异码唯一可译码前缀码
§ 4.3变长信源编码 -6（ 几种类型的信源编码 举例）
例 3：
信源 概率 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
编码 Ⅰ 唯一可译等长编码 Ⅱ 奇异编码 Ⅲ 非奇异编码 Ⅳ 前缀编码 Ⅴ 唯一可译不等长
§ 4.3变长信源编码 -7(Kraft定理 )
引出码树
Kraft定理描述
Kraft定理证明－略
§ 4.3变长信源编码 -8(Kraft定理引出 )
问题,寻求 实时唯一可译码方法：研究实时唯一可译码的码字可分离条件引入：,码树,概念（直观）
结论：通过 Kraft定理给出 实时唯一可译码（ 前缀码）存在的条件码树－－ 变长码的树图表示将变长码与码树建立,一一对应,关系：
树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码
§ 4.3变长信源编码 -9(Kraft定理 )
问题：
比较简单信源，码树方法可直接且直观构造前缀码
较复杂信源，直接画码树复杂且困难解决方法：
为分析起来特别对含有很多符号种类的复杂信源更方便寻找一种与上述,树图,等效的解析式表达式 ----Kraft不等式 。
结论：
Kraft定理给出码字可分离或前缀码存在的充要条件
§ 4.3变长信源编码 -10(Kraft定理 )
定理：长度为 Ki（ i=1,2,…,n） 的 m （ 码字母表长度 ） 进制前缀码存在的充要条件为：
证明：略物理意义：
给定信源个数 N和码字数 M,只要允许码字长度可以足够长,就总可以满足 Kraft不等式,从而得到前缀码
1
1
n
i
k im
§ 4.3变长信源编码 -11(唯一可译码定理 )
Kraft不等式给出的限制也是所有唯一可译码都必须满足的。
定理描述：
任何唯一可译码均满足 Kraft不等式。
结论：
对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码
§ 4.3变长编码定理－ 12
问题：
对于已知信源 S可用码符号 X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择 准则 。
引入：码的 平均长度 。
离散无记忆平稳信源信源熵率为 码字母表个数为 M，
则前缀码平均码长：
ni
ni
ppp
sSsSsS
P
S
1
1
)(SH?
)(
1
i
M
i
i apkk?
§ 4.3变长编码定理－ 13
无失真变长信源编码定理 (即香农第一定理 ),
离散无记忆平稳信源 S，其熵率为,并有码符号
X={x1,…,xm}。对信源 S进行编码,总可以找到一种编码方法，
构成惟一可译码，使信源 S中 每个信源符号 所需的平均码长满足,
另一方面,必可以找到前缀码，使其平均码长满足
)(SH?
m
SHk
l o g
)(
1l o g )( mSHk
§ 4.3变长编码定理－ 14
定理证明－略物理意义：
又称 无噪信道编码定理
编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大
要做到无失真编码，变换每个信源符号平均所需最少的 m元码元数就是信源的熵率（以 m进制信息量单位测度）
信源的熵率是描述信源每个符号平均所需最少的比特数定理说明：
是存在性定理－－具有理论指导意义
是构造性定理－－设计出多种具体编码方法
§ 4.3变长编码定理－ 15－ 编码效率变长码编码效率,?衡量各种编码方法的优略，判断是否最佳码 。
编码前平均每个信源符号携带的信息量为：
编码后平均每个信源符号携带的最大的信息量为：
定义变长码编码效率为：
另一种理解：
最佳码（极限时） 每个信源符号 的平均码长为：
某一方法得到的 每个信源符号 的 平均码长为：
定义变长码编码效率为：
mklog
k
SH
mk
SH m )(
l o g
)(
)(SH?
)(l o g )( SHk mmSH
'k
''
)(
k
SH
k
k m
比较：
定长编码的编码效率：
变长编码的编码效率：
注意到,是指每个信源符号所需的平均码长，而 也是平均到每个信源符号的码长，所以它们是一致的，均表示无失真信源编码的效率。
K SLHmSHR SH mLK )(l o g )()(
k
SH
mk
SH m )(
l o g
)(
k LK
例 4,p160例 4.4
一离散无记忆信源
41
2
4
3
1 ss
p
S
其 熵 为,信源符号）比特 /(811.0l o g4l o g)( 344341SH
用二元符号（ 0,1； m=2）构造一个 前缀码,1,0 21 ss
此时 每个信源符号 平均码长 为,1?k
8 1 1.0)( k SH?编码效率 为：
为提高编码效率，对 S的 2次扩展信源进行 2维联合编码：
构造一个扩展信源 S2的前缀码：
前缀码
s1s2 9/16 0
s1s2 3/16 10
s1s2 3/16 110
s1s2 1/16 111
i? )( iP?
此时 平均码长 为：
16272?k
此时信源 S中每个符号对应的 平均码长 为：
32271627 2k
编码效率 为,961.0)(2
k SH?
同样可得,985.0)(3
k SH? 991.0)(4 k SH?
定长编码与变长编码效率比较：
例 4与例 2相比,同一个信源，当要求编码效率达到 96％时，
等长码需要 4100万个信源符号联合编码；
变长码只需 2个符号（二次扩展信源）联合编码；
结论,采用变长编码,L不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着 L的增大，编码效率越来越接近于 1。
§ 4.4实用的无失真信源编码方法举例－
1
（ huffman编码）
Huffman编码
编码方法
特点
应用
问题
§ 4.3实用的无失真信源编码方法举例－
2
（ huffman编码）
编码方法：
例?,=
消息 U 概率 pi 编码 C
U1 1/2 0 0
1 0
U2 1/4 0 10
1/21
U3 1/8 0 110
1/4 1
U4 1/8 1 111
pis
8/18/14/12/1
4321 ssss
§ 4.3实用的无失真信源编码方法举例－
3（ huffman编码）
编码规则：
1)将信源消息 U按概率大小排序 （ 由大至小 ） 。
2)从最小两个概率开始编码,并赋予一定规则,如下支路小概率为,1”,上支路大概率为,0”。 若两支路概率相等,仍为下支为,1”上支为,0”。
3) 将已编码两支路概率合并,重新排队,编码 。
4) 重复步骤 3） 直至合并概率归一时为止 。
5) 从概率归一端沿树图路线逆行至对应消息编码,如 U3为,110”。
§ 4.3实用的无失真信源编码方法举例－
4
（ huffman编码）
例 2：
§ 4.3实用的无失真信源编码方法举例－
5
（ huffman编码）
特点：
编码不是唯一的
保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用
每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元码情况）
每次缩减信源的最长两个码字具有相同码长这三个特点保证了所得到 huffman码一定是最佳码
§ 4.3实用的无失真信源编码方法举例－
6
（ huffman编码）
应用,
在不同领域得到广泛应用。
例,International digital facsimile coding standard(1980)US HDTV(1995)
问题：
误差扩散
速率匹配
要求了解信源的统计分布；
算法复杂度随着信源符号串长度的增加而迅速增长。
解决：
工程上克服误差扩散的方法有两种：一是限制哈夫曼码仅能应用于优质信道 （ <=10-6）
以限制扩散的可能性；二是采用定期清洗,防止扩散区域增大 。 但是它是靠牺牲有效性换取的 。
工程上解决速率匹配问题的方法是在两者之间加一个类似与水库的缓存器，它变速入，恒速出，以解决两者速率的匹配。
信源统计特性未知时可采用所谓通用编码的方法来解决
算法复杂度问题考虑采用算术编码方法解决。
