信息论与编码复习

1、课程内容 信息论的基本问题信息的度量 无失真信源编码定理香农第一定理 信道编码定理香农第二定理 限失真信源编码定理香农第三定理 信源编码 信道编码2绪 论 1、信息论的奠基人香农及其重要著作； 2、信息、消息、信号的区别和联系 3、通信系统的模型各主要功能模块（包括信源、信道、信宿、信源编译码器、信道编译码器）及其作用4 信息论的奠基人：香农 信息时代的里程碑： 1948年 香农通信的数学理论(A mathematical theory of communication)。第一次提出了信息量的概念，并应用数理统计的方法来研究通信系统，创立了信息论。 三大定理 无失真信源编码定理（第一极限定理）

2、 信道编码定理（第二极限定理） 限失真信源编定理（第三极限定理） 5（一） 信息论的形成与发展（二）信息、消息和信号的区别与联系 信息 是事物运动状态或存在方式。6 消息是指包含有信息的语言、文字和图像等 信号是消息的物理体现。 信号是信息的载荷子或载体，是物理性的。 同一信息，可以采用不同的信号形式 (比如文字、语言、图象等）来载荷； 同一信号形式，比如 “0”与 “1”可以表达不同形式的信息，比如无与有、断与通、低与高 (电平) 等。 在通信系统中，实际传输的是信号，但本质内容的是信息。信息包含在信号之中，信号是信息的载体。通信的结果是消除或部分消除不确定性，从而获得信息。7（三）数字通信

3、系统模型8信道信源信源编码加密信道编码干 扰 源信宿信源解码解密信道解码加密密钥解密密钥信源、信宿和信道 信源：向通信系统提供消息u的人和机器。发送消息的源 信宿：信息归宿之意，亦即收信者或用户，是信息传送的终点或目的地。 信道：传输信息的物理媒介 9信源编码器与译码器 信源编码器 符号转换； 压缩信源的冗余度,提高通信系统传输效率； 包括无失真信源编码、限失真信源编码。 信源译码器 把信道译码器输出的代码组变换成信宿所需要的消息形式，它的作用相当于信源编码器的逆过程10信道编码器与译码器 信道编码 提高信息传送的可靠性。 在信源编码器输出的代码组上有目的地增加一些监督码元,使之具有检错或纠错

4、的能力 信道译码器 具有检错或纠错的功能,它能将落在其检错或纠错范围内的错传码元检出或纠正,以提高传输消息的可靠性。 11信源与信息熵 熟练掌握：自信息量、离散信源熵、互信息、信息不增性的定义概念、并能进行相关计算 熵的性质(非负性、对称性、确定性、香农辅助定理、最大熵定理、条件熵小于无条件熵) p28 掌握互信息量和熵之间的关系. 离散平稳无记忆信源X的N次扩展信源的熵等于信源X的熵的N倍 13(一)自信息量设离散信源X，其概率空间为自信息量：某符号出现后提供给收信者的信息量14)(log)(iixpxI1212()()()nnxxxXp xp xp xP1()0()1iniip xp x自

5、信息量 自信息的单位的确定 在信息论中常用的对数底是2,信息量的单位为比特(bit)； 若取自然对数e,则信息量的单位为奈特(nat); 若以10为对数底,则信息量的单位为笛特(det) 15I(xi)的特性： I (xi)是非负值 当p(xi) = 1时，I(xi) = 0 当p(xi) = 0时，I(xi) = I(xi)是先验概率p(xi)的单调递减函数，即 当p(x1)p(x2)时，I (x1)I (x2)两个独立事件的联合自信息量等于它们分别的自信息量之和。1617),(log)(iixpxI)|(log)|(jijiyxpyxI)(log)(jijiyxpyxI(二)离散信源熵 离

6、散信源熵H(X) (平均不确定度/香农熵) 定义 信源的平均不确定度，是在总体平均意义上的信源不确定度。18iiiiiixpxpxIxpXH)(log)()()()(单位为比特/符号或比特/符号序列 条件熵条件熵19)|()|()|(jiijijyxIyxpyXH(| )( ) (|)( ) ( |) ( |)( ,) ( |)jjjjijijijijijiH X Yp y H X yp y p x y I x yp x y I x y )|(log),()|(),()|(ijijjiijijjixypyxpxyIyxpXYH20 联合熵联合熵 联合熵是联合符号集合(X,Y)上的每个元素对(x

7、i,yj)的自信息量的概率加权统计平均值。21 联合熵H(X,Y)表示X 和Y同时发生的不确定度。(, )( ,) ( ,)( ,)log( ,)ijijijijijijH X Yp x y I x yp x yp x y H(XY)与H(X)、H(X/Y)之间的关系 H(X,Y)H(X)H(Y|X) H(X,Y)H(Y)H(X|Y) 当X、Y独立时H(X,Y)H(X)H(Y)22(三)、互信息23 定义为 xi的后验概率与先验概率比值的对数)()|(log);(2ijijixpyxpyxI 互信息I(xi;yj)：表示接收到某消息yj后获得的关于事件xi的信息量。平均互信息24 互信息= 先

8、验不确定性后验不确定性 = 不确定性减少的量,( ; )()(| )(/)( ,)log( )ijiji jiI X YH XH X Yp xyp x yp x Y未知,X 的不确定度为H(X) Y已知,X 的不确定度变为H(X |Y)(四)、平均互信息的性质(; )( ;)I X YI Y X(; )0I X Y (; )()()( ;)( )( )I X YH XI XI Y XH YI Y25(; )( ;)I X YI Y X(; )0I X Y (; )()( ;)( )I X YH XI Y XH Yi.对称性：ii.非负性：iii.极值性：iv.凸函数性 （1）平均互信息量I(X

9、;Y)是输入信源概率分布 p(xi)的上凸函数研究信道容量的理论基础。 （2）平均互信息量I(X;Y)是是信道转移概率 p(yj|xi)的下凸函数研究信源的信息率失真函数的理论基础。平均互信息与各类熵的关系 26)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)()()()|()()|()()(YHXHXYHYXHYHXYHXHXYH维拉图 27H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)|()()|()()()()()|()()|()()(XYHYHYXHXHYHXH

10、XYHYXHYHXYHXHXYH（五）、数据处理定理 数据处理定理说明： 当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。 28(六)、熵的性质1.非负性 H(X)H(p1，p2，pn)0 式中等号只有在pi =1时成立。2.对称性 H(p1，p2，pn) = H(p2，p1，pn) 例如下列信源的熵都是相等的：291231/3 1/2 1/6xxxXP 2/ 16/ 13/ 1321yyyPY6 / 13 / 12 / 1321zzzPZ3.确定性 H(X)H(p

11、1，p2，pn)0 只要信源符号中有一个符号出现概率为1,信源熵就等于零。4.极值性(香农辅助定理) 对任意两个消息数相同的信源 30niyqYxpX, 2 , 1,)()(iniiniiinqppppppHloglog),(11215.最大熵定理 离散无记忆信源输出M个不同的信息符号,当且仅当各个符号出现概率相等时即( pi1/M)熵最大。31MMMHXH2log1,1)()()()()()|()()|(YHXHXYHYHXYHXHYXH6.条件熵小于无条件熵 信道与信道容量 熟练掌握信道容量的定义以及相关计算（包括计算信道容量以及达到信道容量时对应的输入概率分布） 重点：无干扰离散信道、对

12、称DMC（离散无记忆）信道 33信道容量 信道容量C： 最大的信息传输率341)(,0)(),;(max1)(niiiapapapYXICi 单位时间的信道容量：);(max1)(YXITCiap1、无干扰离散信道 设信道的输入X XA=a1 an,输出YB=b1 bm信道 输入和输出符号之间有确定的一一对应关系35) 3 , 2 , 1, (10)|()|(jijijibapabpjiij 由36)|(log),()|(ijijjixypyxpXYH)|(log),()|(jiijjiyxpyxpYXH 噪声熵H(Y|X) = 0 损失熵H(X|Y) = 0)()()(YHXHYXI；nYX

13、ICiap2)(log);(max信道 多个输入变成一个输出(nm)3701)|(01)|(或或jijibapabp 噪声熵H(Y|X) 0 损失熵H(X|Y) 0()( )( )I X YHYH X；)(max);(max)(YHYXICiap信道 一个输入对应多个输出(nm) 接收到符号Y后,对发送的X符号是完全确定的。 噪声熵H(Y|X) 0 损失熵H(X|Y) = 038)()(),(YHXHYXI)(max);(max)(XHYXICiap2、对称DMC信道 对称离散信道： 对称性: 每一行都是由同一集q1, q2,qm的诸元素不同排列组成输入对称 每一列都是由p1, p2,pn集的

14、诸元素不同排列组成输出对称392131616121313161213131616161613131PP对称DMC信道 若输入符号和输出符号个数相同,都等于n,且信道矩阵为40pnpnpnppnpnpnppP111111111 此信道称为强对称信道 (均匀信道)信道矩阵中各列之和也等于1 对称离散信道的平均互信息为41)|()()|()()(XYHYHYXHXHYXI；niaYHabpabpabpabpapXYHiijjijijijiji, 2 , 1)|()|(log)|()|(log)|()()|(),()|()|(21mipppHaYHXYH 对称DMC信道的容量： 42 上式是对称离散信

15、道能够传输的最大的平均信息量,它只与对称信道矩阵中行矢量p1, p2,pm 和输出符号集的个数m有关。ijmjijmppmpppHmC121loglog),(log 强对称信道的信道容量： )1,1,1 (log2npnppHnC信息率失真函数 1、概念、定义：失真函数、平均失真、允许失真度、试验信道 2、信息率失真函（注意与信道容量的比较 ) 3、信息率失真函数的定义域(即Dmin和Dmax）及相应的信道转移概率的计算441、失真函数 失真函数在信号空间中可以看作一类“距离”侧度，它有性质： 0( ,)0ijijijxyd x yxy45失真函数定义为：,(1)()0 (2)()0(3) 0

16、()minijijijijuU vVijd u vuvd u vd u v ，当 将所有的d(xi,yj)排列起来,用矩阵表示为:46),(),(),(),(1111mnnmbadbadbadbadd失真矩阵2、平均失真 xi和yj都是随机变量,所以失真函数d(xi,yj)也是随机变量,限失真时的失真值只能用数学期望表示 将失真函数的数学期望称为平均失真：( ,) ( ,)ijijijDdp u v d u v47jjiijiibadabpapD),()|()( 允许失真D：平均失真的上界 失真函数d(xi,yj)(信号空间中某类“距离” )： 描述了某个信源符号通过传输后失真的大小 平均失真

17、 ： 描述某个信源在某一试验信道传输下的失真大小,它对信源和信道进行了统计平均,是从总体上描述整个系统的失真D483、试验信道 若平均失真度 不大于我们所允许的失真,即49DDD 则称此为保真度准则 当信源p(xi)给定,单个符号失真度d(xi,yj) 给定时,选择不同的信道p(yj|xi), 相当于不同的编码方法,其所得的平均失真度不同。满足 条件的所有转移概率分布pij ,构成了一个信道集合50DD |(DDabpPijD）： 称为D失真允许的试验信道：满足保真度准则的试验信道。4、信息率失真函数R(D) R(D)： 在限定失真为D的条件下信源输出的最小信息速率。 51),(min)(YX

18、IDRDP 在信源给定后,我们希望在满足一定失真的情况下,使信源必须传输给收信者的信息传输率R尽可能地小。 若从接收端来着,就是在满足保真度准则下,寻找再现信源消息所必须获得的最低平均信息量。即在满足保真度准则的条件下寻找平均互信息I(X,Y)的最小值。 PD是所有满足保真度准则的试验信道集合,因而可以在集合PD中寻找某一个信道pij,使I (X,Y)取极小值。 离散无记忆信源52ijjijijiPpbpabpabpapDRDji)()|(log)|()(min)(R(D)的定义域 率失真的定义域问题就是在信源和失真函数已知的情况下,讨论允许平均失真度D的最小和最大取值问题。 由于平均失真度是

19、非负实数d(xi,yj)的数学期望,因此也是非负的实数,即 的下界是0。 R(D)=0意味着不需传输任何消息，D越大，直至无穷大都能满足这种情况。 Dmin Dmax为R(D)的定义域。（确界）53DD, 0Dmin 和R(Dmin)的计算 信源的最小平均失真度：54nijijiyxdxpD1min),(min)( 只有当失真矩阵的每一行至少有一个0元素时,信源的平均失真度才能达到下限值0。Dmax和R(Dmax) 选择所有满足R(D)0中D的最小值，定义为R(D)定义域的上限Dmax，即 由于I(X,Y) = 0的充要条件是X与Y统计独立,即：max() 0minR DDD55)()|(ji

20、jypxypjijiijypjjijiiypyxdxpypyxdypxpDjj),()()(min),()()(min)()(maxnijiimjyxdxpD12 , 1max),()(min 平均互信息I(X;Y)： 信源的概率分布p(xi)的上凸函数。 信道传递概率p(yj|xi)的下凸函数。56);(max)(YXICixp 信道容量： 信息率失真函数： );(min)(YXIDRDP 假定信道固定的前提下,选择一种试验信源使信息传输率最大。 它所反映的是信道传输信息的能力,是信道可靠传送的最大信息传输率。 一旦找到了信道容量,它就与信源不再有关,而是信道特性的参量,随信道特性的变化而变

21、化 不同的信道其信道容量不同。57 假定信源给定的情况下,用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。 它反映的是信源可以压缩的程度,是在满足一定失真度要求下信源可压缩的最低值。 率失真函数一旦找到,就与求极值过程中选择的试验信道不再有关,而只是信源特性的参量 不同的信源其R(D)不同。58： 充分利用已给信道,使传输的信息量最大,而发生错误的概率任意小。 ： 解决在已知信源和允许失真度D的条件下,使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息,以提高通信的有效性。59第五章 信源编码 1、编码的定义和分类：信源编码、信道编码、安全编码 2

22、、信源编码的目的 3、唯一可译码的特殊结论 4、熟练掌握三种能获得最佳变长编码的方法：香农编码、费诺编码、哈夫曼编码；了解游程编码60 实现的信源编码,要求: 信源符号X1 X2Xl XL 是一一对应的 码字Y1 Y2Yk YK 能够无失真或无差错地从Y恢复X,也就是能正确地进行反变换或译码 ; 传送Y时所需要的信息率最小信息率最小61定长编码 只有当K长的码符号序列数 mK大于或等于信源的符号数nL时,才可能存在定长非奇异码定长非奇异码。 loglogLKKnnmLm或定长编码定理由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1XlXL,可用 K个符号Y1YkYK(每个

23、符号有m种可能值)进行定长编码。对任意0,0,只要 则当L足够大时,必可使译码差错小于;反之,当时,译码差错一定是有限值,而当L足够大时,译码几乎必定出错 log(X)LKmHLlog(X)2LKmHL只要码字所能携带的信息量大于信源序列输出的信息量,则可以使传输几乎无失真,条件是条件是L足够大足够大。反之,当 时,不可能构成无失真的编码,也就是不可能做一种编码器,能使收端译码时差错概率趋于零。 时,则为临界状态临界状态,可能无失真,也可能有失真。_()LKHX_()LKHX变长编码定理 单个符号变长编码定理：单个符号变长编码定理： 若一离散无记忆信源的符号熵为H(X),每个信源符号用m进制码

24、元进行变长编码,一定存在一种无失真编码方法,其码字平均长度满足下列不等式:()()1 loglogLH XH XKmm变长编码定理 离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理 对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率 满足不等式 K()(X) LLHXKH 编码效率的下界下界： ()()log()LLLHXHXmKHXL5.2.3 最佳变长编码 最佳码： 对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长平均码长小于所有其他唯一可译码的平均长度。 香农（Shannon） 费诺（Fano） 哈夫曼（Huffma ）哈夫曼编

25、码的步骤 将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2) p(xn)取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。 对重排后的两个概率最小符号重复步骤的过程。不断继续上述过程,直到最后两个符号配以0和1为止。 从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也

26、不变,所以没有本质区别；缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。不同的编法得到的码字长度Ki也不尽相同。 在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号新符号尽可能排在靠前排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。71香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩；香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高；费诺码和哈夫曼码的

27、编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码 ；对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码。限失真信源编码定理 设离散无记忆信源X的信息率失真函数为R(D) , 当信息率 RR(D)时,只要信源序列长度 L 足够长,一定存在一种编码方法,其译码失真小于或等于 D+,为任意小的正数； 反之,若RR(D) ,则无论采用什么样的编码方法,其译码失真必大于D。常用信源编码方法 游程编码 算术编码 预测编码 变换编码74第六章 信道编码 1、信道编码的目的 2、纠错码的分类：不同的分类标准，得到不同的分类，3、从编码定理的

28、公式出发分析使得差错概率尽可能小可以采取的措施 4、掌握两种译码方法：最优译码和最大似然译码方法 5、了解如下线性分组码的相关概念：线性分组码的生成矩阵、校验矩阵、伴随式和标准阵列译码 6、了解特殊的线性分组码的特性 循环码、汉明码75第六章 信道编码 在通信系统中，要提高信息传输的有效性有效性，我们将信源的输出经过信源编码信源编码用较少的符号来表达信源消息，这些符号剩余度很小，效率很高，但对噪声干扰的抵抗能力很弱。 为了提高信息传输的准确性，使其具有较好的抵抗信道中噪声干扰的能力，需要进行信道编码信道编码。信道编码定理 上界仅与信道有关，与编码方式无关77信道编码定理 正定理：只要传信率R小

29、于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。 逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。 最佳译码，也叫最大后验概率译码(MAP) 最大似然译码( MLD) cmax (c /r)iiP cmax(r/c )iiP 线性分组码 c m G 1n 1k kn 码字 消息 生成矩阵 Ggk-1g1g0T，有k个(1n)行矢量线性分组码的形成 c = mk-1 gk-1+ m1 g1+m0 g0 Ggk-1g1g0T 当信息元确定后，码字仅由G矩阵决定，因此我们称这kn 矩阵G为该(n,k)线性分组码的生成矩阵。 系统形式(1)(1)(1)1(1)01(1)11100(1)0100100010 ; 0001kn kkkn kn kpppGI Ppppppp 系统形式生成的码字c前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。 空间构成 n维n重空间有相互正交的n个基底 选择k个基底构成码空间C 选择另外的(n-k)个基底构成空间D C和D是对偶 GHT=0