总结与复习20126.ppt

信息论与编码 总结与复习 2012,信息学院 信息工程教研室 牛秋娜,本课程主要内容,一个理论和三个编码: 理论-香农信息论 编码-信源编码 信道编码 保密编码,第一部分、信息论基础,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）对称性：H(p1p2)=H(p2p1) （3）极值性： 1离散信源各符号等概率时出现极大值： H0=log m 2连续信源信号幅度受限时均匀分布出现 极大值： 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,第一部分、信息论基础 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)。 传输矩阵:,第一部分、信息论基础 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),例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)= -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)损失熵：,第一部分、信息论基础 1.2 信道的信息理论,第一部分、信息论基础 1.2 信道的信息理论,4. 信道容量 对称信道：传输矩阵的各行都是一些相同元素的重排，各列也是一些相同元素的重排。,（1）定义：对于给定的信道，总存在一个信源能使互信息取极大值，该极大值定义为信道的信道容量： 信道容量反映了一个信道最大所能传输的平均互信息，是给定信道的属性。使传信率等于信道容量的信源，称为该信道的匹配信源。,第一部分、信息论基础 1.2 信道的信息理论,（2）信道容量的计算： 对于简单信道要求能计算信道容量： 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/符号；,第一部分、信息论基础 1.2 信道的信息理论,（3）波形信道的信道容量： 发送连续信号的信源是连续信源，传输连续信号的信道是波形信道。 高斯加性噪声波形信道的容量由Shannon公式给出： C= B log(1+ PX /Pn ) 香农公式给出了带宽B、信道容量和信噪比PX /Pn三者之间的制约关系。 信道容量不变 时带宽与信噪比有互换关系。,第二部分、无失真信源编码,第二部分、无失真信源编码 2.1 信源编码理论,1.1 信源编码理论: 1、信源的相对信息率和冗余度： 实际信源由于非等概，有记忆： 信源每个符号最大可以荷载的信息量是 H0=log m 平均每个符号的实际信息荷载量是H HN H(X) （1）只要信息熵没有达到最大值，就存在冗余。 （2）定义相对信息率： = H/H 0 （3）信源冗余度（或剩余度）： =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）计算平均码长与编码效率。 2、Huffman编码的推广： 扩展信源编码；多元编码,第二部分、无失真信源编码 2. 2 编码方法,3、游程编码 适用于连0连1情况。等熵变换，没有直接压缩代码，但将二元码变成了多元码。为使用Huffman编码创造了条件。与MH编码结合即传真编码。 4、算术编码 属于序列编码。通过计算非等概信源的序列概率和积累概率直接找到相应的等概序列。 5、词典编码 不依赖于概率的通用编码。建立初始小词典后边输入边查词典边补充新词条，以词条序号为编码。,第三部分、信道编码 3.1 信道编码理论,第三部分、信道编码,3.1 信道编码理论: 1、检错与纠错原理： （1）检错原理：添加冗余避免码字非此即彼； （2）纠错原理：添加冗余拉大码字汉明间距； （3）汉明距离：两码字不同码元的个数； （4）检错能力：d0e +1 纠错能力：d02t +1 纠检同时：d0e+t +1 (et),2、译码规则与错误概率： （1）最小错误准则：选联合概率矩阵每列最大元素 （2）最大似然准则：选传输概率矩阵每列最大元素 （3）错误概率计算：未选中元素的总联合概率 （4）差错率计算：也就是（3）的结果。 （5）漏检率计算：使用反馈重发方式时的差错率就等于漏检率。 3、几种简单的信道编码： （1）重复码（2）奇偶校验码（3）恒比码,第三部分、信道编码 3.1 信道编码理论,3.2 线性分组码: 码长为n，信息位为k ，记作（n , k）； 监督位r n-k 1、编码 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 线性分组码,3.3、循环码,1. 码多项式 2. 生成多项式码多项式中那个次数最低的非零多项式g(x),第三部分、信道编码 3.3 循环码,n-k = r 次；常数项为1。 任意码多项式都是生成多项式 g(x)的倍式。 g(x)是xn-1的一个因式。,3. 编码 确定编码的n、k、r 值； 写出给定信息位多项式：K(x)； 左移 r 位：x r k (x) 计算监督位多项式： r (x) = x rK (x) mod g(x) ； 写出码多项式：C(x) = x r K (x) + r (x) 写出码字：C,第三部分、信道编码 3.3 循环码,4. 纠错、译码 接收码多项式R(x)； 伴随子多项式S(x) = R(x) mod g(x)； 若 S(x) = 0，则表明接收码无误。 若 S(x) 0，表明接收码有误。 S(x) =C(x)+E(x) mod g(x) = E(x) mod g(x)； 列S (x)E (x) 对照表，由S(x)查出E (x) C (x) = R (x) + E(x),第三部分、信道编码 3.3 循环码,第三部分、信道编码 3.4 循环码的扩展,3.4、循环码的扩展,1. 截短的循环码 由(n,k)循环码截短生成的(n-i,k-i )码。如CRC码,2. 本原BCH码 本原BCH码取码长为n = 2m 1，生成多项式为：,它是能纠正多位错的循环码。式中 t 是纠错位数，mi(x)是xn-1的第i类因式。,3.5、卷积码,1. (n, k, m)的含义 2. 输出对输入的依赖关系 监督方程 逻辑电路 冲激响应 转移函数矩阵 3. 状态转移图与格图：状态指寄存器的值。 4. 编码与译码,第三部分、信道编码 3.5 卷积码,卷积码维特比译码的基本步骤是： A.画出卷积码的网格图。 B.按时间顺序依次计算每个时刻各条支路的支路度量; C. 计算进入该时刻各节点各条路径的路径度量，并保留路径度量最小的那一条路径; D. 各个时刻都进行相同的计算，最终由路径度量最小的那条保留路径来决定译码。,例7已知(2, 1, 2)卷积码的冲激响应为： g1=(1, 1, 1)， g2=(1, 0, 1)； （1）写出监督方程和转移函数矩阵。 （2）画出编码器的电路框图。 （3）画出状态转移图。 解: (1)转移函数矩阵 G(D)=(1+D+D2, 1+D2) 监督方程:,第三部分、信道编码 3.5 卷积码,（2）电路图,（3）状态转移图:,第三部分、信道编码 3.5 卷积码,S2,S1,注意！ ai的状态是ai-2ai-1 即寄存器S2S1的值。 （注意先后次序）,k,c1c2,第四部分、限失真信源编码,第四部分、限失真信源编码 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是编码的符号个数。 第二定理负责信道编码； 信道编码通过添加冗余来检错纠错，结果差错减少而传信率降低。定理指出零差错传输的极限传信率RC，这里C是信道容量。 第三定理负责限失真信源编码；通过削减次要信息使传信率降低。 但是要满足指定的保真度，限失真信源编码的极限传信率RR(D)，R (D)是信源的率失真函数。,典型题目讲解,第五部分、典型题目,一填空： 码长为10最多可纠2位错的线性分组码可写为( ) 码; 2.监督位为r=6的汉明码，信息位为_位，编码效率等于_，能够纠正 位错。 3.无失真信源编码定理指出平均码长的理论极限值 ，此时编码效率为 。 4. 信源编码的主要目的是 ；信道编码的主要目的是 ；保密编码的主要目的是 。,10, 4,57,57/63=0.905,1,检查纠正错误,H/logr,增强抗攻击性,1,压缩代码长度,5. 某二元无记忆信源发出100个二元符号，其中有m个“1”， 若P(0)=1/4，则总自信息为_。 6信道误码率为p=10-3，采用三连重复码编码传输时的差错 率约为 。 7. 香农信源编码定理指出，无失真压缩的极限信息率R 不能大于 ， 香农信道编码定理指出，无差错传输的传信率不能大于 。 8. 已知在GF(24)中因式分解有：x15-1= m0(x)m1(x) m3(x) m5(x) m7(x) =(x+1) (x4+x+1) (x4+x3+x2+x+1) (x2+x+1)(x4+x3+1)，则(15，5)本原BCH编码的生成多项式是 _。,第五部分、典型题目,310-6,log M,信道容量,g(x)=LCMm1(x)m3(x)m5(x) =x10+x8+x5+ x4+x2 +x+1,200-1.585m,9.某理想通信系统，信噪比为3dB，为使功率节省一半又 不损失信息量，带宽应增加到原来的 _倍。 10.错传率为p的BSC的信道容量为 。 11.若 _受限,输出波幅度在a,b之内，则均匀分布的连续信源具有最大熵，熵值为_；若_受限，正态分布的连续信源具有最大熵，熵值为 ；,第五部分、典型题目,1+plog p+(1-p)log(1-p),log (b-a),峰值功率,平均功率,log23=1.585,第五部分、典型题目,二判断(正确打，错误打) 1信源符号的相关程度越大，信源的信息熵越大。 2、异前缀码一定是即时码； 3、信道编码定理指出：信道无失真传递信息的条件是信息率小于信道容量 ； 4、Huffman编码是单符号信源编码的最佳编码； 5、最大似然译码准则是使平均译码错误率最小的准则。 6、满足克拉夫特不等式的码必定是惟一可译码。,第五部分、典型题目,7、 交织码，Fire码，游程编码都可用于纠正突发错误的信道编码中。 8、 (15，11) 码是汉明码。 9、 (23，12) 码不是完备码。 10、信源编码中往往无法指出哪几个码元或符号是冗余，冗 余表现为信息熵没有达到最大值。 11、恒比码是线性分组码。 12、离散等概信源具有最大信息熵。 13、,第五部分、典型题目,三计算题： 1一阶马尔可夫信源的状态图如右，信源X的符号集为0,1,2，图中 。分别求： (1)平稳后的信源概率分布； (2)信源熵H； (3)求p=1时实际信源的熵，并说明所得结果的理由。,解：(1) 一阶马尔可夫信源，状态为单个符号，信源符号集为X=0,1,2，E1=0,E2=1,E3=2,稳态概率满足： Q(0)= (1-p)Q(0) 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=1时， 理由：因为每种状态都只发两个符号，当一种符号概率为1时，另一个必然为0，实际上只发一种确定的符号，成为确定事件，其自信息为0。三种状态下发出符号的自信息均为0，平均值也一定为0。因此不确定性为0，所以信源熵为0。,2.二元无记忆信源发出a、b两个符号，概率分别为0.7和0.3，试用三次扩展信源进行二元Huffman编码。 解：根据 p(x1x2x3)=p(x1)p(x2)p(x3) 不难求出三次扩展信源的概率空间为：,按8个符号的概率排队，进行Huffman编码,第五部分、典型题目,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%,第五部分、典型题目,3二元信源每秒发出100个符号，若信源概率为0.6和0.4；信道传输矩阵为: ；求发信率和传信率。,第五部分、典型题目,解：发信率就是信源符号熵乘以码率：Rb=RBH(X)： H(X) = -0.6log0.6-0.4log0.4= 0.9710 bit/符号 Rb=RBH(X)= 97.1 bit/s 传信率就是平均互信息乘以码率，Rt=RBI(X;Y) ：,联合熵：H(XY)=1.7822; 接收符号熵：H(Y)=0.9928; 平均互信息：I (X;Y) =H(X)+H(Y)-H(XY)=0.1816 bit/符号 传信率: Rt=RBI(X;Y)= 18.16 bit/s,4.（1）(7, 3)截短循环码生成多项式是g(x)=x4+x+1。求生成矩阵与一致校验矩阵。 （2）为信