信息处理算法信息论基础information-theory11

1、信息论基础Elements of Information Theory杭州师范大学理学院kht/s/1kT1X4Jd课程安排&课程要求上间地点第1周-第16周，每周二，13:20-15:50 ，下沙校区A-201教室信息论信息论假说 ：物质、能量与信息是组成世界的三大要很深入地了解了物质与能量，而对信息的认识还相对较少。们已经信息论是运用概率论与数理统计的方法对信息定量化，将信的息传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输、信息压缩以及信息是信息论研究中的重要领域。本课程的目标研究信息论基本内容及相关应用，即信息熵、信道容量以及信源和信道编码和通信等问题，为进一步学习相

2、关课程打下基础。考核要求出勤(15%)+平时的作业(35%)+期末(50%)电子课件ht/s/1kT1X4Jd及参考书，信息论与编码（第二版），电子工业，2014, 信息论基础（第4版）,邮电大学2008，信息论2014与编码，人民邮电T. M. Cover and J. A. Thomas,Elements of Information Theory,（信息论基础, 机械工业,2012）R.e, Information Theory,Coding and Cryptography, （信学, 机械工业息论、编码与, 2005）主要内容第1章 绪论第2章 离散信源及其信息测量基本概念第3章 离

3、散信道及其信道容量第4章 （略去）第5章 无失真信源编码定理第6章 有噪信道编码定理基础理论第7章 保真度准则下的信源编码第8章 无失真的信源编码第9章 信道的纠错编码实际方法第9章 通信与相关应用作业中问题12U 11 ，失真矩阵信源01/ 3D 117.2 无21 p(u)1/ 31/ 3求Dmin, Dmax, 以及相应的信道Pp(u) min d (u, v) 1 1解：Dmin13vuu minp(u) d (u, v) min( 2 ), ( 2 1 ) Dmax11134333333vvu p11p12 设信道矩阵 P pp , 其中pp 1, i 1, 2, 322 p32 2

4、1i1i 2 1 p310P 1 , 其中0 1相对于Dmin，信道矩阵应该有p+ p=0；min1231 0相对于Dmax，信道矩阵应该有p12+ p31 =1；1rsD p(xi )p( y j| xi )d (xi , y j )1,i 1 j 1m1 ( p2 p) ( pp) (2 pp)1112212231323133 p p31 12纠错编码第二定理证明，当R C 0时 PE的码存在。注：证明过程采用的是随机编码的方法随机编码所得的码集很大，通过搜索得到好码的方法在实际上很难实现即使找到了好码，这种码的码字也没有规律，不便于译码（一般的译码问题是问题）真正实用的信道编码方法还需要

5、通过各种数学工具来构造，使码具有好的结构性以便于译码近世代数是纠错编码理论用到的最重要的数学工具它包括群论、环论、域论、格论、线性代数等许多分支纠错编码的基本思路纠错编码是提高传输可靠性的最主要的措施之一根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。信道模型信道可分为三类只产生随机错误的信道称为随机信道。比如信道、同轴电缆、光缆信道以及大多数微波中继信道产生突发错误的信道称为突发

6、信道。实际的短波信道、移动通信信道、由于擦伤造成成串差错的光盘和磁盘，均为这一类信道有些实际信道既有随机错误又有突发错误，称为混合信道干扰源一般有两种一是随机噪声，它主要来源于设备的热噪声和散弹噪声以及媒介的热噪声，它是通信系统中的主要噪声二是脉冲干扰和信道，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障等CmmR检错编码检错译码信道纠检错的工作方式反馈反馈重传(ARQ)发送端经编码后发出能够发现错误的码，接收端收到后经检，验如果发现传输中有错误，则通过反馈系统把这一判断结果反馈发回端，然后发送端把前面发出的信息重新传送一次，直到接收端为认正确地收到信息为止CmmR纠错编码纠

