CRC编码多项式生成.doc

水平垂直奇偶校验水平垂直奇偶校验是在结合水平奇偶校验和垂直奇偶校验的基础上形成的一种校验方法。它是在一批字符传送之后,另外增加一个称为“方块校验字符”的检验字符,方块校验字符的编码方式是使所传输字符代码的每个纵向列中位代码的“1”的个数成为奇数(或偶数)。假设数据格式及其发送顺序如图5所示,如果水平和垂直方向上都使用偶校验,则水平垂直奇偶校验的编码规则如图6所示。图5水平垂直奇偶校验时数据格式及其发送顺序图6水平垂直奇偶校验法举例式中,m为码字的定长位数,n为码字的个数。设水平垂直奇偶校验的编码效率为R,则: 水平垂直奇偶校验又称为纵横奇偶校验。它能检测出传输过程中发生的所有3位或3位以下的错误、奇数个错误、大部分偶数个错误以及突发长度≤m+1的突发错误,可使误码率降至原误码率的百分之一到万分之一,有较强的检错能力,但是有部分偶数个错误不能检测出来。水平垂直奇偶校验还可以自动纠正差错,使误码率降低2~4个数量级,适用于中、低速传输系统和反馈重传系统,被广泛用于通信和某些计算机外部设备中。 (CRC,CyclicRedundancyCheck)法由分组线性码的分支而来,主要应用于二元码组。它是利用除法及余数的原理来作错误侦测(ErrorDetecting)的。这是一种比较精确、安全的检错方法,能够以很大的可靠性识别传输错误,并且编码简单,误判概率很低,但是这种方法不能够校正错误。循环冗余校验法在通信系统中得到了广泛的应用,特别适用于传输数据经过有线或无线接口时识别错误的场合。,它不产生奇偶校验码,而是将整个数据块当成一个连续的二进制数据M(x),在发送时将多项式M(x)用另一个多项式(被称为生成多项式G(x))来除,然后利用余数进行校验。从代数的角度可将M(x)看成是一个多项式,即M(x)可被看作系数是0或1的多项式,一个长度为昭的数据块可以看成是xm-1到x0的m次多项式的系数序列。例如一个8位二迸制数可以表示为:1x7+0x6+1x5+1x4十0x3+1x2+0x+1。实际应用时,发送装置计算出CRC校验码,并将CRC校验码附加在二进制数据M(x)后面一起发送给接收装置,接收装置根据接收到的数据重新计算CRC校验码,并将计算出的CRC校验码与收到的CRC校验码进行比较,若两个CRC校验码不同,则说明数据通信出现错误,要求发送装置重新发送数据。该过程也可以表述为:发送装置利用生成多项式G(x)来除以二进制数据M(x),将相除结果的余数作为CRC校验码附在数据块之后发送出去,接收时先对传送过来的二进制数据用同一个生成多项式G(x)去除,若能除尽即余数为0,说明传输正确;若除不尽说明传输有差错,可要求发送方重新发送一次。其工作过程如图7所示。图7循环冗余校验法的工作方法采用循环冗余校验法,能检查出所有的单位错误和双位错误,以及所有具有奇数位的差错和所有长度小于等于校验位长度的突发错误,能查出99%以上比校验位长度稍长的突发性错误。其误码率比水平垂直奇偶校验法还可降低1~3个数量级,因而得到了广泛采用。 CRC校验码的计算是一种循环过程。CRC校验的计算包括了要计算其CRC值的数据字节以及所有前面的数据字节的CRC值。数据块中的