信息论讲义_第十二讲

15
S1 bb
S2 cde
S3 de
S4 b
S5 ad bcde
S6 d
S7 eb
S8
Φ
5.4.3 唯一可译码判别准则（续）
例如： S0={a,c,ad,abb,bad,deb,bbcde}是否唯一可译码
16
5.4.4 变长信源编码定理
1. 码平均长度
离散无记忆信源为 S
s1 P p( s1 ) s2 p( s2 ) sq p( sq )
H (S ) H (S ) L 1 gr log gr log
20
5.4.4 变长信源编码定理（续）
释： (1) L 的极限值为
H (S ) log r
，即下界；小于 L
下界，则唯一可译码不存在 (2) 紧致码平均码长不一定达到下界 (3) 达到下界的唯 达到下界的唯一可译码是紧致码 可译码是紧致码 (4) 紧致码最短码长 L H ( S ) l r log
编码后的码字 W1 , W2 , , Wq 码字的长度 l1 , l 2 , , l q 因为是唯一可译码，si和Wi一一对应
p( si ) p(Wi )
则码字平均长度为
L p (Wi )li p ( si )li
i 1 i 1
17
q
q
5.4.4 变长信源编码定理（续）
21
5.4.4 变长信源编码定理（续）
4. 变长无失真信源编码定理（香农第一定理，序列） 定理：设离散无记忆信源
s1 P p( s1 ) s2 p( s2 ) sq p( sq )
S
其信源熵为H(S)，它的N次扩展信源为
S
N
1 P p (1 )
bit/码符号
故
1 H (s) Rt R t Lt
bit/秒
L
Rt
信息传输率高
18
5.4.4 变长信源编码定理（续）
2. 紧致码
定义：对于某一个信源和某一码符号集，若有一个唯一 可译码 其平均码长度 L 小于所有其它唯一可译码的平 可译码，其平均码长度 均码长度，则称该码为紧致码（也称最佳码） 释：无失真信源编码核心问题是寻找紧致码 紧致码是平均码长最短的唯 可译码，但紧致码不 紧致码是平均码长最短的唯一可译码，但紧致码不 一定只有一个。
H ( S ) 1 LN H ( S ) log r N N log r
1 LN H r (S ) H r (S ) N N
23
5.4.4 变长信源编码定理（续）
当 N 时，则
LN H r (S ) N N lim
LN H ( S ) lim N N log r
8
5.4.1 变长信源主要编码方法
1、匹配编码：概率大的信源符号，代码长度短； 反之，概率小的信源符号，代码长度长。 2、变换编码：从一种空间变换成另一种空间，然后 进行编码。 3、识别编码：对有标准形状的文字、符号和数据 进行编码。 ＊在这里仅介绍匹配编码方法。
9
5.4.1 变长信源主要编码方法（续）
li r 1 i 1 q
克拉夫特证明不等式为即时码存在的充要条件； 麦克米伦证明不等式为唯 可译码存在的充要条件 麦克米伦证明不等式为唯一可译码存在的充要条件。
11
5.4.2 Kraft不等式和McMillan不等式（续）
例：设二进制码树中X=(a1 , a2 , a3 , a4), K1不存在满足这种 =1，K2=2，
释： (1)li 是第i个码字的长度，必须是整数； (2) L 是变长编码后，一个信源符号平均所需要的码元个数，可以是小数； (3)编码后，每个信源符号si平均用 L 个码符号来表示，平均每个码符号 携带的信息量
H (s) R H (X ) L
(4)若传输一个码符号需要 (4)若传输 个码符号需要t秒，则每秒传输率为
10
5.4.2 Kraft不等式和McMillan不等式
设信源符号集为S = (s1, s2, …, sq,)，码符号集 为X = (x1, x2, …, xr)，对信源进行编码，代码组 为C = (w1, w2, …,wq)，相应码长分别 相应码长分别 l1, l2,…, lq， 即时码存在（唯 可译码存在）的充要条件为 即时码存在（唯一可译码存在）的充要条件为：
其中，L N 是扩展信源中每个信源符号 i 对应的 平均码长
LN p ( i )i
i 1 qN
式中， i 是 i 对应的码字长度
24
5.4.4 变长信源编码定理（续）
对于平稳遍历的离散有记忆信源 如马尔可夫信 对于平稳遍历的离散有记忆信源（如马尔可夫信 源），有
LN H lim N N log r
2 N 2 H ( S ) (1 ) 2
D I ( si )
5
上
编码指标
节
提
要
(1) 编码速率：
L log r R N bit / 符号
(2) 编码效率：
H (s) R
6
第五章 无失真信源编码
内容提要 5.1 编码器 5 2 分组码 5.2 5.3 定长编码 5.4 变长编码 5 5 变长编码方法 5.5
19
5.4.4 变长信源编码定理（续）
3. 定理：（平均码长下界） 设离散无记忆信源
s1 P p( s1 ) s2 p( s2 ) sq p( sq )
S
的信源熵为H(S)，用码符号集 X {x1 , x2 , , xr }进行 编码，则存在一种编码方式构成唯一可译码，平 均码长 L 满足
13
5.4.3 唯一可译码判别准则
1、由原始码集合S0，构造集合S1，S2，… ① S1的构造： 若 wi S 0 , w j S 0 ，且 且 wi w j A ，则后缀 则后缀A放入S1中， 中 S1由所有这样的A构成。 ② Sn(n>1)的构造：将S0和Sn-1进行比较 若 W S 0 ,U S n 1 ，且 且 W UA ，则 则A放入Sn中， 中 若 W ' S n 1 ,U ' S 0 ，且 W ' U ' A' ，则A’放入Sn中， Sn由所有这样的A和A’构成。
其中，H 为有记忆信源的极限熵
25
5.4.4 变长信源编码定理（续）
释：① L N 是扩展信源SN编码后，一个符号 i 对应的平 均码长； 平均码长；
LN 扩展信源编码后 原始信源S一个符号 扩展信源编码后，原始信源 个符号Si 对应的 N
② L 是原始信源S编码后，一个符号 Si 对应的平 均码长 均码长；
Morse电报字符
A B C D E F G H I J ·– –··· –·–· –·· · ··–· ––· ···· ·· ·––– K L M N O P Q R S T –·– ·–·· –– –· ––– ·– –· ––·– ·–· ··· – U V W X Y Z ， . ··– ···– ·–– –··– –·–– – –·· ––··– – ·–·– ·– 1 2 3 4 5 6 7 8 9 0 ·–––– ··––– ···–– ····– ····· –···· ––··· –––·· ––––· –––––
NH r ( S ) 1 1 用变长编码来达到相当高的编码效率 ,一般所要求的信源 LN
序列长度N可以比定长编码小得多。
28
5.4.4 变长信源编码定理（续）
例：设离散无记忆信源概率空间
a6 a7 a8 X a1 a2 a3 a4 a5 P 0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.04
信息理论基础
（第十二讲） （第十 讲）
授课教师 于 授课教师：于
泽
电子信息工程学院201教研室
上
信源编码的目的
节
提
要
一是使序列中的各个符号尽可能地 中 互相独立，即 解除相关性------方法包括预测编码和变换编码； ； 二是使编码中各个符号出现的概率 是使编码中各个符号出现的概率均匀分布，即 概率均匀化 概率均匀化------方法主要是统计编码。 方法主要是统计编码。
K3=2，K4=3，应用 应用Kraft不等式,得： 得
4 Ki 1 2 2
Ki的唯一可译码
3
9 2 2 2 2 2 1 8 i 1 如果将各码字长度改成K1=1 1，K2=2 2，K3=3 3，K41 2 2 2 3 2 3 1
2

p ( 2 )
p ( q N )
N
q
22
5.4.4 变长信源编码定理（续）
扩展信源熵为H(SN)，码符号集X=(x1,x2, …xr)， 用X对SN编码，则总可以找到一种编码方法，构 成唯一可译码 成唯 可译码，使信源 使信源S中的每个信源符号所需 要的码字平均长度满足 或
14
5.4.3 唯一可译码判别准则（续）
2、定理：码集合S0是唯一可译码的充要条件是S1,S2,… 中没有一个含有 个 S0的元素。 例如： S0={a {a,c,abb,bad,deb,bbcde} c abb bad deb bbcde}是否唯 是否唯一可译码 可译码
S0 a c abb bad deb bb d bbcde
27
5.4.4 变长信源编码定理（续）
5.编码速率、编码效率、剩余度
(1) 编码速率：变长编码的编码速率为 LN R log r N (2) 编码效率：编码效率定义为
H ( S ) NH r ( S ) NH ( S ) R LN LN log r
(3) 剩余度： 剩余度 变长码的剩余度为