差错控制编码

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数字通信原理,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/9/14,#,数 字 通 信 原 理,Principles of,Digital Communication,Central South University,College of Information Science and Engineering,数字通信原理,8/7/2024,8/7/2024,数字通信原理,第一讲,绪论,第二讲,信息论基础和信号分析,第三讲,模拟调制技术,第四讲,信源编码技术,第五讲,数字基带传输,第六讲,数字调制技术,第七讲,差错控制编码,数字通信原理,8/7/2024,目 录,8/7/2024,数字通信原理,第七讲 差错控制编码,7.1 基本概念,7.2 纠错编码原理,7.3 常用的简单编码,7.4 线性分组码,7.5 循环码,8/7/2024,数字通信原理,7.1 基本概念,7.1.1 产生误码的原因和信道分类,一、原因,系统特性的不理想：,乘性噪声,数字信号波形失真接收端误判形成误码,信道噪声干扰：,加性噪声,数字信号变形误码,二、信道分类,按加性噪声引起的错码分布规律的不同分类：,随机信道：存在白色高斯噪声，误码相互独立；,突发信道：存在突发脉冲干扰，误码在短时间内成串出现，并前后有关；,混合信道：随机信道突发信道；,8/7/2024,数字通信原理,三、差错类型,随机差错独立差错,差错的出现随机，且差错之间是统计独立的,由随机噪声引起,存在这种差错的信道称为随机信道无记忆信道,突发差错,差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关,因脉冲噪声，也可能是由存储系统中磁带的缺陷或读写头接触不良引起,存在这种差错的信道称为突发信道有记忆信道,8/7/2024,数字通信原理,加大发送功率,即提高信噪比，虽简单有效，但功率不可无限增加，所以实际上受到一定的限制；,匹配滤波接收,：可一直白色噪声，使误码率下降；,合理的调制解调方式,Pe,PSK,Pe,DPSK,Pe,FSK相干、ASK,t),8/7/2024,数字通信原理,C,e,1,d,0,t,C,1,C,2,t,d,0,C,1,C,2,t,e,d,0,t,8/7/2024,数字通信原理,差错控制编码的效果,假设随机信道中发送“0”码与发送“1”码传错概率相等为P,e,且P,e,1,则在码长为n的码组中发生r个错误的概率为：,P,n,(r)=C,n,r,P,e,r,(1-,P,e,),n-r,n!/r!(n-r)!,P,e,r,当码长n=7,P,e,=10,-3,时，则有,P,7,(1)7 P,e,=7 10,-3,P,7,(2)21 P,e,2,=2.1 10,-5,P,7,(3)35 P,e,3,=3.5 10,-8,8/7/2024,数字通信原理,编码效率,指一个码组中信息位所占比重，用,表示,=k/n，其中k为信息码元的数目，n,为码长,可见：若加入的监督位越多，纠错能力越强，编码效率越低；,纠错编码的,任务,是，根据不同干扰特性设计出纠检错能力最强，效率高的纠错码，且译码设备不太复杂；,8/7/2024,数字通信原理,7.3 常用的简单编码,奇偶校验码奇偶监督码,奇监督码,：使码字加上1位监督位C,0,后，码字中“1”的个数为奇数个；,偶监督码,：使码字加上1为监督位C,0,后，码字中“1”的个数为偶数个；,只能检测出奇数个错误，不能纠错,应用：以随机错误为主的计算机通信系统，难于对付突发错误,最小码距d,min,=2,8/7/2024,数字通信原理,二维奇偶校验码水平垂直奇偶监督码,将奇偶监督码推广到二维。即在每一行进行奇偶校验，同时在矩阵中每一列进行奇偶校验，发送时按列的顺序传输,接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验,能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误；并有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好分布在矩阵的四个顶点时，则检测不出,可纠正一些错误,适用于检测突发错误，将使误码减少到原来的11,8/7/2024,数字通信原理,8/7/2024,数字通信原理,等比码,每个码组中含“1”和“0”的个数的比例恒定，又称,等重码,、,恒比码,、,定1码,；,能检测出所有1位错和奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出）,简单，适应于对字母或符号进行编码，常用于电传机传输汉字，以及其他产生固定字符的键盘设备中；,举例,8/7/2024,数字通信原理,正反码,监督位数与信息位数目相同，且两者相同或相反，取决于信息序列中“1”的个数；,编码规则,当信息位中有奇数个“1”时，监督位是信息位的简单重复；,当信息位中有偶数个“1”时，监督位是信息位的反码；,接收端解码,先将码组中信息位与监督位按位模2加，得到合成码组,产生校验码组：码组中信息码元有奇数个“1”，则校验码组=合成码组，否则校验码组=合成码组的反码,按照校验码组中“1”的个数进行检错及纠错,8/7/2024,数字通信原理,校验码组的组成,错码情况,1,全为“0”,无错码,2,有4个“1”，1个“0”,信息码中有一位错码，位置为校验码中对应的“0”的位置,3,有4个“0”，1个“1”,监督码中有一位错码，位置为校验码中对应的“1”的位置,4,其他组成,错码多于1个,8/7/2024,数字通信原理,举例：电报通信中常用5单位电码来构造正反码,编码,若为11001，则码字为1100111001,若为10001，则码字为1000101110,假设发送码组为1100111001,若接收码组为1100111001，判决为无错传输,若接收码组为1000111001：合成码组01000；因码组中信息码元有偶数个“1”，则校验码组为10111；说明信息码元中第二位错码，给以纠正,若接收码组为1100101001：合成码组10000；因码组中信息码元有奇数个“1”，则校验码组为10000，说明监督码元中第一位错码,若接收码组为1001111001：合成码组01010；因码组中信息码元有奇数个“1”，则校验码组为01010，说明错码多于1个,码长为10的正反码能够纠正1位差错，并能检测所有2位及以下的错码。,8/7/2024,数字通信原理,7.4 线性分组码,基本概念,系统码,：信息码元编码后，信息码元本身不变，而只在信息码元后加入监督码元，即前半部分为不变的信息码元，后半部分为监督码元的码型；,线性码,：监督码元和信息码元成线性关系的码型；,分组码,：监督码元只和本身信息码元有关的码型；,线性分组码,：利用代数关系，将信息序列划分为等长的k位序列段，在每一信息段后附加r个监督码元，并使监督码元和信息码元成线性关系，这样构成的码型就叫；,汉明码,：纠单个错的线性分组码；,循环码,：在严谨的代数基础上构造的、纠错能力强的解编码设备并不复杂的线性分组码；,卷积码,：监督码元不仅与本身信息码元有关，且跟其它码元有关的一种码型；,8/7/2024,数字通信原理,线性分组码的特点,具有,封闭性,，即任意两许用码组之和仍为一许用码组；,码距的最小值等于最小码重,（除全“0”码组以外）；,线性分组码的表示（n，k），码长为n，信息码长为k，监督码长rnk；,一致校验矩阵H(Paritycheck Matrix),用于说明监督码元与信息码元监督关系的矩阵；,8/7/2024,数字通信原理,举例：（7，4）码,设码元表示为：C=C,6,C,5,C,4,C,3,C,2,C,1,C,0,；,由（7，4）码可知：n=7，k=4，r=3；,假设：,8/7/2024,数字通信原理,举例：（7，4）码,则可写成矩阵形式：,为一致校验矩阵H,8/7/2024,数字通信原理,8/7/2024,数字通信原理,一致校验矩阵H的特性,：,H是rn阶矩阵，r为监督码元个数，n为码长；,H=P|I,r,，P是rk阶阵，I,r,为r个监督码系数构成的rr阶单位矩阵，此时称H为典型形式监督矩阵，各行线性无关；,若接收到码字R与H的转置乘积为0，则说明接收到的码字R是正确的，即,RH,T,=0，则R正确；,最小码距d,0,RC，说明正确接收；,若传输过程发生误码，设收发码组之差为E,则,E=E,n-1,E,n-2,E,0,=R-C,E,i,1 第i位有错，即R,i,不等于C,i,0 第i位没有错，即R,i,C,i,E为错误图样，,即发送数据序列与接收序列对应码位的模和；,R=C+E(模2)，可知，S=RH,T,=EH,T,，称S为校正子或伴随式或校验子，为1r阶行矩阵，它最多能指出,2,r,-1种错误。,以（7，4）汉明码为例，设发送码组,A=,（0001011），接收码组R=（0000011），则收端译码过程如下：,计算校正子S=RH,T,=0000011H,T,=011,T,查表得a,3,为错误位置，即可纠正,8/7/2024,数字通信原理,线性分组码不能检错的概率,但错误码组刚好等于任意许用码组时，校正子S=0，不能检测出错误,设信道的误码率为,p,e,，线性分组码的最大检错个数为D，则不能检错概率为,其中，,W,i,表示该码中重量为i的码组数目。,8/7/2024,数字通信原理,7.5 循环码,特点,除线性分组码的特点外，还具有循环性，即任意许用码组循环移位后仍是许用码组（除全“0”码组外）,码多项式,为进一步说明循环码的性质和构造而设计的，是,把码长为n的码组中的各码元当作n-1次多项式的系数而构成的。,码多项式表示,若码组A=（a,n-1,，a,n-2，,，a,1,，a,0,)，则其相应的码多项式为：A(x)=a,n-1,x,n-1,+a,n-1,x,n-1,+a,1,x+a,0,如码组（1100101）对应的码多项式可表示为,A,7,(x)=1x,6,+1x,5,+0 x,4,+0 x,3,+1x,2,+0 x+1=x,6,+x,5,+x,2,+1,码多项式与码组的关系：本质上是一回事，仅是表示方法的不同而已,8/7/2024,数字通信原理,码多项式的模运算,一般来说，若一整数m可以表示为,则称在模n运算下，有m,p（模n）,即：模n运算中，整数m等于被n除所得的余数；,码多项式的模运算也类似：,8/7/2024,数字通信原理,定理1：,若T(x)是n长循环码中的一个码多项式，则,x,i,T(x)按模,x,n,1运算的余式必为循环码中的另一个码多项式；,即若 x,i,A(x)A,i,(x)（模x,n,+1）,则 A,i,(x)也是一许用码组，且为A(x)码组向左循环移位i次的结果。,（证明）,生成多项式g(x)和生成矩阵G,g(x)是循环码中前k-1位为0的码字的码多项式，即为(n-k)阶码多项式；,定理2：,在循环码中，(n-k)阶码多项式有且仅有一个；,定理3：,循环码中，所有码多项式都能被g(x)整除；,推论,：次数不大于k-1次的任何多项式与g(x)的乘积都是码多项式；,定理4：,循环码的生成多项式g(x)是x,n,+1的一个因式；,生成多项式的常数项必须不为“0”。,8/7/2024,数字通信原理,根据循环性，xg(x)，x,2,g(x)，,，x,k-1,g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x)：,注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵。,8/7/2024,数字通信原理,循环码的编码过程和译码过程,编码(设信息码多项式为m(x),确定g(x);,信息码元左移r位，得M(x)=x,n-k,m(x)；,M(x)除以g(x)，求余数R(x)；,T(x)=x,n-k,m(x)+R(x),例，对(7,3)循环码编码,设(7,3)循环码的生成多项式为g(x)=x,4,+x,2,+x+1,待编码信息位为110,则m(x)=x,2,+x,x,n-k,m(x)=x,4,(x,2,+x)=x,6,+x,5,而,即余式r(x)=x,2,+1,于是，对应码组A(x)=x,6,+x,5,+,x,2,+1 1100101,8/7/2024,数字通信原理,循环码的编码过程和译码过程,可见，上例编出的循环码就是系统码。,于是，以多项式形式表示的系统循环码的生成矩阵为：,其中,r,n-i,(x),是g(x)除x,n-i(,i=1,2,，k),所得的余式。,8/7/2024,数字通信原理,编码实现(见图P251，图93),译码,：,设发送码字T(x)=x,r,m(x)+R(x)，接收码字为A(x),检错：,用g(x)去除接收到的码组A(x)，根据余式r(x)是否为0，判断传输正误；,当超出检错能力，也有r(x)=0，称不可检错误；,组成见P252，图94；,纠错：,较之检错要复杂得多,要求每个可纠正的错误必须与一个特定的余式建立一一对应关系，这样才能纠正错码，计算错误图样来判断错码位置；,常用循环码有,费尔码,(Fire)，能纠三个随机错误的,高莱码,(Golay)，是(23,12)码；另外还有一种为,BCH码,，可纠多个错；,RS码,等；,8/7/2024,数字通信原理,例1：设（7,4）线性码的生成矩阵,当信息位为0001时，试求其后的监督位。,例2：求上例的监督矩阵；,例3：试求(7,3)循环码的生成多项式和生成矩阵。,例题,8/7/2024,数字通信原理,例4：已知（7，4）循环码的全部码组为：,试写出该循环码的生成多项式g(x),和生成矩阵G，并将G化成典型矩阵。,例题,8/7/2024,数字通信原理,缩短循环码,在(n，k),循环码的2,k,个码组集合中，选择前i个信息位为0的所有码组（共2,k-i,个），组成一个新的码组集合，这一新的码组集合就构成了(n-i，k-i)码，称它为(n，k)的,缩短循环码,。,例如要构造一个能够纠正一位错误的(12，8）码，我们可以从（15，11）汉明码中挑出前三位均为0的码组来构成。,8/7/2024,数字通信原理,在(n，k)的缩短循环码中，每一个码组,必定能被g(x)除尽,（,注,：,g(x),是原循环码的生成多项式,）,每一个码组是原来循环码的码组，只是这码组的前i个信息码元为0，所以它必定能被g(x)除尽。,换言之，所有次数小于n-i次，且能被g(x)除尽的多项式都是(n-i，k-i)缩短循环码的码多项式。,在(n，k)的缩短循环码中，所有码组的前i位为0，故发送时可不发送这i个0，仅传输后面的n-i位码元。,(n-i，k-i)码的纠检错能力不低于原来的(n，k)循环码的纠检错能力。,缩短循环码的所有码组是原来循环码组集合中的一部分，且监督码元位数没变。,8/7/2024,数字通信原理,缩短循环码的生成矩阵可从原循环码的典型生成矩阵中除去前i行和前i列得到。,例如（7，3）循环码的一种典型生成矩阵为：,除去其第一行第一列，便得到（6，2）缩短循环码的生成矩阵G,（6,2）,。,缩短循环码的码组之间并,不一定存在循环关系,。,8/7/2024,数字通信原理,循环码的检错能力,能检出全部的单个错误：,对应一位错码的错码多项式E(x)=x,i,，,而多于一项的生成多项式g(x)=+1，显然x,i,除以g(x)的余数不会等于0，也即能检测出全部单个错码。,能检出全部离散的二位错：,对应的错码多项式E(x)=x,i,+x,j,=x,i,(1+x,j-i,)，只要选取的g(x),不能除尽(x,j-i,+1)，,且(n-k)(j-i),能检出全部的奇数个错码：,含有奇数项错码的多项式必不含,(x+1)因子，只要选取的g(x)含有(x+1)因子,能检测所有长度不超过(n-k),的突发错误：,突发长度不大于b的突发错误对应的错码多项式 为,E(x)=x,i,(e,b-1,x,b-1,+e,b-2,x,b-2,+e,1,x+1)=x,i,E,1,(x),由于g(x)除不尽x,i,；g(x),为n-k次多项式，只要E,1,(x),的次数b-1不超过(n-k-1)次，g(x)便除不尽E,1,(x)。,也就是说，能检测长度不超过(n-k)的突发错误。,8/7/2024,数字通信原理,经常,不断地学习,你就什么都知道。你知道得越多,你就越有,力量,Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will,Be,写,在最后,谢谢你的到来,学习并没有结束，希望大家继续努力,Learning Is Not Over.I Hope You Will Continue To Work Hard,演讲人：,XXXXXX,时 间：,XX,年,XX,月,XX,日,