信息论总结与复习.ppt

信息论与编码 总结与复习,本课程主要内容,一个理论和三个编码:理论-香农信息论 编码-信源编码 信道编码 保密编码,第一部分、信息论基础,1.1 信源的信息理论:1、信息的定义：（1）自信息 I=log(1/p)=-log p（2）信息量=通信所消除掉的不确定度=通信前的不确定度-通信后的不确定度（3）信息的单位：对数的底取2时，自信息的单位叫比特(bit)。,第一部分、信息论基础 1.1 信源的信息理论,3、信息熵的特点（1）非负性：H(X)0（2）对称性：H(p1p2)=H(p2p1)（3）极值性：1离散信源各符号等概率时出现极大值：H0=log m,第一部分、信息论基础 1.1 信源的信息理论,4、离散序列的信息熵（1）无记忆信源的联合熵与单符号熵：H(X1X2XN)=H(X1)+H(X2)+H(X3)+H(XN)=NH(X1)（2）有记忆信源的联合熵与条件熵：H(X1X2XN)=H(X1)+H(X2|X1)+H(X3|X1X2)+H(XN|X1X2XN-1)（3）平均符号熵：HN=H(X1X2XN)/N,第一部分、信息论基础 1.1 信源的信息理论,（4）序列信息熵的性质：1条件熵不大于无条件熵，强条件熵不大于弱 条件熵：H(X1)H(X2|X1)H(X3|X1X2)H(XN|X1X2XN-1)2条件熵不大于同阶的平均符号熵:HN H(XN|X1X2XN-1)3序列越长，平均每个符号的信息熵就越小：H1 H2 H3 H N总之：H0 H1 H2 H3 HN H（无记忆信源取等号。）,第一部分、信息论基础 1.1 信源的信息理论,第一部分、信息论基础 1.1 信源的信息理论,5、马尔可夫信源的信息熵（1）马尔可夫信源的数学模型和定义：N阶马尔可夫信源的关联长度是N+1，N+2以外不关联。（2）状态、状态转移与稳态概率：状态、状态转移、状态转移图、稳定状态、稳态方程（3）稳态符号概率：,结论：N阶马氏信源稳态信息熵(即极限熵)等于N+1阶条件熵。,（4）稳态信息熵：,例1 已知二阶马尔可夫信源的条件概率：p(0|00)=p(1|11)=0.8；p(0|01)=p(1|10)=0.6；求稳态概率、稳态符号概率、稳态符号熵和稳态信息熵。解：二阶马氏信源关联长度=3，状态由2符号组成，共有 4个状态，分别为：E1=00；E2=01；E3=10；E4=11；已知的条件概率即是：p(0|E1)=p(1|E4)=0.8；p(0|E2)=p(1|E3)=0.6；根据归一化条件可求出另外4个状态符号依赖关系为：p(1|E1)=p(0|E4)=0.2；p(1|E2)=p(0|E3)=0.4；,第一部分、信息论基础 1.1 信源的信息理论,稳态方程组是：,第一部分、信息论基础 1.1 信源的信息理论,可解得：,稳态符号概率为：,稳态信息熵为：,=0.895 bit/符号,第一部分、信息论基础 1.1 信源的信息理论,因此，稳态符号熵=1bit/符号。,第一部分、信息论基础 1.2 信道的信息理论,1.2 信道的信息理论:1、信道的数学模型：进入广义信道的符号为aiA；从广义信道出来的符号bj B；其前向概率为 pij=p(bj|ai)。传输矩阵:,2、信道的分类：（1）无噪无损信道：ai与bj是一一对应的，p(bj|ai)=ij，传输矩阵为单位方阵。（2）有噪有损信道：ai与bj多-多对应的，传输矩阵中所有的矩阵元都有可能不为零。特例是BSC信道。（3）有噪无损信道分组一对多（弥散），传输矩阵应具有一行多列的分块对角化形式。（4）无噪有损信道：分组多对一（归并），其传输矩阵应具有多行一列的分块对角化形式。（5）对称信道：传输矩阵的各行都是一些相同元素的重排，各列也是一些相同元素的重排。,第一部分、信息论基础 1.2 信道的信息理论,第一部分、信息论基础 1.2 信道的信息理论,3、信道有关的信息熵：（1）信源熵(先验熵)：,（2）噪声熵(散布度)：,（3）联合熵：,（4）接收符号熵：,（5）损失熵(后验熵)：,第一部分、信息论基础 1.2 信道的信息理论,4.平均互信息（1）平均互信息的定义：系统完成一个符号从发到收的通信过程后，关于符号ai的不确定度的变化为：,统计平均而言，平均每收发一对符号信宿所获得的信息量为：,计算公式：I(X;Y)=H(X)H(X|Y)=H(Y)H(Y|X)=H(X)+H(Y)H(XY),（2）平均互信息与信息熵之间的关系：,第一部分、信息论基础 1.2 信道的信息理论,第一部分、信息论基础 1.2 信道的信息理论,5.信道容量,例2已知信源先验概率p(x)=0.7,0.3，信道传输矩阵；试计算各信息熵和互信息。,H(XY)=-0.21log0.21 0.14log0.14 0.35log0.35 0.12log0.12 0.09log0.090.09log0.09=2.3924 bit/符号,解:(1)先验熵：H(X)=-0.7log20.7 0.3log20.3=(-0.7lg0.7 0.3lg0.3)/lg2=0.881 bit/符号(2)联合熵：,第一部分、信息论基础 1.2 信道的信息理论,H(Y|X)=0.21log0.3 0.14log0.2 0.35log0.5 0.12log0.4 0.09log0.30.09log0.3=1.5114 bit/符号(4)接收符号熵：由,P(Y)=（0.21+0.12，0.14+0.09，0.35+0.09）=（0.33,0.23,0.44）H(Y)=1.5366 bit/符号,(3)噪声熵：,由 和,第一部分、信息论基础 1.2 信道的信息理论,H(X|Y)=-0.21log(7/11)-0.09log(9/44)=0.8558 bit/符号 或：H(X|Y)=H(XY)-H(Y)=2.3924-1.5266=0.8558 bit/符号(6)平均互信息：I(X;Y)=H(X)-H(X|Y)=0.881 0.8558=0.0252 bit/符号,(5)损失熵：,第一部分、信息论基础 1.2 信道的信息理论,第一部分、信息论基础 1.2 信道的信息理论,（2）信道容量的定义：对于给定的信道，既然总存在一个信源能使互信息取极大值，就可以把这个极大值定义为该信道的信道容量：,信道容量反映了一个信道最大所能传输的平均互信息，是给定信道的属性。,第一部分、信息论基础 1.2 信道的信息理论,（3）信道容量的计算：对于简单信道要求能计算信道容量：1）无损信道：C=maxI(X;Y)=maxH(X)=log m；2）无噪信道：C=maxI(X;Y)=maxH(Y)=log S；3）对称信道：C=maxI(X;Y)=logS-H(p1,p2,pS)；,例3求对称信道 的信道容量。,解：C=log4-H(0.2,0.3,0.2,0.3)=2+(0.2log0.2+0.3log0.3)2=0.03 bit/符号；,第二部分、无失真信源编码,第二部分、无失真信源编码 2.1 信源编码理论,1.1 信源编码理论:1、信源的相对信息率和冗余度：（1）实际信源由于非等概，使H(X)H0=log m（2）实际信源由于有记忆，使H HN H(X)（3）信源每个符号最大可以荷载的信息量是 H0（4）平均每个符号的实际信息荷载量是H（5）只要信息熵没有达到最大值，就存在冗余。,定义相对信息率：=H/H 0 信源冗余度（或剩余度）：=1-怎样将这些冗余压缩掉？寻找一种更短的代码序列，在不损失信息的前提下，替代原来的符号序列。应当尽量使所找的编码序列各个码元相互独立且等概，就会使单位符号信息含量更多，代码就比原来更短。,第二部分、无失真信源编码 2.1 信源编码理论,第二部分、无失真信源编码 2.1 信源编码理论,2、变长码编码原理：（1）概率匹配原则：信息量大(不常出现)的符号用长码，信息量小(经常出现)的符号用短码。,（2）平均码长：,（4）极限码长=H/log r;,（5）编码效率：,（3）Shannon变长码编码定理：,第二部分、无失真信源编码 2.1 信源编码理论,3、唯一可译性与即时性：（1）断字问题：分组编码的变长码被连接起来发 送，接收端如何才能将它们分开进行译码呢？（2）唯一可译码（3）即时码（4）构造码树的方法（5）克拉夫特不等式：唯一可译码的必要条件。,例5 以下哪些编码一定不是惟一可译码？写出每种编码克拉夫特不等式的计算结果。码A：0，10，11，101；码B：1，01，001，0001；码C：0，10，110，1110，111110；解：码A：1/2+1/4+1/4+1/81，不能唯一可译；码B：1/2+1/4+1/8+1/161,有可能唯一可译；码C：1/2+1/4+1/8+1/16+1/641，有可能唯一可译；,第二部分、无失真信源编码 2.1 信源编码理论,第二部分、无失真信源编码 2.2 编码方法,1.2 编码方法:1、Huffman编码：（1）信源符号按概率大小排队。（2）合并概率最小的两个符合为一个节点。（3）节点参与排队放在与自己概率相等符号后面。（4）重复这个过程直到合并完全部符号。（5）标记每个分支的的0与1。（6）从根到叶的路径就给出了相应符号的码字。（7）计算平均码长与编码效率。,第三部分、信道编码 3.1 信道编码理论,第三部分、信道编码,3.1 信道编码理论:1、检错与纠错原理：（1）检错原理：添加冗余避免码字非此即彼；（2）纠错原理：添加冗余拉大码字汉明间距；（3）汉明距离：两码字不同码元的个数；（4）检错能力：d0e+1 纠错能力：d02t+1 纠检同时：d0e+t+1(et),2、译码规则与错误概率：（1）最小错误准则：选联合概率矩阵每列最大元素（2）最大似然准则：选传输概率矩阵每列最大元素（3）错误概率计算：未选中元素的总联合概率（4）差错率计算：采用信道编码与译码后仍然不能纠正的错误所具有的概率。也就是（3）的结果。,第三部分、信道编码 3.1 信道编码理论,例7 已知对称信道(1)求信道容量和最佳信源。,第三部分、信道编码 3.2 信道编码理论,(2)在上面最佳信源分布下，按最大似然译码准则确定其译码规则，并计算错误概率。解:（1）最佳输入为等概率分布。信道容量为：C=logS-H(p1,p2,p3)=log3-,=1.5850-1.3516=0.2334 bit/符号（2）译码规则:F(b1)=a1;F(b2)=a2;F(b3)=a3;错误概率：PE=3(3/9+1/9)/3=4/9=0.44,3.2 线性分组码:码长为n，信息位为k，记作（n,k）；监督位r n-k1、编码 C=KG 生成矩阵G是k n的矩阵。左半边是kk单位信息位方阵Ik右半边是kr的监督位矩阵Q,第三部分、信道编码 3.2 线性分组码,2、纠错和译码H一致校验矩阵左半边是rk矩阵P右半边是rr单位方阵Ir；P与生成矩阵中的Q互为转置关系：P=QT 监督方程也可表示为：CHT=0；满足此方程的均为正确的许用码字，否则，便是误码。,第三部分、信道编码 3.2 线性分组码,N 维错误格式矢量 E 发送码字为C，接收码字为R，三者的关系是：E=C R；R=C E；C=R E；伴随子向量 S=RHT S=RHT=(C E)HT=CHT EHT=EHT；若R=C，E为全零向量，则S=0；反之，若R C，则E0，导致S0；因此由伴随子向量S是否为零就能检查出接收码R是否有误。,第三部分、信道编码 3.2 线性分组码,纠错：R错一位的情况：S与HT的哪一行相同，就表明错在哪一位。R错两位以上：查表法，查R-C对照来译码。3、纠错能力不等式：2 r Cn0+Cn1+Cn2+Cnt 完备码：上式取等号的情况。汉明码：纠1位错的完备码，2r=1+n,第三部分、信道编码 3.2 线性分组码,第四部分、限失真信源编码,第四部分、限失真信源编码 4.1失真度,4.1 失真度,平方失真：,绝对失真：,相对失真：,汉明失真：,1、失真度的定义,3、平均符号失真度：,第四部分、限失真信源编码 4.2：率失真函数,4.2 率失真函数,1、保真度准则：预先指定一个允许失真的上限值D，叫做保真度，要求：,2、失真度矩阵D：由单符号失真度排列成，“行”为发送符号，“列”为接收符号。,2、率失真函数的定义：在满足保真度准则下，传信率R的下限值是保真度D值的函数，R(D)就叫做率失真函数。,3、R(D)的定义域：,4、R(D)的计算：,R(Dmin)=R(0)=H(U),R(D max)=0,（1）一般情况，按定义：,（2）特殊情况，汉明失真：,R(D)=minI(U;V)=H(U)-H(D)-D log(r-1),第四部分、限失真信源编码 4.2：率失真函数,例11 已知信源概率为：p(X)=(0.5,0.3,0.2),，求汉明失真下保真度D=0.3时的最小传信率和该信源的最大平均失真度。解：由汉明失真的率失真函数公式：R(D)=H(X)-H(D)-Dlog(r-1)H(X)=-0.5log0.5-0.3log0.3-0.2log2=1.4855 当D=0.3时，H(D)=-0.3log0.3-0.7log0.7=0.8813 最小传信率：R(0.3)=1.4855-0.8813-0.3log2=0.3042；,所以 D max=min 0.5,0.7,0.8=0.5,计算Dmax：,0.5 0.7 0.8,各列相加,第四部分、限失真信源编码 4.2：率失真函数,第四部分、限失真信源编码 4.3：香农三定理,4.3 香农三个定理：,三个定理各有自己管辖的范围，各指出信息率的一个理论极限：第一定理负责无失真信源编码；用信息含量更浓的代码序列代替原先有冗余的信源序列。定理指出无失真信源编码的极限信息率R log m，这里m是编码的符号个数。第二定理负责信道编码；信道编码通过添加冗余来检错纠错，结果差错减少而传信率降低。定理指出零差错传输的极限传信率R C，这里C是信道容量。第三定理负责限失真信源编码；通过削减次要信息使传信率降低。但是要满足指定的保真度，限失真信源编码的极限传信率R R(D)，R(D)是信源的率失真函数。,第五部分、典型题目,计算题：1一阶马尔可夫信源的状态图如右，信源X的符号集为0,1,2，图中。分别求：(1)平稳后的信源概率分布；(2)信源熵H；(3)求p=1时实际信源的熵，并说明所得结果的理由。,解：(1)一阶马尔可夫信源，状态为单个符号，信源符号集为X=0,1,2，E1=0,E2=1,E3=2,稳态概率满足：Q(0)=p Q(0)(1-p)Q(1)Q(1)=p Q(2)(1-p)Q(1)且，Q(0)+Q(1)Q(2)1解方程：Q(0)1/3；Q(1)1/3；Q(2)1/3；(2)(3)实际信源熵为H。p=0时，理由：因为每种状态都只发两个符号，当一种符号概率为1时，另一个必然为0，实际上只发一种确定的符号，成为确定事件，其自信息为0。三种状态下发出符号的自信息均为0，平均值也一定为0。因此不确定性为0，所以信源熵为0。,2.二元无记忆信源发出a、b两个符号，概率分别为0.7和0.3，试用三次扩展信源进行编码。解：根据 p(x1x2x3)=p(x1)p(x2)p(x3)不难求出三次扩展信源的概率空间为：,按8个符号的概率排队，进行赫付曼编码,第五部分、典型题目,1 0 1 0 1 0 1 0 1 0 1 0 1 0,1011 1010 1001 1000 011 010 11 00 码字,4 4 4 4 3 3 2 2码长,第五部分、典型题目,码字 00 11 010 011 1000 1001 1010 1011 码长 2 2 3 3 4 4 4 4 码字平均长度：LN=2.726；信源符号平均编码长度：,信源信息熵:H(X)=-0.3log0.3-0.7log0.7=0.881编码效率：=0.881/0.909=96.9%,第五部分、典型题目,全面复习 重点掌握 重视概念 细心运算 动手动脑 不存侥幸祝大家取得满意的考试成绩！,