7、错译码信道前向纠错(FEC)发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译可以自动纠错注：前向纠错方式不需要反馈信道，特别适合于只能提供单向信道的场合；由于能自动纠错，不要求检错重发，因而延时小，实时性好；随着纠错能力的增强，译码设备也变得复杂混合纠错对发送端进行适当的编码。当错误不严重，在码的纠错能力范围之内时，采用自动纠错；当产生的差错超出码的纠错能力范围时，通过反馈系统要求发端重发纠错码(Error Correcting Code)的分类按功能分检错码：仅能检测误码纠错码：可纠正误码纠删码：兼纠错和检错能力纠错码按信息码元与监督码元之

8、间的检验关系分线性码：满足线性关系非线性码：不存性关系按信息码元与监督码元之间的约束方式不同分分组码：本码组的监督码元仅和本码组的信息元相关树码：本码组的监督码元不仅和本码组的信息元相关，而且与前面码组的信息码元有关。如果是线性关系则称为卷积码按信息码元在编码后是否保持不式变系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变非系统码：信息位打乱，与编码前不同按纠正差错的类型可分为纠随机错误码纠突发错误码纠随机和突发错误码 循环码线性分组码非循环码纠错码 非线性 线性 卷积码树码非线性信息序列码字编码举例及基本概念00000000000010011101给出一种编码方式，如右

9、图：0100100111编码是消息序列集M 到码字集C的0110111010M C1001001110m mm mc c c .c1231 271011010011信息序列组由 3(=k) 个信息码元(信息位)组成，1101101001共有 8=23( =2k )个不同的信息码组1111110100输出长度为n=7的码字编附加 r=n-k个元(校验位或监督位)，每个元是该信息码组的某些信息码元的模2和：C4C3码字的数目共有 M =2k ，最小距离d=4，码字的集合称为 (n,k) 线性分组码，也称 (n,M,d)码，n,k,d码。编码效率定义：设x=x1x2xn是码C的一个码字，x的汉明重量

10、为wH(x)=#xi 0 | i=1,2,n，则码C的最小重量wmin (C)=min wH(x) | x C, x 0 最小距离dmin(C)=min D (x, y) | x y C= minwH (x-y) | x y C对二进制(n, k)线性分组码，合法码字数为2k，可用编码空间的序列数为2n个。任一种2k信息集合到二进制序列集合(2n)的都是一种(n, k)码 ，kC 2因此总共可能的编码方案有种2nlog 2klog Mk信息传输率（码率） R nnn k编码效率n纠错编码发现或构造好码是信道编码研究的主要问题一方面要兼顾纠错能力与编码性质(码率高)另一方面是实现的考虑，要求容易

11、译码线性分组码是相对简单的一类码，最具实用价值的有汉明码、循环码、BCH码、RS码等对信道编码的一般要求是纠错检错能力强；信息传输率高；编译码简单，实现容易且费用低；与信道的差错统计特性相匹配。+01线性码010001001110定义：集合0,1上定义两种运算加法“+”：a+b = a+b mod 2乘法“* ”： a*b则0,1, +, 一个域。称上述域为一个二元域(有限域)，记为GF(2)，或F2 。定义：码C称作(n,k)-线性码，如果C是V=F2F2F2=F2n 的一个k-维子空间。定理：是码C是一个(n,k)-线性码，则有最小距离dmin(C)=最小重量 wmin (C)定理：码C称

12、作(n,k)-线性码，则存在k个线性无关码字x1 , x2 , , xk能够C, 即L(x1 , x2 , , xk)=C;n-k个线性无关向量y1 , y2 , , yn-k与C正交, 即L(y1 , y2 , , yn-k)=C 。证明：(略去)例1哪些是线性码？码1码2码3码4码5码600000101000011100000100001110100000110000000011011011101111001011010100101110111信息序列码字例200000000000010011101码字C C1C2C3C4C5C6C7各分量有下面的关系0100100111C4 011011

