信息论与编码期末复习

1、信息论与编码复习信息论与编码复习2013版版信息论与编码信息论与编码的主要内容的主要内容一个理论和三个编码: : 理论-香农信息论 编码-信源编码 信道编码 保密编码（了解） 第一部分、信息论基础第一部分、信息论基础1.1 信源的信息理论: : 1 1、信息的定义：、信息的定义： （1 1）自信息）自信息 I = log(1/p) =- -log p （2 2）信息量信息量=通信所消除掉的不确定度通信所消除掉的不确定度 =通信前的不确定度通信前的不确定度-通信后的不确定度通信后的不确定度 （3 3）信息的单位：对数的底取）信息的单位：对数的底取2时，时，自信自信息的单位叫比特息的单位叫比特(

2、(bit)。第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论2 2、信息熵的定义：、信息熵的定义： （1 1）离散信源离散信源miiimimiiiippippIpXH111log1log)(（2 2）连续信源）连续信源dxxpxpxh)(log)()(第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论3 3、信息熵的特点、信息熵的特点（1 1）非负性：）非负性：H(X) 0（2 2）对称性：对称性：H(p1p2)=H(p2p1)（3 3）极值性：）极值性： 1离散信源各符号等概率时出现极大值：离散信源各符号等概率时出现极大值： H0=l

3、og m 2连续信源信号幅度受限时均匀分布出现连续信源信号幅度受限时均匀分布出现 极大值：极大值： hmax( (X)=)=log (b-a)； 3连续信源信号方差有限时高斯分布出现连续信源信号方差有限时高斯分布出现 极大值：极大值：)2(log21)(2maxeXh第一部分、信息论基础第一部分、信息论基础 1.1 信源的信息理论信源的信息理论4 4、离散序列的信息熵、离散序列的信息熵（1 1）无记忆信源的联合熵与单符号熵：）无记忆信源的联合熵与单符号熵： H(X1X2XN) = H(X1)+H(X2)+H(X3)+H (XN) = NH(X1) （2 2）有记忆信源的联合熵与有记忆信源的联合

4、熵与条件条件熵：熵： 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条件熵不大于同阶的平均符号熵条件熵不大于同阶的平均符号熵: : HN H (XN|X

5、1X2XN-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以外不关联。以外不关联。（2 2）状态、状

6、态转移与稳态概率：）状态、状态转移与稳态概率： 状态、状态转移、状态转移图、稳定状态、稳态方程状态、状态转移、状态转移图、稳定状态、稳态方程（3 3）稳态符号概率：）稳态符号概率：1111()(|)()(|)log (|)LmLmikiikikiikikHQ E H aEQ Ep aEp aE 结论：结论：N阶马氏信源稳态信息熵阶马氏信源稳态信息熵(即极限熵即极限熵)等于等于N+1阶条件熵。阶条件熵。（4 4）稳态信息熵：）稳态信息熵：LiikikEapEQap1)|()()()|()(1lim211121NNNNXXXXHXXXXHNHN第一部分、信息论基础第一部分、信息论基础 1.2 信道

7、的信息理论信道的信息理论1.2 信道的信息理论: : 1 1、信道的数学模型：、信道的数学模型： 进入广义信道的符号为进入广义信道的符号为aiA；从广义信道出来；从广义信道出来的符号的符号bj B；其前向概率为；其前向概率为 pij=p(bj|ai)。 传输矩阵传输矩阵: :msmmsspppppppppP2122221112112 2、信道的分类：、信道的分类：（1）无噪无损信道：）无噪无损信道：ai与与bj是一一对应的，是一一对应的， p (bj| |ai ) =ij ，传输矩阵为单位方阵。传输矩阵为单位方阵。（2）有噪有损信道：）有噪有损信道： ai与与bj多多- -多对应的，传输矩阵中

8、所有的多对应的，传输矩阵中所有的矩阵元都有可能不为零。矩阵元都有可能不为零。特例是特例是BSCBSC信道和信道和BECBEC信道信道。（3）有噪无损信道）有噪无损信道分组一对多（弥散），分组一对多（弥散），传输矩阵应具有一传输矩阵应具有一行多列的分块对角化形式。行多列的分块对角化形式。（4）无噪有损信道：）无噪有损信道：分组多对一（归并），分组多对一（归并），其传输矩阵应具其传输矩阵应具有多行一列的分块对角化形式。有多行一列的分块对角化形式。（5 5）对称信道：）对称信道：传输矩阵的各行都是一些相同元素的重排，传输矩阵的各行都是一些相同元素的重排，各列也是一些相同元素的重排。各列也是一些相同元

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

10、|(11jimisjjibapbapYXH第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论4. 平均互信息平均互信息（1 1）平均互信息的定义：平均互信息的定义：u系统完成一个符号从发到收的通信过程后，关于系统完成一个符号从发到收的通信过程后，关于符号符号ai的不确定度的变化为：的不确定度的变化为：misjijijijiapbapbapbaIEYXI11)()|(log)();();()()|(log)|(log)(log);(ijijiijiapbapbapapbaIu统计平均而言，平均每收发一对符号信宿所获得的统计平均而言，平均每收发一对符号信宿所获得的信息量

11、为：信息量为： 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）平均互信息与信息熵之间的关系：）平均互信息与信息熵之间的关系：第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论 H(Y | X)= 0.21log0.3 0.14log0.2 0.35log0.5 0.12log0.4 0.09log0.30.09log0.3 = 1

12、.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. 012. 035. 014. 021. 0)(XYP3 . 03 . 04 . 05 . 02 . 03 . 0P由由 和和第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论 H(X|Y)=

13、 -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. 009. 023. 009. 033. 012. 044. 035. 023. 014. 033. 021. 0)|(YXP)()()|(jjijiypyxpyxp09. 009. 012. 035. 014. 0

14、21. 0)(XYP (5)损失熵损失熵：第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论5. 信道容量信道容量（1 1）传码率与传信率：）传码率与传信率： 单位时间信道传输的码元数量叫做传码率，用单位时间信道传输的码元数量叫做传码率，用 RB（每秒符号数）表示，也叫波特率。（每秒符号数）表示，也叫波特率。 单位时间信道传输的净信息量值叫做传信率，单位时间信道传输的净信息量值叫做传信率，用用Rb（每秒信息量）表示，也叫比特率。显然：（每秒信息量）表示，也叫比特率。显然： Rb= I(X;

15、Y)RB 第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论（2 2）信道容量的定义：）信道容量的定义：对于给定的信道，既然总存在一个信源能使互信对于给定的信道，既然总存在一个信源能使互信息取极大值，就可以把这个极大值定义为该信道息取极大值，就可以把这个极大值定义为该信道的信道容量：的信道容量：);()(YXIMaxCxp 有时，也把单位时间的最大传信率定义为信道有时，也把单位时间的最大传信率定义为信道容量，记做容量，记做Ct =C RB； 信道容量反映了一个信道最大所能传输的平信道容量反映了一个信道最大所能传输的平均互信息，是给定信道的属性。均互信息，是给定信道的

16、属性。第一部分、信息论基础第一部分、信息论基础 1.2 信道的信息理论信道的信息理论（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)；2 . 03 . 02 . 03 . 03 . 02 . 03 . 02 . 0P 例例33求对称信道 的信道容量。解：解：C =log4-=

17、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 = 0.03 2 = 0.03 bit/ /符号；符号；第二部分、无失真信源编码第二部分、无失真信源编码第二部分、无失真信源编码第二部分、无失真信源编码 2.1 信源编码理论信源编码理论1.1 信源编码理论: : 1 1、信源的相对信息率和冗余度信源的相对信息率和冗余度： （1 1）实际信源由于）实际信源由于非等概，使非等概，使H(X)H0=log m （2 2）实际信源由于）实际信源由于有记忆，使有记忆，使H

18、HN H(X) （3）信源每个符号最大可以荷载的信息量是信源每个符号最大可以荷载的信息量是 H0 0 （4 4）平均每个符号的实际信息荷载量是）平均每个符号的实际信息荷载量是H （5）只要）只要信息熵没有达到最大值，就存在冗余信息熵没有达到最大值，就存在冗余。 （6）冗余分布在各符号中）冗余分布在各符号中, 并非有了几个没用符号并非有了几个没用符号。定义相对信息率：定义相对信息率： = = H/ /H 0 0 信源冗余度（或剩余度）：信源冗余度（或剩余度）： =1-=1-怎样将这些冗余压缩掉？怎样将这些冗余压缩掉？寻找一种更短的代码序列寻找一种更短的代码序列，在不损失信息的前提，在不损失信息的

19、前提下，替代原来的符号序列。下，替代原来的符号序列。v应当应当尽量使所找的编码序列各个码元相互独立且尽量使所找的编码序列各个码元相互独立且等概等概，就会使单位符号信息含量更多，代码就比，就会使单位符号信息含量更多，代码就比原来更短。原来更短。第二部分、无失真信源编码第二部分、无失真信源编码 2.1 信源编码理论信源编码理论第二部分、无失真信源编码第二部分、无失真信源编码 2.1 信源编码理论信源编码理论 2 2、变长码编码原理：变长码编码原理： （1 1）概率匹配原则：）概率匹配原则：信息量大信息量大( (不常出现不常出现) )的符号的符号用长码，信息量小用长码，信息量小( (经常出现经常出现

20、) )的符号用短码。的符号用短码。)(1logiririaIpl（2 2）平均码长：）平均码长：imiilpl1ll（4）极限码长极限码长 = =H / log r；其中其中log r是极限信息率是极限信息率lo gHlr（5 5）编码效率编码效率：NrHrHNNl1loglog（3）Shannon变长码编码定理：变长码编码定理：第二部分、无失真信源编码第二部分、无失真信源编码 2.1 信源编码理论信源编码理论 3 3、唯一可译性与即时性：唯一可译性与即时性：（1 1）断字问题：）断字问题：分组编码的分组编码的变长码被连接起来发变长码被连接起来发 送，接收端如何才能将它们分开进行译码呢？送，接

21、收端如何才能将它们分开进行译码呢？（2 2）唯一可译码）唯一可译码（3 3）即时码）即时码（4 4）构造码树的方法）构造码树的方法（5 5）克拉夫特不等式：唯一可译码的必要条件。）克拉夫特不等式：唯一可译码的必要条件。第二部分、无失真信源编码第二部分、无失真信源编码 2.2 编码方法编码方法1.2 编码方法: : 1 1、HuffmanHuffman编码编码： （1 1）信源符号按概率大小排队。）信源符号按概率大小排队。 （2 2）合并概率最小的两个符合为一个节点。）合并概率最小的两个符合为一个节点。 （3）节点参与排队放在与自己概率相等符号后面节点参与排队放在与自己概率相等符号后面。 （4

22、4）重复这个过程直到合并完全部符号。）重复这个过程直到合并完全部符号。 （5）标记每个分支的的）标记每个分支的的0与与1。 （6 6）从根到叶的路径就给出了相应符号的码字。从根到叶的路径就给出了相应符号的码字。 （7）计算平均码长与编码效率。）计算平均码长与编码效率。 2 2、HuffmanHuffman编码编码的推广的推广：第三部分、信道编码第三部分、信道编码 3.1 信道编码理论信道编码理论第三部分、信道编码第三部分、信道编码3.1 信道编码理论: : 1 1、检错与纠错原理检错与纠错原理： （1 1）检错原理：添加冗余避免码字非此即彼；）检错原理：添加冗余避免码字非此即彼； （2 2）纠

23、错原理：添加冗余拉大码字汉明间距；）纠错原理：添加冗余拉大码字汉明间距； （3）汉明距离：两码字不同码元的个数；汉明距离：两码字不同码元的个数； （4 4）检错能力：）检错能力：d0 0e +1+1 纠错能力：纠错能力：d0 022t +1+1 纠检同时：纠检同时：d0 0e+ +t +1+12 2、译码规则与错误概率译码规则与错误概率：（1 1）最小错误准则：选联合概率矩阵每列最大元素）最小错误准则：选联合概率矩阵每列最大元素（2 2）最大似然准则：选传输概率矩阵每列最大元素）最大似然准则：选传输概率矩阵每列最大元素（3）错误概率计算：未选中元素的总联合概率错误概率计算：未选中元素的总联合概

24、率（4 4）差错率计算：采用信道编码与译码后仍然不能）差错率计算：采用信道编码与译码后仍然不能纠正的错误所具有的概率。也就是（纠正的错误所具有的概率。也就是（3 3）的结果。）的结果。 （5）漏检率计算：）漏检率计算：使用信道编码与译码后仍然不能使用信道编码与译码后仍然不能发现的错误具有的概率。使用反馈重发方式时的差发现的错误具有的概率。使用反馈重发方式时的差错率就等于漏检率。错率就等于漏检率。第三部分、信道编码第三部分、信道编码 3.1 信道编码理论信道编码理论3.2 线性分组码: : 码长为码长为n，信息位为，信息位为k ，记作（记作（n , k）；）； 监督位监督位r n-k1、编码、编

25、码 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；满足此方程的均为正确的许用码字满足此方程的均为正确的许用码字，否则，便，否则，便是误码。是误码。第三部分、信道编

26、码第三部分、信道编码 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是是否有误。否有误。 第三部分、信道编码第三部分、信道编码 3.

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

28、围，各指出信息率的一个理三个定理各有自己管辖的范围，各指出信息率的一个理论极限：论极限：第一定理第一定理负责无失真信源编码；负责无失真信源编码；用信息含量更浓的代码序用信息含量更浓的代码序列代替原先有冗余的信源序列。定理指出列代替原先有冗余的信源序列。定理指出无失真信源编码无失真信源编码的极限信息率的极限信息率R log m，这里这里m是编码的符号个数。是编码的符号个数。第二定理第二定理负责信道编码；负责信道编码； 信道编码通过添加冗余来检错信道编码通过添加冗余来检错纠错，结果差错减少而传信率降低。纠错，结果差错减少而传信率降低。定理指出零差错传输定理指出零差错传输的的极限传信率极限传信率RC

29、，这里这里C是信道容量。是信道容量。第三定理第三定理负责限失真信源编码；负责限失真信源编码；通过削减次要信息使传信通过削减次要信息使传信率降低。率降低。 但是要但是要满足指定的保真度，限失真信源编码的满足指定的保真度，限失真信源编码的极限传信率极限传信率RR(D)，R (D)是信源的率失真函数。是信源的率失真函数。第五部分、密码第五部分、密码 5.1 密码有关的概念密码有关的概念第五部分、密码第五部分、密码5.1 密码有关概念: : 1 1、密码的功能密码的功能：保密与认证：保密与认证 2 2、密码系统的分类密码系统的分类： （1 1）体制：对称密钥体系与公开密钥体系；）体制：对称密钥体系与公

30、开密钥体系； （2 2）结构：序列密码与分组密码）结构：序列密码与分组密码 （3）学科分支：密码编码学与密码分析学学科分支：密码编码学与密码分析学 （4 4）发展阶段：传统密码学与现代密码学）发展阶段：传统密码学与现代密码学 3 3、对称密钥体制的缺憾对称密钥体制的缺憾：第五部分、密码第五部分、密码 5.2 对称密码对称密码5.2 DES: :1. 初始置换与逆置换初始置换与逆置换2. 换位加密（换位加密（16轮迭代）轮迭代）3. f 函数（扩展、加密、压缩、置换）函数（扩展、加密、压缩、置换）4. 子密钥生成子密钥生成第五部分、密码第五部分、密码 5.3 公开密钥密码公开密钥密码5.3 公开密钥密码: : 1 1、特点：特点： 2