信息论基础理论与应用第三版傅祖芸第5章讲义

信息论基础理论与应用第三版 傅祖芸第5章讲义
引言
信息通过信道传输到信宿的过程。要做到既不失真又快速地 通信，需要解决两个问题： 信源编码:
在不失真或允许一定失真条件下，提高信息传输率. 信道编码:
在信道受到干扰的情况下，增加信号的抗干扰能力，同时又 使得信息传输率最大.
最佳编码： 一般来说，抗干扰能与信息传输率二者相互矛盾。而编码
5、码的N次扩展
若某码 C，它把信源S中的符号si 一一变换成码C中的码
字 wi ，则码C的N次扩展码是所有N个码字组成的码字序列
的集合B:
S C :{W1,W2 ,...,Wq}
扩展 B :{Bi (Wi1Wi2...WiN )}
C {W1,W2 ,L ,Wq}
码C
si N次扩展
Wi (xi1 xi2 ...xili ) N次扩展
i (si1 si2 ...siN )
Bi (Wi1Wi2 ...WiN )
(i 1,2,...,qN )
扩展信源
码B 扩展码
vi Bi (Wi1 ,Wi2 ,L ,WiN ), vi S N ,Wil C
[例] 设信源S的概率空间为：
S
0
s2
P(s2)
01
s3
P(s3)
001
s4
P(s4)
111
试求码的二次扩展码。
信源S的二次扩展信源： S 2 [1 s1s1,2 s1s2 ,3 s1s3,..., 16 s4s4 ] 则码的二次扩展码为：
信源 符号
α1 α2 α3 α4
码字
00: W1W1=B1 001:W1W2=B2 0001:W1W3=B3 0111:W1W4=B4
编码2 0 01 001 101
3、非奇异码与奇异码 非奇异码: 一组码中所有码字都不相同。
si s j Wi Wj ; si , s j S Wi ,Wj C
奇异码: 一组码中有相同的码字。
si s j Wi Wj ; si , s j S
Wi ,Wj C
信源符号
➢ 研究信道编码时，将信源编码与译码看成是信源与信宿的 一部分，从而突出信道编码。
编码器：
对信源的符号按一定的数学规则进行的变换。 它可以看作这样一个系统，它的输入端为原始信源S，其符 号集为
S {S1, S2 ,..., Sq}
而信道所能传输的符号集为
X {x1, x2 ,..., xr}
或：
i (si1 si2 ...siN ) Wi (xi1 xx2 ...xili ),
sik S, (k 1,2,...N ); xik X (k 1,2,...li )
若要实现无失真编码，这种映射应是一一对应的可逆 映射。
码的分类及定义
1、二元码与r元码 2元码: 码符号集X={0,1}. 如果将信源通过二元信道传输，必
Or: 码符号序列的反变换也唯一的（扩展码非奇异）
原因： 若要使某一码为惟一可译码，则对于任意有限长的码
符号序列，必须只能被惟一地分割成一个个的码字，才能 实现唯一的译码。
须将信源编成二元码，这是最常用的一种码。 r元码: 码符号集有r个符号的编码。
2、等长码与变长码 等长码: 一组码中所有码字的长度都相同。 变长码: 一组码中所有码字的长度各不相同。
信源符号si s1 s2 s3 s4
符号出现概率p(si) p(s1) p (s2) p (s3) p (s4)
编码1 00 01 10 11
只可唯一地划分为1,00,01,1,01，因此是惟一可译码； 而对另一个二元码 C2 {0,10, 01} ，当码字序列为
…01001… 可划分为0,10,01或01,0,01，所以是非惟一可译的。
唯一可译码的条件
1）不同的信源符号变换成不同的码字(非奇异码)；
2）任意有限长的信源序列所对应的码元序列各不相同. 即: 码的任意有限长N次扩展码都是非奇异码。

s1

P(
s1
)
s2 P(s2 )
s3 P(s3 )


sq P(sq )
q
p(si ) 1
i 1
若通过—个二元信道进行传输，须把信源符号变换成 0，1 符 号组成的码符号序列(二元序列)。采用如下二元码， 如下表所示 （q=4）：
信源符号si 符号出现概率P(si)
编码器功能：用符号集X中的元素，将原始信源的符
号 si变换为相应的码字符号 wi，编码器输出符号集为
C :{W1,W2,...,Wq} (码或码书)
wi 称为码字，li 为码字 wi 的码元个数（码字长度，码
长）。码字集合C称为码或码书。
编码的形式化描述： 从信源符号到码符号的一种映射
si (i 1,2,...,q) Wi (xi1 xi2 ...xili ), xik X , (k 1,2,...li )
定理理论上证明，至少存在某种最佳的编码能够解决上述矛盾， 做到既可靠又有效地传输信息。
信源编码： 信源虽然多种多样，但无论是哪种类型的信源，信源符号
之间总存在相关性和分布的不均匀性，使得信源存在冗余度。 信源编码的目的就是要减少冗余，提高编码效率。
研究方法
5.1 编码器
➢ 研究信源编码时，将信道编码与译码看成是信道的一部分， 从而突出信源编码；
信源 符号
α5 ：
码字
010:W2W1=B5
：
：
：
：
：
信源 符号
： ： ： α16
码字
： ： ：
111111:W4W4=B16
6、唯一可译码(单义可译码）
由码构成的任意一串有限长的码符号序列只能被唯一的 译成所对应的信源符号序列。
否则,就为非惟一可译码或非单义可译码。
例：对于二元码 C1 {1, 01, 00} ，当任意给定一串码字 序列，例如 …10001101…
a1
p(ai )
1/2
编码1 00
编码2 0
a2
1/4
01
0
a3
1/8
10
1
a4
1/8
11
10
4、同价码
同价码: 码符号集 X {x1, x2,..., xr} 中每个码符号所占的 传输时间都相同(大多数情况)。
变长码中每个码字的传输时间就不一定相同。 （摩尔斯电报码，点-划 所占传输时间不同）