信息论第四章 信源编码
W:{W1,W2,…,Wn}。
2013-12-20 2
S: {s1,s2…sn}
W: {w1,w2…wn} 编码器 A: {a1,a2…aq}
S=原始信源符号集; A=信道码元符号集; W=码字符号集;(码组) Wi=[w1,w2,…wLi] wi∈{a1,a2,…aq} L为码字Wi的码元个数,称为码字Wi的码字长度, 简称码长。 q=2时,称为二元编码,否则称为q元编码。
到一种编码方法,构成单义可译码,使信源S中每个符号所
需要的平均码长满足:
H lim L N log q
已知N次扩展信源的熵为H([S])=H(S1,S2,…,SN),根据平均码 长的界限定理,
H ([S ]) H ([S ]) LN 1 log q log q
2013-12-20 21
例如:W:{0,01}是单义的,但不是瞬时可译码。
2013-12-20 6
⑶单义可译码定理
设原始信源符号集为S:{s1,s2,…sn},码元符号集为 A:{a1,a2,…,aq},码字集合为W:{W1,W2,…Wn},其 码长分别为L1,L2,…,Ln;则单义可译码存在的充要 条件为码长组合满足Kraft不等式,即
2013-12-20 7
信源 符号 s1 s2 s3 s4
[W1]
0 01 011 0111
[W2]
0 10 110 1110
[W3]
0 11 100 110
[W4]
0 10 110 111
[W5]
0 10 11 110
[W6]
00 01 10 11
W1:满足Kraft不等式,但只是单义的,不是瞬时可译码;码长组合为1,2,3,4; W2:满足Kraft不等式,是单义的,也是瞬时可译码;码长组合为1,2,3,4;
i 1 i
i
11
2013-12-20
这时看一下信息传输效率:每个信道码元所 携带的平均信息量。 当信源S给定,信源的熵为H(S),则每 个信道码元所携带的平均信息量可以表 示为:
H (S ) R H ( X ) H ( A) L
2013-12-20 12
H (S ) R H ( X ) H ( A) L
2013-12-20 1
4.1.1 编码器(Encoder)
编码的作用可以分为以下面两点:
•一些原始信源符号不适应信道的传输;
•原始信源符号的传输效率很低;
编码器可以看作这样一个系统。它的输入端为原始信源S
,其符号集为S:{s1,s2,…,sn};si(i=1,2,…n);而信道所能传 输的符号集为A:{a1,a2,…,aq};编码器的功能是用符号集A 中的元素,将原始信源的符号si变换为相应的码字符号Wi , (i=1,2,…,n) , 所 以 编 码 器 输 出 端 的 符 号 集 为
W3:满足Kraft不等式,不是单义的,也不是瞬时可译码;码长组合为1,2,3,3;
W4:满足Kraft不等式,是单义的,也是瞬时可译码;码长组合为1,2,3,3; W5:不满足Kraft不等式,不可能为单义的;码长组合为1,2,2,3;
W6:满足Kraft不等式,是单义的,也是瞬时可译码;为等长码;
码效率的极限定理。
[定理一]: 离散无记忆信源S的N次扩展信源SN,其 熵 为 H(SN) , 并 且 编 码 器 的 码 元 符 号 集 为 A:{a1,a2,…aq},对信源SN 进行编码,总可以找到一 种编码方法,构成单义可译码,使信源S中每个符 号si所需要的平均码长满足:
N
2013-12-20
2013-12-20 16
例如:S:{s1,s2,s3,s4}; P(S):{1/2,1/4,1/8,1/8}时,
编码后码长为[1,2,3,3], 这时平均码长将为L=H(S)=1.74 码元/符号。
上界的证明思路:只要有一种方法使上界成立,就 说明总可以找到一种方法使上界成立。
平均码长大于这个上界当然也可以构成单义可译码,
q
i 1
n
Li
1
①Kraft不等式不仅是单义可译码的充要条件,也是瞬时可译码的充 要条件; ②这里所说的充要条件是对于码长组合而言,而不是对于码字本身 而言,就是说:满足Kraft不等式的码长组合一定能构成单义码,单 义码的码长组合一定满足Kraft不等式。 ③有些码字的码长组合满足Kraft不等式,但不是单义码。(编码方 法不对)
log p( si ) 1 Li log q p( si ) log q log q p( si )
可得:
p( si ) q
Li
当然这要求信源符号的先验概率满足其是以q为底的对数 为整数,这就要求信源符号的先验概率为p(si)=q-Li形式, 如果满足这一条件,编出的码字称为最佳码。
将上式除以N得:
H ([S ]) LN H ([S ]) 1 N log q N N log q N
可以注意到:对于平稳各态历经有记忆信源来说,当信源
稳定后,即当N趋于无穷时,每发一个符号携带的平均信息 量等于其极限熵。
1 lim H ( S1, S2 ,... S N ) lim H ( S N 1 / S1, S2 ,... S N ) H N N N
2013-12-20 8
⑷用码树图构成瞬时可译码
从根开始,画出q条分支,任选一个分支作为W1; 在另一个分支上再分出q条分支,任选一个分支作为 W2;继续进行,直至结束;从根到各端点,所经过的 状态即为码字;
2013-12-20
9
4.1.3 平均码字长度
如果一个码组的参数满足Kraft不等式,就 一定可以构成无噪声信道下的无失真传输 ,然而,在一个通信系统中,信源编码的 主要目的是提高编码效率,即每个码元符 号要携带更多的信息量。因此要定义平均 码长的概念。
lim L H q ( S )
18
说明:H(SN)=NH(S),根据平均码长的界限定理有:
H(S N ) H(S N ) LN 1 log q log q
则不等式都除N可以变为:
H(S N ) LN H(S N ) 1 N log q N N log q N
即得: H ( S )
又考虑到lim(1/N)=0,可知:
H lim L N log q
22
2013-12-20
比较定理一和定理二,由于H(S)≤H∞ ,所以,有记忆信源的 平均码长的下界将小于无记忆信源的平均码长的下界; 对于m阶马尔柯夫信源来说;H∞=Hm+1(S),则有:
H m 1 lim L N log q
即,记忆长度越长,平均码长的下界就越小。有:
H m ( S ) H1 ( S ) H 0 ( S ) H max ( S ) H
定理一和定理二说明:可以用信源扩展的方法,达到数据 压缩的目的,扩展程度越高,编码效率越高。
2013-12-20
23
[定理三]:
设信源S的熵为H(S),无噪声离散信道的信道容 量为C。则总可以找到一种编码方法,使信道上 的信源符号平均传输速率为[C/H(S)-ε]。其中ε可 以是任意小的正数。要使符号平均传输速率大于 C/H(S)是不可能的。
2013-12-20 5
⑵瞬时可译码(非续长码)定义
如果一个码组中的任一个码字都不是另一个码 字的续长,或者说,任何一个码字后加上若干 码元后都不是码组中另一个码字。则称为瞬时 可译码,也称为非续长码。
例如:
W:{0,10,100,111}不是瞬时可译码,100为10的 续长。
瞬时可译码一定是单义的,单义可译码却不一 定是瞬时可译码。
第四章 信源编码
4.1 离散信源的信源编码
通信的根本目的就是有效而可靠地传输信息。
Shannon信息论中的一个重要内容就是它给出了信
息传输的有效性和可靠性的极限能力。
具体表现为两个编码定理;一般称为Shannon第一
编码定理(信源编码定理,有效性编码定理)和
Shannon第二编码定理(信道编码定理,抗干扰编 码定理)。
但实际上总希望码长小; 当一个离散无记忆信源的统计特性确定后 ,信源熵
H(S)就确定了,平均编码长度下界也就确定了,编码
效率也就确定了,如果进一步提高效率,就要想其它 方法。下面的编码定理给出了进一步的方法。
2013-12-20 17
4.2 编码定理
以下是Shannon编码定理的三种形式。它们是进一步提高编
i 1
n
由单义可译码的存在定理可知,当满足∑q-Li≤1时,取对数
后为小于等于0。则有:
H ( S ) L log q 0;
2013-12-20
H (S ) L log q
15
平均码长最小不能小于极限值,H(S)/logq,若小于,则不存
在单义可译码; 当下界等号成立时,效率最高时,为
2013-12-20 3
4.1.2 单义可译码(Uniquely decodable code)
⑴单义可译码定义 如果一个码组的任一有限长的码字序 列(一串码字),只能唯一地被译成 一个一个码字,则称为单义可译码, 也称为异前置码。
2013-12-20
4
例如:
信源符号:S: {s1,s2,s3}; 码元符号:A:{0,1}; 码字集合:W: {w1=0, w2=10, w3=11}, 为单义可译码。 在无差错条件下,当接收码字序列为: 010011001111…,可以唯一地译为: w1,w2,w1,w3,w1,w1,w3,w3……; 如果码字集合为:W:{0,01,11} 则为非单义可译码。 当接收码字序列为:010011001111… 时, 可以译为:w2,w1,w1,w3,w1,w1,w3,w3,(w2,w3..),… 即可以有不同的译码方法。