《信息论总结与复习》由会员分享，可在线阅读，更多相关《信息论总结与复习（45页珍藏版）》请在金锄头文库上搜索。
1、信息论与编码信息论与编码 总结与复习总结与复习本课程本课程主要内容主要内容一个理论和三个编码: : 理论-香农信息论 编码-信源编码 信道编码 保密编码 第一部分、信息论基础第一部分、信息论基础1.1 信源的信息理论: : 1 1、信息的定义：、信息的定义： （1 1）自信息）自信息 I = log(1/p) =- -log p （2 2）信息量信息量=通信所消除掉的不确定度通信所消除掉的不确定度 =通信前的不确定度通信前的不确定度-通信后的不确定度通信后的不确定度 （3 3）信息的单位：对数的底取）信息的单位：对数的底取2时，时，自信息自信息的单位叫比特的单位叫比特( (bit)。第一部分、
2、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论3 3、信息熵的特点、信息熵的特点（1 1）非负性：）非负性：H(X) 0（2 2）对称性：对称性：H(p1p2)=H(p2p1)（3 3）极值性：）极值性： 1离散信源各符号等概率时出现极大值：离散信源各符号等概率时出现极大值： H0=log m 第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论4 4、离散序列的信息熵、离散序列的信息熵（1 1）无记忆信源的联合熵与单符号熵：）无记忆信源的联合熵与单符号熵： H(X1X2XN) = H(X1)+H(X2)+H(X3)+H (XN) = NH(X1
3、) （2 2）有记忆信源的联合熵与有记忆信源的联合熵与条件条件熵：熵： H(X1X2XN)=H(X1) + H(X2|X1) + H(X3|X1X2) + +H (XN|X1X2XN-1)（3 3）平均符号熵：平均符号熵： HN =H(X1X2XN) / N第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论（4 4）序列信息熵的性质：）序列信息熵的性质： 1条件熵不大于无条件熵，强条件熵不大于弱条件熵不大于无条件熵，强条件熵不大于弱 条件熵：条件熵：H(X1) H(X2|X1) H(X3|X1X2) H (XN|X1X2XN-1)2条件熵不大于同阶的平均符号熵条件熵
4、不大于同阶的平均符号熵: : HN H (XN|X1X2XN-1) 3序列越长，平均每个符号的信息熵就越小：序列越长，平均每个符号的信息熵就越小： H1 H2 H3 H N总之：总之：H0 H1 H2 H3 HN H （无记忆信源取等号。）（无记忆信源取等号。）第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论5 5、马尔可夫信源的信息熵、马尔可夫信源的信息熵（1 1）马尔可夫信源的数学模型和定义：马尔可夫信源的数学模型和定义： N阶阶马尔可夫信源的关联长度是马尔可夫信源的关联长度是N+1
5、，N+2以外不关联。以外不关联。（2 2）状态、状态转移与稳态概率：）状态、状态转移与稳态概率： 状态、状态转移、状态转移图、稳定状态、稳态方程状态、状态转移、状态转移图、稳定状态、稳态方程（3 3）稳态符号概率：）稳态符号概率：结论：结论：N阶马氏信源稳态信息熵阶马氏信源稳态信息熵(即极限熵即极限熵)等于等于N+1阶条件熵。阶条件熵。（4 4）稳态信息熵：）稳态信息熵：例例1 已知二阶马尔可夫信源的条件概率：已知二阶马尔可夫信源的条件概率： p(0|00)=(0|00)=p(1|11)=0.8(1|11)=0.8；p(0|01)=(0|01)=p(1|10)=0.6(1|10)=0.6； 求
6、求稳稳态态概概率率、稳稳态态符符号号概概率率、稳稳态态符符号号熵熵和和稳稳态信息熵。态信息熵。解：解：二阶马氏信源关联长度二阶马氏信源关联长度=3=3，状态由，状态由2 2符号组成，共有符号组成，共有 4 4个状态，分别为：个状态，分别为：E1=00=00；E2=01=01；E3=10=10；E4=11=11； 已知的条件概率即是：已知的条件概率即是： p p(0|(0|E E1 1)=)=p p(1|(1|E E4 4 )=0.8)=0.8；p p(0|E(0|E2 2)=)=p p(1|(1|E E3 3 )=0.6)=0.6； 根据归一化条件可求出另外根据归一化条件可求出另外4 4个状态
7、符号依赖关系为：个状态符号依赖关系为： p p(1|(1|E E1 1)=)=p p(0|(0|E E4 4 )=0.2)=0.2；p p(1|(1|E E2 2 )=)=p p(0|(0|E E3 3 )=0.4)=0.4； 第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论E4E3E2E10:0.8 0:0.4 0:0.2 1:0.81:0.2 1:0.41:0.6 0:0.6稳态方程方程组是：是：第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论可解得：可解得：稳态符号概率为稳态符号概率为：稳态信息熵为：稳态信息熵为：=0.895
8、0.895 bit/ /符号符号第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论因此，稳态符号熵因此，稳态符号熵=1=1bit/符号符号。第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论1.2 信道的信息理论: : 1 1、信道的数学模型：、信道的数学模型： 进入广义信道的符号为进入广义信道的符号为aiA；从广义信道出来；从广义信道出来的符号的符号bj B；其前向概率为；其前向概率为 pij=p(bj|ai)。 传输矩阵传输矩阵: :2 2、信道的分类：、信道的分类：（1）无噪无损信道：）无噪无损信道：ai与与bj是一一对应的，是一一
9、对应的， p (bj| |ai ) =ij ，传传输矩阵为单位方阵。输矩阵为单位方阵。（2）有有噪噪有有损损信信道道： ai与与bj多多- -多多对对应应的的，传传输输矩矩阵阵中中所所有有的的矩阵元都有可能不为零。矩阵元都有可能不为零。特例是特例是BSCBSC信道信道。（3）有有噪噪无无损损信信道道分分组组一一对对多多（弥弥散散），传传输输矩矩阵阵应应具具有有一一行多列的分块对角化形式。行多列的分块对角化形式。（4）无噪有损信道：）无噪有损信道：分组多对一（归并），分组多对一（归并），其传输矩阵应具其传输矩阵应具有多行一列的分块对角化形式。有多行一列的分块对角化形式。（5 5）对对称称信信道道
10、：传传输输矩矩阵阵的的各各行行都都是是一一些些相相同同元元素素的的重重排排，各列也是一些相同元素的重排。各列也是一些相同元素的重排。第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论 3 3、信道有关的信息熵：、信道有关的信息熵：（1）信源熵）信源熵 (先验熵先验熵)： （2）噪声熵）噪声熵 (散布度散布度)：（3）联合熵：）联合熵：（4）接收符号熵：）接收符号熵：（5）损失熵）损失熵(后验熵后验熵)：第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论4. 平均
11、互信息平均互信息（1 1）平均互信息的定义：平均互信息的定义：u系系统统完完成成一一个个符符号号从从发发到到收收的的通通信信过过程程后后，关关于于符号符号ai的不确定度的变化为：的不确定度的变化为：u统计平均而言，平均每收发一对符号信宿所获得的统计平均而言，平均每收发一对符号信宿所获得的信息量为：信息量为： H(X|Y) I (X;Y) H(Y|X) 损失熵损失熵 平均互信息平均互信息 噪声熵噪声熵 H(XY)H(X) H(Y)信源熵信源熵 接收符号熵接收符号熵计算公式：计算公式：I (X;Y) = H(X) H(X|Y)= H(Y) H(Y|X)= H(X) +H(Y)H(XY) （2）平均
12、互信息与信息熵之间的关系：）平均互信息与信息熵之间的关系：第一部分、信息论基础第一部分、信息论基础 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) )先
13、验熵：先验熵： 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,
14、0.44） H(Y)= -0.33log0.33 -0.23log0.23 -0.44log0.44 =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/ /符号
15、符号 (5)损失熵损失熵：第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论（2 2）信道容量的定义：）信道容量的定义：对对于于给给定定的的信信道道，既既然然总总存存在在一一个个信信源源能能使使互互信信息息取取极极大大值值，就就可可以以把把这这个个极极大大值值定定义义为为该该信信道道的信道容量：的信道容量： 信信道道容容量量反反映映了了一一个个信信道道最最大大所所能能传传输输的的平平均均互信息，是给定信道的属性。互信息，是给定信道的属性。第一部分、信息论基础第一部分、信息论基础 1.2 信
16、道的信息理论信道的信息理论（3 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)； 例例33求对称信道 的信道容量。解：解：C =log4-=log4-H(0.2,0.3,0.2,0.3)(0.2,0.3,0.2,0.3) =2+(0.2log0.2+0.3log0.3)2 = 0
17、.03 =2+(0.2log0.2+0.3log0.3)2 = 0.03 bit/ /符号；符号；第二部分、无失真信源编码第二部分、无失真信源编码第二部分、无失真信源编码第二部分、无失真信源编码 2.1 信源编码理论信源编码理论1.1 信源编码理论: : 1 1、信源的相对信息率和冗余度信源的相对信息率和冗余度： （1 1）实际信源由于）实际信源由于非等概，使非等概，使H(X)H0=log m （2 2）实际信源由于）实际信源由于有记忆，使有记忆，使H HN1，不能唯一可译；，不能唯一可译； 码码B： 1/2+1/4+1/8+1/161,有可能唯一可译；有可能唯一可译； 码码C：1/2+1/4
18、+1/8+1/16+1/64t)+1 (et)2 2、译码规则与错误概率译码规则与错误概率：（1 1）最小错误准则：选联合概率矩阵每列最大元素）最小错误准则：选联合概率矩阵每列最大元素（2 2）最大似然准则：选传输概率矩阵每列最大元素）最大似然准则：选传输概率矩阵每列最大元素（3）错误概率计算：未选中元素的总联合概率错误概率计算：未选中元素的总联合概率（4 4）差错率计算：采用信道编码与译码后仍然不能）差错率计算：采用信道编码与译码后仍然不能纠正的错误所具有的概率。也就是（纠正的错误所具有的概率。也就是（3 3）的结果。）的结果。 第三部分、信道编码第三部分、信道编码 3.1 信道编码理论信道
19、编码理论例例7 已知已知对称信道对称信道 (1)求信道容量和最佳信求信道容量和最佳信源。源。第三部分、信道编码第三部分、信道编码 3.2 信道编码理论信道编码理论(2)在上面最佳信源分布下，按最大似然译码准则确定其译在上面最佳信源分布下，按最大似然译码准则确定其译码规则，并计算错误概率。码规则，并计算错误概率。解解: :（1 1）最佳输入为等概率分布。信道容量为：最佳输入为等概率分布。信道容量为： C=logS-H(p1, p2, p3)=log3 - =1.5850- -1.3516 =0.2334 bit/符号符号 （2）译码规则）译码规则: F(b1)=a1 ; F(b2)=a2 ; F
20、(b3)=a3 ; 错误概率：错误概率：PE=3(3/9+1/9) /3=4/9=0.443.2 线性分组码: : 码长为码长为n，信息位为，信息位为k ，记作（记作（n , k）；）； 监督位监督位r n-k1、编码、编码 C = KG 生成矩阵生成矩阵G是是k n的矩阵。的矩阵。l左半边是左半边是kk单位信息位方阵单位信息位方阵Ikl右半边是右半边是kr的监督位矩阵的监督位矩阵Q第三部分、信道编码第三部分、信道编码 3.2 线性分组码线性分组码2、纠错和译码、纠错和译码H一致校验矩阵一致校验矩阵l左半边是左半边是rk矩阵矩阵Pl右半边是右半边是rr单位方阵单位方阵Ir；lP与生成矩阵中的与
21、生成矩阵中的Q互为转置关系：互为转置关系：P=QT 监督方程也可表示为：监督方程也可表示为： CHT = 0；满足此方程的均为正确的许用码字满足此方程的均为正确的许用码字，否则，便，否则，便是误码。是误码。第三部分、信道编码第三部分、信道编码 3.2 线性分组码线性分组码N 维错误格式矢量维错误格式矢量 E 发送码字为发送码字为C，接收码字为，接收码字为R ，三者的关系是：三者的关系是： E = C R； R = C E； C =R E；伴随子向量伴随子向量 S S = = RHT S= RHT = (C E) HT = CHT EHT = EHT；l若若R = C，E为全零向量，则为全零向量
22、，则S=0=0；l反之，若反之，若R C ，则，则E0，导致，导致S0；因此由；因此由伴随子向量伴随子向量S是否为零就能检查出接收码是否为零就能检查出接收码R是是否有误。否有误。 第三部分、信道编码第三部分、信道编码 3.2 线性分组码线性分组码纠错：纠错：lR错一位的情况：错一位的情况：S与与HT的哪一行相同，就的哪一行相同，就表明错在哪一位。表明错在哪一位。 lR错两位以上：查表法，错两位以上：查表法， 查查R-C对照来译码。对照来译码。3、纠错能力不等式：、纠错能力不等式： 2 r Cn0 +Cn1 + Cn2 + Cnt 完备码：上式取等号的情况。完备码：上式取等号的情况。汉明码：纠汉
23、明码：纠1位错的完备码，位错的完备码， 2r =1+n第三部分、信道编码第三部分、信道编码 3.2 线性分组码线性分组码第四部分、限失真信源编码第四部分、限失真信源编码第四部分、限失真信源编码第四部分、限失真信源编码 4.1失真度失真度4.1 4.1 失真度失真度平方失真：平方失真：绝对失真：绝对失真：相对失真：相对失真：汉明失真：汉明失真：1、失真度的定义、失真度的定义3 3、平均符号失真度：、平均符号失真度：第四部分、限失真信源编码第四部分、限失真信源编码 4.2：率失真函数：率失真函数4.2 4.2 率失真函数率失真函数1、保真度准则：、保真度准则：预先指定一个允许失真的上限预先指定一个
24、允许失真的上限值值D，叫做，叫做保真度保真度，要求：，要求：2、失真度矩阵失真度矩阵D：由由单符号失真度排列成，单符号失真度排列成， “行行”为发送符号，为发送符号，“列列”为接收符号。为接收符号。2 2、率失真函数的定义：、率失真函数的定义：在满足保真度准则下，在满足保真度准则下，传信率传信率R的下限值是保真度的下限值是保真度D值的函数，值的函数，R(D)就就叫做率失真函数。叫做率失真函数。 3 3、R(D)的定义域：的定义域：4 4、R(D)的计算：的计算：R(Dmin) = R(0)= H(U)R (D max) = 0（1）一般情况，按定义：）一般情况，按定义：（2）特殊情况，汉明失真
25、：）特殊情况，汉明失真：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=
26、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计算计算Dmaxmax： 0.5 0.7 0.80.5 0.7 0.8 0.50.5 0.30.3 0.20.2各列相加各列相加第四部分、限失真信源编码第四部分、限失真信源编码 4.2：率失真函数：率失真函数第四部分、限失真信源编码第四部分、限失真信源编码 4.3：香农三定理：香农三定理4.3 4.3 香农三个定理：香农三个定理： 三个定理各有自己管辖
27、的范围，各指出信息率的一个理三个定理各有自己管辖的范围，各指出信息率的一个理论极限：论极限：第一定理第一定理负责无失真信源编码；负责无失真信源编码；用信息含量更浓的代码序用信息含量更浓的代码序列代替原先有冗余的信源序列。定理指出列代替原先有冗余的信源序列。定理指出无失真信源编码无失真信源编码的极限信息率的极限信息率R log m，这里这里m是编码的符号个数。是编码的符号个数。第二定理第二定理负责信道编码；负责信道编码； 信道编码通过添加冗余来检错信道编码通过添加冗余来检错纠错，结果差错减少而传信率降低。纠错，结果差错减少而传信率降低。定理指出零差错传输定理指出零差错传输的的极限传信率极限传信率
28、R C，这里这里C是信道容量。是信道容量。第三定理第三定理负责限失真信源编码；负责限失真信源编码；通过削减次要信息使传信通过削减次要信息使传信率降低。率降低。 但是要但是要满足指定的保真度，限失真信源编码的满足指定的保真度，限失真信源编码的极限传信率极限传信率R R(D)，R (D)是信源的率失真函数。是信源的率失真函数。第五部分、典型题目第五部分、典型题目计算题：计算题： 1一阶马尔可夫信源的状态图如右，信源一阶马尔可夫信源的状态图如右，信源X的符号集为的符号集为0,1,2，图中，图中 。分别求：。分别求：(1)平稳后的信源概率分布；平稳后的信源概率分布；(2)信源熵信源熵H；(3)求求p=
29、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)(2) (3) 实际信源熵为实际信源熵为H。p=0时，时， 理由：因为每种状态都只发两个符号，当一种符号概率为理由：因为每种状态都只发两个符号，当一种符号概率为
30、1时，另一时，另一个必然为个必然为0，实际上只发一种确定的符号，成为确定事件，其自信，实际上只发一种确定的符号，成为确定事件，其自信息为息为0。三种状态下发出符号的自信息均为。三种状态下发出符号的自信息均为0，平均值也一定为，平均值也一定为0。因此不确定性为因此不确定性为0，所以信源熵为，所以信源熵为0。2.2.二二元元无无记忆信信源源发出出a、b两两个个符符号号，概概率率分分别为0.7和和0.3，试用试用三次三次扩展信源展信源进行编码。进行编码。解解：根根据据 p(x1x2x3)=p(x1)p(x2)p(x3) 不不难难求求出出三三次次扩展信源的概率空展信源的概率空间为： 按按8 8个符号的
31、概率排队，进行赫付曼编码个符号的概率排队，进行赫付曼编码第五部分、典型题目第五部分、典型题目 bbb 0.0270.027 bba 0.0630.063 bab 0.0630.063 abb 0.0630.063 (0.09)(0.09)(0.126)(0.126) baa 0.1470.147 aba 0.1470.147 aab 0.1470.147 (0.216)(0.216)(0.294)(0.294)aaa 0.3430.343 (0.363)(0.363) 0.6370.637 root 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
32、 1 1 0 0 1011 1011 1010 1010 1001 1001 1000 1000 011 011 010 010 11 11 00 00 码字码字 4 4 4 4 4 4 4 4 3 3 3 3 2 2 2 2码长码长第五部分、典型题目第五部分、典型题目 码字码字 00 11 010 011 1000 1001 1010 1011 00 11 010 011 1000 1001 1010 1011 码长码长 2 2 3 3 4 4 4 4 2 2 3 3 4 4 4 4 码字平均长度：码字平均长度： L LN N=2.726=2.726； 信源符号平均信源符号平均编码长度：度：信源信息熵信源信息熵: : H( (X)=-0.3log0.3-0.7log0.7=0.881编码效率：编码效率：=0.881/0.909=96.9=0.881/0.909=96.9%第五部分、典型题目第五部分、典型题目全面复习全面复习 重点掌握重点掌握 重视概念重视概念 细心运算细心运算 动手动脑动手动脑 不存侥幸不存侥幸祝大家取得满意的考试成绩！祝大家取得满意的考试成绩！