13、1010 01001001110 01011010011C3 0 01101101001 C3 C71111110100C1 C 0 2 10011000 C3 10 011010 C TTHC0 4 1010001 C5 0TCH1 0110000C6 称(n-k)n矩阵HH QIC7 为一致校验矩阵校验矩阵(Parity Check Matrix)H被称为校验矩阵对 (n,k) 线性分组码，校验矩阵为(n-k)n矩阵对于系统码，校验矩阵可以表示为H = QI其中 Q 为(n-k)k 矩阵，I 为(n-k)(n-k)矩阵定理：设H为(n,k)-线性分组码C的校验矩阵，则向量x=x1x2xn是

14、码C的一个码字当且仅当 (if and only if) Hxt= 0, orxHt= 0等价地，如果H的每一列用向量表示，即H=H1,H2,Hn,则x=x1x2xnC一致校验方程nxHt x H 0iii1 C1 C2C1例2 (续)C2由校验方程，得到C C33C4C4C3C31000111C 01C CC100111230101110事实上，C的一个基底作为行可以构G IP成kn生成矩阵G。m c1, c2 , c3 C = mG令生成矩阵(Generator Matrix)G被称(n,k)线性分组码的生成矩阵生成矩阵为 kn 维矩阵对于系统码，生成矩阵可以表示为G = IP其中P为k(

15、n-k) 维矩阵，为I 维矩阵。把生成矩阵的每一行用一个行向量G1,G2,Gk来表示，则生成矩阵可以表示为G1 G G 2 G k m m1, m2 ,., mk 令，则kC = mG miGii1校验矩阵和生成矩阵的关系由于生成矩阵G的每一行都是一个码字，所以G的每行都满t足 HG= 0 ，则有iHGt = 0对于标准形式的校验矩阵和生成矩阵，有HGt = Q II Pt= Q+ Pt = 0Q = Pt定义：设C是F2上的一个n长分组码，则C的对偶码为C= x | xVn(F2), xy=0,yC定理：C是F2上的(n,k)-线性码，则C (n,n-k)-线性码。推论：C的生成矩阵(校验矩

16、阵)为C的校验矩阵(生成矩阵)。例例3：3次简单重复码是一个(3,1)线性分组码。其生成矩阵为G 1 1 1C C1C2C3 m11 1 1 m1 m1 m1例4：(4,3)偶是一个(4,3)线性分组码，其生成矩阵为1100G 011010011100m 01C C C C C mm1012341230101 m1, m2 , m3 , m1 m2 m3 例5已知生成矩阵为10010001101111110G 0101mC00000000000010011101求生成的线性分组码及由H 生成0100100111的线性分组码0110111010C mG(7,3)-线性码1001001110101

17、101001111011010011111110100求出校验矩阵利用生成矩阵与校验矩阵的关系10010001101111110G 01G IP011011P 01111110利用标准形式的校验矩阵Q I和生成矩阵I P的关系 QPt1001100I 1110100H Q10100010111000mC00000001001000110100010101100111000000001100011100010101001111101001000101生成码空间C mHC的生成矩阵1001111101100001000010H QI 10011000101100100111100010011011

18、0001101001生成矩阵的式1100010101001110100100111101100010110001011110001011000111010011101001011110100111011111111111离散平稳无二分组码的纠错检错能力元对称信道适用对于一个二进制对称信道，当输入为2k个等可能的n长码字，则最大后验概率准则等效于最小汉明距离译码准则np(y j | xi ) p( y jknd| xi) pkdpk 1对于(n, k)线性分组码，设dmin为码的最小距离，则dmin= 2u +1这组码能纠正 u 个错误的充要条件是uu l 1能检测l个错误的充要条件是 dmin2u+1ll问题：以码字为中心，将空间被划分成不同的球体，纠错l+1编码问题变成空间的覆盖问题。编码参数的关系能纠正 u 个错误，同时可以发现l (lu)个错误的充分必要条件为 u l 1dminluu+l+1码的纠错能力u与码字的长度n和消息数M满足以下关系uC 2niMni0纠错编码研究之一：构造编码，使得各个参数n,k,d,M等满足要求，且达到最佳。n校验矩阵与码的最小距离关系xHt x H 0iii1定理：对于(n,k)-线性分组码校验矩阵H中的任意 t 列线性无关而t+1列线性相关，则码的最