《差错控制原》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第7章 差错控制原理,石高涛,天津大学计算机科学与技术学院,1,差错产生的原因,信号在传输过程中会收到例如脉冲干扰、随机噪声干扰等使信号波形失真，从而使接收解调后的信号产生差错。,误比特率是指二进制比特在数据传输系统中被传错的概率，它在数值上近似等于：,P,e,=N,e,/N,其中，N为传输的二进制比特总数，Ne为被传错的比特数,信源,通信信道,信宿,数据,噪声,数据+噪声,2,差错产生的原因,两类噪声：,随机噪声：时时处处存在、幅度小、频带宽，导致产生的噪声随机、离散，前后差错之间无关联。,脉冲噪声：强度大、持续时间与数据传输中每比特的时间相比较长，因而造成错误成串出现。,信源,通信信道,信宿,数据,噪声,数据+噪声,3,主要内容,差错控制基本原理,汉明距与检错纠错,差错控制编码,差错控制方法,4,主要内容,差错控制基本原理,汉明距与检错纠错,差错控制编码,差错控制方法,5,信源编码与信道编码,在数字通信系统中，为了提高数字信号传输的有效性而采取的编码称为,信源编码,；为了提高数字通信的可靠性而采取的编码称为,信道编码,。,信源编码,：,模拟信号如果想利用数字通信系统进行传输，就需要将模拟信息源的输出转化为数字信号，而这个转化构成就称为信源编码。脉冲编码调制(PCM)、差分脉冲编码调制(DPCM)、增量调制(DM).,信道编码,：,又称差错控制编码，是在信息序列上附加上一些,监督码元，利用这些冗余的码元,，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。,6,差错控制基本原理,原始数字信号是分组传输的，例如每,k,个二进制码元为一组（称为信息组），,经信道编码后转换为每,n,个码元一组的码字(码组)，这里,n,k,，,分组码,通常表示为(,n,，,k,)，其中,n,=,k,+,r,r,是码组中监督码位的长度,n,是编码码组的总长度。,信道编码是用增加数码，利用“冗余”来提高抗干扰能力的，也就是以降低信息传输速率为代价来减少错误的，或者说是用削弱有效性来增强可靠性的。,7,增加冗余码的原因,原始数据码本身随机变化，无任何规律，通过增加冗余信息使其呈现某种规律性，从而可以在接收端进行错误检测。,考察3位二进制码，其中的八个组合可表示八种不同信息，如果只传输这三位，则任意一个组合出错都回变成另一组码，接受端无法发现错误。,许用码,000,011,101,110,禁用码,001,010,100,111,其中任一个码,一位,出错，都会变成禁用码。从而接收端,能够且只能够,检测出错误。,相当于用3位二进制表示4个信息，从而存在一位冗余。,8,增加冗余码的原因,为了能纠正错误，还需要增加冗余码元。如下表所示，若,许用码只有000,111，其余均为禁用码组,。,这相当于使用三位二进制码来代表两种不同的信息，有两位码是冗余的。,接收端可检测出2位以下的错误或者纠正1位错误,许用码,000,111,禁用码,001,010,011,100,101,111,当收到禁用码组时100时，可以认为只有一位出错，则原始信息为000，因为111任何一位出错都不会变成100，此时即,检错1位又能纠错1位,。,若认为错码不超过2位，则存在两种可能：000错1位或者111错2位。,9,检错码和纠错码,按照信道编码的不同功能，可以将它分为,检错码和纠错码,。,检错码仅能检测误码，例如，在计算机串口通信中常用到的奇偶校验码等；,纠错码可以纠正误码，当然同时具有检错的能力，当发现不可纠正的错误时可以发出出错指示。,10,主要内容,差错控制基本原理,汉明距与检错纠错,差错控制编码,差错控制方法,11,汉明距离,汉明距离又称码距，它是指两个等长二进制码组之间,对应位不同的个数,，用来描述码组之间的不同程度。,其中,a,ji,a,ki,分别为第,j,个码组和第,k,个码组的第,i,为码元;,n,为码组长度,一个码组集合中，任何两个码组间的汉明距离的最小值称为,最小码距,。,最小码距越大，差错控制能力越强。,12,汉明距离,汉明距离又称码距，它是指两个等长二进制码组之间,对应位不同的个数,，用来描述码组之间的不同程度。,许用码,000,011,101,110,许用码,000,111,最小码距为2，接收端,能够,检测出,1位错误,。,最小码距为3，接收端,能够,检测出,2位错误,。,13,汉明距和检错纠错的关系,当码字用于,检测错误,时，如果要检测,e,个错误，则分组码最小汉明距离,d,0,和,e,之间的关系：,在图中用A和B分别表示两个码距为,d,0,的码字，若A发生,e,个错误，则A就变成以A为球心，,e,为半径的球面上的码字，为了能将这些码字分辩出来，它们必须距离其最近的码字B至少有一位的差别,A,B,e,d,0,14,汉明距和检错纠错的关系,当码字用于,纠正错误,时，如果要纠正,t,个错误，则,在图中用A和B分别表示两个码距为,d,0,的码字，若A发生,t,个错误，则A就变成以A为球心，,t,为半径的球面上的码字；B发生,t,个错误，则B就变成以B为球心，,t,为半径的球面上的码字。为了在出现,t,个错误之后，仍能够分辩出A和B来，那么，A和B之间距离应大于2,t,，最小距离也应当使两球体表面相距为1。,A,B,t,d,0,t,1,15,主要内容,差错控制基本原理,汉明距与检错纠错,差错控制编码,差错控制方法,16,差错控制编码,奇偶校验码,：奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。它是由,n,-1位信息元和1位校验元组成，可以表示成为（,n,，,n,-1）。,如果是奇校验码，在附加上一个监督元以后，码长为,n,的码字中“1”的个数为奇数个；,如果是偶校验码，在附加上一个监督元以后，码长为,n,的码字中“1”的个数为偶数个。,17,奇偶校验码是最常见的检错码方式，它可以构成垂直奇偶校验、水平奇偶校验和垂直水平奇偶校验。,垂直奇偶校验：,也称为字符奇偶校验。对于单元字符代码，在字符代码最后一位加上一个奇偶校验位b,7,，使码组中的1的个数为奇数或者偶数。,接收端可以通过校验接收字符码组中的1的个数为偶数(或奇数)来判断传输是否有差错。,差错控制编码,18,垂直水平奇偶校验,又叫二维奇偶校验或方阵校验。它不仅对水平（行）方向的码元，而且还对垂直（列）方向的码元实施奇偶监督。,将信息码组排列成矩阵，每一个码组写成一行，然后根据奇偶校验原理在垂直和水平两个方向进行校验。,发送时需要将校验位和校验码发送到接收端。,1 1 0 0 1 0 1 0 0 0,0 1 0 0 0 0 1 1 0 1,0111100001,1001110000,1010101010,0,0,1,0,1,1100011110,0,19,恒比码,恒比码中的1和0的个数保持恒定比例。,数字,码字,0123456789,01101010111100110110110100011110101111000111010011,若码长为,n,，码重为,w,，则此码的码字个数为 ，禁用码字数为 。,该码的检错能力较强，除对换差错（1和0成对的产生错误）不能发现外，其它各种错误均能发现。,国际上通用的电报通信系统中，采用7中取3码，实践证明，应用这种码，使国际电报通信的误码率保持在以 10,-6,下。,20,正反码,校验码取决于信息码中1的数目，或者与信息码元相同(正码)，或者与信息码元相反(反码)。,博多码：当信息码组中有奇数个1时，校验码与信息码相同，当信息码中有欧数个1时，校验码是信息码的反码。如：11001校验码为11001，而11101校验码为00010。,接收端将接收的码组中的信息码与校验码模2加，得到一个5单位合成码组作为校验码。如果信息码奇数个1，合成码就是校验码；如果信息码是欧数个，则合成码的反码为校验码。,对根据校验码中1的个数依据下表进行判决：,21,正反码译码判决表,类型,校验码组形式,译码判决,1,全0,传输正确,2,4个1，1个0,校验码中0对应位置的1位信息码出错,3,4个0，1个1,校验码中1对应的1位监督码出错,4,其他,大于1位的传输错误,信息码 校验码,信息码有奇数个1,判决校验码,判决校验码,信息码有欧数个1取反,01101 01101,01010 10111,00000,11101,00000,00010,22,循环冗余校验编码,又称CRC码，纠错能力强，采用多项式编码的方法。目前广泛应用的一种纠错编码。,二进制可使用多项式来表示：如10111可表示为：,x,4,+,x,2,+,x,+1,多项式的系数就代表二进制10111.,对长度为,n,的二进制序列，存在一个以,x,为基的,n,-1次多项式。,000,001,010,0,1,x,100,101,111,x,2,x,2,+1,x,2,+x+1,23,在发送端，将要发送的数据比特序列作为一个多项式,T,(,x,)的系数，并选定一个,k,次幂的生成多项式,G,(,x,)。对于二进制乘法,该步意味着数据比特序列左移,k,位.,CRC基本原理,CRC生成多项式,G,(,x,)标准：使用时从中选择：,CRC-12 G(x)=x,12,+x,11,+x,3,+x,2,+1,CRC-16 G(x)=x,16,+x,15,+x,2,+1,T,(,x,),T,(,x,),x,k,k,位,T,(,x,),x,k,R,(,x,),G,(,x,),将,T,(,x,),x,k,除以生成多项式,G,(,x,),其中,Q,(,x,)为商，,R,(,x,)为余数。,将,T,(,x,),x,k,+,R,(,x,)所对应的比特序列作为一个整体发送,。,24,校验过程(接收端),在接收端，对接收序列所对应的多项式,T,(,x,),x,k,进行与发送端同样的运算，即：,比较R(x)和R(x)，如果R(x)=R(x)，认为传输正确，否则认为传输错误。,T,(,x,),x,k,R,(,x,),25,CRC例子,假设发送数据为,110011,;生成多项式为,x,4,+,x,3,+1，,k,=4，所对应的序列为11001；,将发送数据序列左移4位，新的序列为：1100110000;,按模2算法,，将生成的新序列用多项式序列去除，,Q(x),T(,x,),x,k,R(x),发送新序列为：,110011,1001,如果没有发送失败那么接收端收到的比特序列一定能被同一个多项式整除。,26,CRC的性能,CRC生成的多项式结构与检错效果已经过严格的数学分析。,能检错出全部单个错误、能检测出全部随机的2位错误,能检测出全部奇数个错误。,能检测出全部长度小于等于k位的突发错误,能以1-(1/2),k-1,的概率检测出长度为k+1位突发错误。,27,发送方将数据单元分成k段，每段,n,比特；将各段相加求和；,对和取反得到校验和,；将校验和字段附加到数据序列末尾与数据一起发送。,校验和编码,接收端将接收到的数据单元分成长度为n比特的段；将所有分段相加求和；对和求反；如果结果为0，表示传输正确。,n n n n,n n n n,28,校验和例子,例：假定要发送16位数据1010100100111001,采用8位校验和，则发送比特为：10101001,00111001,00011101,10101001,00111001,+,11100010,00011101,取反,发送端,10101001,00111001,+,00011101,00000000,取反,接收端,11111111,能检测所有奇数个错误及大多数偶数个错误，但如果某一段中的一个或多个比特损坏，下一个分段中具有相反值的对应位也被破坏，这些列的和保持不变，从而无法检测出错。,0,0101001,1,0111001,+,00011101,00000000,取反,11111111,出错情况,0,0101001,00111001,+,