《总结与复习20146》由会员分享，可在线阅读，更多相关《总结与复习20146（56页珍藏版）》请在金锄头文库上搜索。
1、信息论与编码 总结与复习 2014,信息学院 信息工程教研室 牛秋娜,本课程主要内容,一个理论和三个编码:理论-香农信息论编码-信源编码信道编码保密编码 各编码作用是？,第一部分、信息论基础,1.1 信源的信息理论:1、信息的定义：（1）自信息 I = log(1/p) =-log p（2）通信完成后获得的净信息量=通信所消除掉的不确定度 （3）信息的单位：对数的底取2时，自信息的单位叫比特(bit)。,第一部分、信息论基础 1.1 信源的信息理论,2、信息熵的定义：（1）离散信源,（2）连续信源,第一部分、信息论基础 1.1 信源的信息理论,3、信息熵的特点 （1）非负性：H(X) 0 （2
2、）极值性：1离散信源各符号等概率时出现极大值：H0=log m2连续信源信号幅度受限时均匀分布出现极大值： hmax(X)=log (b-a)； 3连续信源信号方差有限时高斯分布出现极大值：,第一部分、信息论基础 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,第一部
3、分、信息论基础 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以外不关联
4、。 （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；根据归一化条件可求出
5、另外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)。传输矩阵:,第一部分、信息论基础
6、1.2 信道的信息理论,2、信道有关的信息熵： （1）信源熵 (先验熵)：,（2）噪声熵 ：,（3）联合熵：,（4）接收符号熵：,（5）损失熵(后验熵)：,第一部分、信息论基础 1.2 信道的信息理论,3. 平均互信息,计算公式： I (X;Y) = H(X) H(X|Y)= H(Y) H(Y|X)= H(X) +H(Y)H(XY) I (X;Y) 代表系统每完成收发一对符号的通信过程后，所消除掉的平均不确定度，即信宿从每个符号中平均所获得的净信息量。,例2已知信源先验概率p(x)=0.7, 0.3，信道传输 矩阵 ；试计算各信息熵和互信息。,H(XY)= -0.21log0.21 0.14l
7、og0.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.
8、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)噪声熵：,由 和,第一部分、信息论基础 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)损失熵：,第一部
9、分、信息论基础 1.2 信道的信息理论,第一部分、信息论基础 1.2 信道的信息理论,4. 信道容量 对称信道：传输矩阵的各行都是一些相同元素的重排，各列也是一些相同元素的重排。,（1）定义：对于给定的信道，总存在一个信源能使互信息取极大值，该极大值定义为信道的信道容量： 信道容量反映了一个信道最大所能传输的平均互信息，是给定信道的属性。使传信率等于信道容量的信源，称为该信道的匹配信源。,第一部分、信息论基础 1.2 信道的信息理论,（2）信道容量的计算： 对于简单信道要求能计算信道容量： 1）无损信道：C = maxI(X;Y)= maxH(X)=log m ； 2）无噪信道：C = max
10、I(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/符号；,第一部分、信息论基础 1.2 信道的信息理论,（3）波形信道的信道容量： 发送连续信号的信源是连续信源，传输连续信号的信道是波形信道。 高斯加性噪声波形信道的容量由Shannon公式给出：C= B log(1+ PX /Pn ) 香农公式给出了带宽B、信道容量和信噪比PX /Pn（注意是线性比值）三者之
11、间的制约关系。 信道容量不变 时带宽与信噪比有互换关系。,第二部分、无失真信源编码,第二部分、无失真信源编码 2.1 信源编码理论,1.1 信源编码理论:1、信源的相对信息率和冗余度：实际信源由于非等概，有记忆：信源每个符号最大可以荷载的信息量是 H0=log m平均每个符号的实际信息荷载量是H HN1，不能唯一可译；码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）信源符号按
12、概率大小排队。（2）合并概率最小的两个符合为一个节点。（3）节点参与排队放在与自己概率相等符号后面。（4）重复这个过程直到合并完全部符号。（5）标记每个分支的的0与1。（6）从根到叶的路径就给出了相应符号的码字。（7）计算平均码长与编码效率。2、Huffman编码的推广：扩展信源编码；多元编码,例6设信源概率空间为，编码符号集为Y=0,1，进行Huffman编码（要求码长发差最小）。 解：编码为： s1(10)，s2(11)，s3(010)，s4(011)， s5(0000)，s6(0001)，s7(0010)，s8(0011)平均码长：l =2.75H(X)=2.75bit/符号，=100%,第二部分、无失真信源编码 2.2 编码方法,第二部分、无失真信源编码 2. 2 编码方法,3、游程编码适用于连0连1情况。等熵变换，没有直接压缩代码，但将二元码变成了多元码。为使用Huffman编码创造了条件。与MH编码结合即传真编码。 4、词典编码不依赖于概率的通用编码。建立初始小词典后边输入边查词典边补充新词条，以词条序号为编码。,第三部分、信道编码 3.1 信道编码理论,
