信息论总结与复习

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) （2

3、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，N+2以

5、外不关联。以外不关联。（2 2）状态、状态转移与稳态概率：）状态、状态转移与稳态概率： 状态、状态转移、状态转移图、稳定状态、稳态方程状态、状态转移、状态转移图、稳定状态、稳态方程（3 3）稳态符号概率：）稳态符号概率：1111()(|)()(|)log (|)LmLmikiikikiikikHQ E H aEQ Ep aEp aE 结论：结论：N阶马氏信源稳态信息熵阶马氏信源稳态信息熵(即极限熵即极限熵)等于等于N+1阶条件熵。阶条件熵。（4 4）稳态信息熵：）稳态信息熵：LiikikEapEQap1)|()()()|()(1lim211121NNNNXXXXHXXXXHNHN例例1 已知二

6、阶马尔可夫信源的条件概率：已知二阶马尔可夫信源的条件概率： 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； 求稳态概率、稳态符号概率、稳态符号熵和稳求稳态概率、稳态符号概率、稳态符号熵和稳态信息熵。态信息熵。解：解：二阶马氏信源关联长度二阶马氏信源关联长度=3=3，状态由，状态由2 2符号组成，共有符号组成，共有 4 4个状态，分别为：个状态，分别为：E1=00=00；E2=01=01；E3=10=10；E4=11=11； 已知的条件概率即是：已知的条件概率即是： p p(0|(0|E E1

7、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个状态符号依赖关系为：个状态符号依赖关系为： 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:

8、0.41:0.6 0:0.6稳态方程组是：稳态方程组是：1)()()()()(8 . 0)(4 . 0)()(2 . 0)(6 . 0)()(6 . 0)(2 . 0)()(4 . 0)(8 . 0)(4321424423312311EQEQEQEQEQEQEQEQEQEQEQEQEQEQEQEQ第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论可解得：可解得：61)()(31)()(3241EQEQEQEQ4141218 . 0316 . 0614 . 0612 . 031)| 1 ()() 1 (212 . 0314 . 0616 . 0618 . 031)|0

9、()()0(iiiiiiEpEQpEpEQp稳态符号概率为稳态符号概率为：稳态信息熵为：稳态信息熵为：2 4 . 0log4 . 06 . 0log6 . 0612 2 . 0log2 . 08 . 0log8 . 031H=0.895 0.895 bit/ /符号符号第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论因此，稳态符号熵因此，稳态符号熵=1=1bit/符号符号。第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论1.2 信道的信息理论: : 1 1、信道的数学模型：、信道的数学模型： 进入广义信道的符号为进入广义信道的符号为a

10、iA；从广义信道出来从广义信道出来的符号的符号bj B；其前向概率为其前向概率为 pij=p(bj|ai)。 传输矩阵传输矩阵: :msmmsspppppppppP2122221112112 2、信道的分类：、信道的分类：（1）无噪无损信道：）无噪无损信道：ai与与bj是一一对应的，是一一对应的， p (bj| |ai ) =ij ，传输矩阵为单位方阵。传输矩阵为单位方阵。（2）有噪有损信道：）有噪有损信道： ai与与bj多多- -多对应的，传输矩阵中所有的多对应的，传输矩阵中所有的矩阵元都有可能不为零。矩阵元都有可能不为零。特例是特例是BSCBSC信道信道。（3）有噪无损信道）有噪无损信道分

11、组一对多（弥散），分组一对多（弥散），传输矩阵应具有一传输矩阵应具有一行多列的分块对角化形式。行多列的分块对角化形式。（4）无噪有损信道：）无噪有损信道：分组多对一（归并），分组多对一（归并），其传输矩阵应具其传输矩阵应具有多行一列的分块对角化形式。有多行一列的分块对角化形式。（5 5）对称信道：）对称信道：传输矩阵的各行都是一些相同元素的重排，传输矩阵的各行都是一些相同元素的重排，各列也是一些相同元素的重排。各列也是一些相同元素的重排。第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论

12、3 3、信道有关的信息熵：、信道有关的信息熵：（1）信源熵）信源熵 (先验熵先验熵)： miiiapapXH1)(log()(（2）噪声熵）噪声熵 (散布度散布度)：)|(log)()|(11ijmisjjiabpbapXYH（3）联合熵：）联合熵：)(log)()(11jimisjjibapbapXYH（4）接收符号熵：）接收符号熵：mijjbpbpYH1)(log()(（5）损失熵）损失熵(后验熵后验熵)：)|(log)()|(11jimisjjibapbapYXH第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论4. 平均互信息平均互信息（1 1）平均互信息的

13、定义：平均互信息的定义：u系统完成一个符号从发到收的通信过程后，关于系统完成一个符号从发到收的通信过程后，关于符号符号ai的不确定度的变化为：的不确定度的变化为：misjijijijiapbapbapbaIEYXI11)()|(log)();();()()|(log)|(log)(log);(ijijiijiapbapbapapbaIu统计平均而言，平均每收发一对符号信宿所获得的统计平均而言，平均每收发一对符号信宿所获得的信息量为：信息量为： H(X|Y) I (X;Y) H(Y|X) 损失熵损失熵 平均互信息平均互信息 噪声熵噪声熵 H(XY)H(X) H(Y)信源熵信源熵 接收符号熵接收符

14、号熵计算公式：计算公式：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，信道传输，信道传输矩阵矩阵 ；试计算各信息熵和互信息。；试计算各信息熵和互信息。3 . 03 . 04 . 05 . 02 . 03 . 0P09. 009.

15、012. 035. 014. 021. 03 . 03 . 03 . 03 . 04 . 03 . 05 . 07 . 02 . 07 . 03 . 07 . 0)(XYP 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)联合熵：联合熵：第一部分、信息论基

16、础第一部分、信息论基础 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)接收符号熵：接收符号熵：由由mijijyxpyp1)()( P(Y)=（0.21+0.12，0.14+0.09，0.35+0.09） = （0.33, 0.23, 0.44） H(Y)= -0.33log0.33 -0.23log0.23 -0.44log0.44 =1.5366 bit/ /符号符号 (3)噪声熵：噪声熵：09. 009.

17、012. 035. 014. 021. 0)(XYP3 . 03 . 04 . 05 . 02 . 03 . 0P由由 和和第一部分、信息论基础第一部分、信息论基础 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/ /符号符号4492391144435231411744

18、. 009. 023. 009. 033. 012. 044. 035. 023. 014. 033. 021. 0)|(YXP)()()|(jjijiypyxpyxp09. 009. 012. 035. 014. 021. 0)(XYP (5)损失熵损失熵：第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论（2 2）信道容量的定义：）信道容量的定义：对于给定的信道，既然总存在一个信源能使互信对于给定的信道，既然总存在一个信源能使互信息取极大值，就可以把这个极大值定义为该信道息取极大值，就

19、可以把这个极大值定义为该信道的信道容量：的信道容量：);()(YXIMaxCxp 信道容量反映了一个信道最大所能传输的平信道容量反映了一个信道最大所能传输的平均互信息，是给定信道的属性。均互信息，是给定信道的属性。第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论（3 3）信道容量的计算：）信道容量的计算：对于简单信道要求能计算信道容量：对于简单信道要求能计算信道容量：1）无损信道：）无损信道：C = maxI(X;Y)= maxH(X)=log m ； 2）无噪信道：）无噪信道：C = maxI(X;Y)= maxH(Y)= log S ； 3）对称信道：）对称信

20、道：C=maxI(X;Y)=logS-H(p1, p2, pS)；2 . 03 . 02 . 03 . 03 . 02 . 03 . 02 . 0P 例例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.2log0.2+0.3log0.3)2 2 = 0.03 = 0.03 bit/ /符号；符号；第二部分、无失真信源编码第二部分、无失真信源编码第二部分、无失真信源编码第二部分、无失真信源编码 2.1 信源编码理论信源编码理论1.1 信源编码理论:

21、 : 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+1/8+1/16+1/64t)+1 (et)2 2、译码规则与错误概率译码规则与错误概率：（1 1）最小错误准则：选联合概率矩阵每列最大元素最小错误准则：选联合概率矩阵每列最大元素（2 2）最大似然准则：选传输概率矩阵每列最大元素最大似然准则：选传输概

22、率矩阵每列最大元素（3）错误概率计算：未选中元素的总联合概率错误概率计算：未选中元素的总联合概率（4 4）差错率计算：采用信道编码与译码后仍然不能差错率计算：采用信道编码与译码后仍然不能纠正的错误所具有的概率。也就是（纠正的错误所具有的概率。也就是（3 3）的结果。）的结果。 第三部分、信道编码第三部分、信道编码 3.1 信道编码理论信道编码理论例例7 已知已知对称信道对称信道 (1)求信道容量和最佳信求信道容量和最佳信源。源。第三部分、信道编码第三部分、信道编码 3.2 信道编码理论信道编码理论(2)在上面最佳信源分布下，按最大似然译码准则确定其译在上面最佳信源分布下，按最大似然译码准则确定

23、其译码规则，并计算错误概率。码规则，并计算错误概率。解解: :（1 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.44959193939591919395P91log9193log9395log953.2 线性分组码: : 码长为码长为n，信息位为，信息位为k ，记作（记作（n , k）

24、；）； 监督位监督位r n-k1、编码、编码 C = KG 生成矩阵生成矩阵G是是k n的矩阵。的矩阵。l左半边是左半边是kk单位信息位方阵单位信息位方阵Ikl右半边是右半边是kr的监督位矩阵的监督位矩阵Q第三部分、信道编码第三部分、信道编码 3.2 线性分组码线性分组码2、纠错和译码、纠错和译码H一致校验矩阵一致校验矩阵l左半边是左半边是rk矩阵矩阵Pl右半边是右半边是rr单位方阵单位方阵Ir；lP与生成矩阵中的与生成矩阵中的Q互为转置关系：互为转置关系：P=QT 监督方程也可表示为：监督方程也可表示为： CHT = 0；满足此方程的均为正确的许用码字满足此方程的均为正确的许用码字，否则，便

25、，否则，便是误码。是误码。第三部分、信道编码第三部分、信道编码 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为全零向量，则为全零向量，则S=0=0；l反之，若反之，若R C ，则，则E0，导致，导致S0；因此由；因此由伴随子向量伴随子向量S是否为零就能检查出接收码是否为零就能检查出接收码R是是否有误。否有误。

26、第三部分、信道编码第三部分、信道编码 3.2 线性分组码线性分组码纠错：纠错：lR错一位的情况：错一位的情况：S与与HT的哪一行相同，就的哪一行相同，就表明错在哪一位。表明错在哪一位。 lR错两位以上：查表法，错两位以上：查表法， 查查R-C对照来译码。对照来译码。3、纠错能力不等式：、纠错能力不等式： 2 r Cn0 +Cn1 + Cn2 + Cnt 完备码：上式取等号的情况。完备码：上式取等号的情况。汉明码：纠汉明码：纠1位错的完备码，位错的完备码， 2r =1+n第三部分、信道编码第三部分、信道编码 3.2 线性分组码线性分组码第四部分、限失真信源编码第四部分、限失真信源编码第四部分、限

27、失真信源编码第四部分、限失真信源编码 4.1失真度失真度4.1 4.1 失真度失真度2( ,)()ijijd u vuv平方失真：平方失真：绝对失真：绝对失真：(,) |ijijd uvuv相对失真：相对失真：|(,)|ijijiuvd uvu汉明失真：汉明失真：1( ,)( ,)0ijijijijuvd u vu vuv1、失真度的定义、失真度的定义3 3、平均符号失真度、平均符号失真度：第四部分、限失真信源编码第四部分、限失真信源编码 4.2：率失真函数：率失真函数, ( ,)() ( , )ijU VDE d u vP uv d u v4.2 4.2 率失真函数率失真函数1、保真度准则：

28、、保真度准则：预先指定一个允许失真的上预先指定一个允许失真的上限值限值D，叫做，叫做保真度保真度，要求：，要求：2、失真度矩阵失真度矩阵D：由由单符号失真度排列成，单符号失真度排列成， “行行”为发送符号，为发送符号，“列列”为接收符号。为接收符号。DD 2 2、率失真函数的定义：、率失真函数的定义：在满足保真度准则下，在满足保真度准则下，传信率传信率R的下限值是保真度的下限值是保真度D值的函数，值的函数，R(D)就就叫做率失真函数。叫做率失真函数。 );()()|(YXIDRMinDijBuvP3 3、R(D)的定义域：的定义域：4 4、R(D)的计算：的计算：0minmin DDR(Dmi

29、n) = R(0)= H(U)R (D max) = 0UVvuduPD),()(minmax（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时的最小传信率和该信源的最大平均失真度。时的最小传信率和该信源的最大平均失真度。 解：解：由汉明失真的率失真函数公式：由汉明失

30、真的率失真函数公式： 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计算计算Dmaxmax：011101110D 0.5 0.7 0.80.5 0.7 0.8 0.50.5 0.30.3 0.20.202 . 02 . 03 . 003 . 05 . 05 .

31、 00各列相加各列相加第四部分、限失真信源编码第四部分、限失真信源编码 4.2：率失真函数：率失真函数第四部分、限失真信源编码第四部分、限失真信源编码 4.3：香农三定理：香农三定理4.3 4.3 香农三个定理：香农三个定理： 三个定理各有自己管辖的范围，各指出信息率的一个理三个定理各有自己管辖的范围，各指出信息率的一个理论极限：论极限：第一定理第一定理负责无失真信源编码；负责无失真信源编码；用信息含量更浓的代码序用信息含量更浓的代码序列代替原先有冗余的信源序列。列代替原先有冗余的信源序列。定理指出定理指出无失真信源编码无失真信源编码的极限信息率的极限信息率R log m，这里这里m是编码的符

32、号个数。是编码的符号个数。第二定理第二定理负责信道编码；负责信道编码； 信道编码通过添加冗余来检错信道编码通过添加冗余来检错纠错，结果差错减少而传信率降低。纠错，结果差错减少而传信率降低。定理定理指出零差错传输指出零差错传输的的极限传信率极限传信率R C，这里这里C是信道容量。是信道容量。第三定理第三定理负责限失真信源编码；负责限失真信源编码；通过削减次要信息使传信通过削减次要信息使传信率降低。率降低。 但是要但是要满足指定的保真度，限失真信源编码的满足指定的保真度，限失真信源编码的极限传信率极限传信率R R(D)，R (D)是信源的率失真函数。是信源的率失真函数。第五部分、典型题目第五部分、

33、典型题目计算题：计算题： 1一阶马尔可夫信源的状态图如右，信源一阶马尔可夫信源的状态图如右，信源X的符号集为的符号集为0,1,2，图中，图中 。分别求：。分别求：(1)平稳后的信源概率分布；平稳后的信源概率分布；(2)信源熵信源熵H；(3)求求p=1时实际信源的熵，并说明所得结果的理由。时实际信源的熵，并说明所得结果的理由。1pp解解：(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) 且且，

34、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时，时， 理由：因为每种状态都只发两个符号，当一种符号概率为理由：因为每种状态都只发两个符号，当一种符号概率为1时，另一时，另一个必然为个必然为0，实际上只发一种确定的符号，成为确定事件，其自信，实际上只发一种确定的符号，成为确定事件，其自信息为息为0。三种状态下发出符号的自信息均为。三种状态下发出符号的自信息均为0，平均值也一定为，平均值也一定为0。因此不确定性为因此不确定性为0，所以信源熵为，所以信源熵为0。31123H()(|)()loglog ()loglog ()loglog loglogiiiQ E H X EQ EppppQ EppppQ Epppppppp0lim