几种常见的校验码

admin

1．奇/偶校验
1）基本原理

奇/偶校验包括奇校验和偶校验两种。无论是奇校验还是偶校验，校验码模型中r 只设置1位。编码时，通过设置r的具体取值（0或1）使k+1位二进制序列中1的个数为偶数或奇数；校验时，通过检查编码序列中1的个数的奇/偶性是否发生变化来判断是否发生了错误。若未发生变化，则奇/偶校验认为数据未发生错误，反之就认为发生了错误。
例：设校验信息（k=8） 为10110101，则采用奇校验得到的编码为101101010，若校验时得到的序列依然为101101010，则序列中1的个数仍然为奇数个，因此认为没有出错；若校验时得到的序列变为101100010，则序列中1的个数变成了偶数，显然不符合奇校验的规则，故认定收到的编码序列中有错。
由于奇/偶校验编码的码距为2,因此,只能检测错误而不能纠正错误。
2）特点
奇/偶校验具有下列特点：
（1）编码和校验均非常简单，对应的电路也简单，实现的代价低；
（2）冗余信息少，仅1位校验位；
（3）检测错误的标准是序列中1的个数的奇偶性，由于序列中偶数位数据同时出错时不改变序列中1的个数的奇偶性，因此，奇/偶校验不能检测偶数位同时出错的错误。因此，奇/偶校验给出的无错的错结论不一定可靠。
2．循环冗余校验CRC（Cyclic Redundancy Check）
1）编码过程

CRC具有检错与纠错功能，校验信息r的位数与被校验信息k的位数需满足下列关系：
　　 ；
CRC编码的基本步骤如下：
（1）将k位有效信息表达为多项式M（x）：
　　 ，式中 为0或1。
（2）将M（x）左移r位（注意r与k之间的约束关系），即变成 ，左移后右面的r位用来放置校验位；
（3）选择一个生成多项式G（x），其最高次幂等于r，最低次幂为0，即G（x）必须是r+1位。
注意：M（x） 与G（x）存在一对多的关系。
（4）用多项式 按模2运算法则除以生成多项式G（x），所得余数即为校验模型中的r位校验信息。
（5）按照校验模型，将被校验信息k和校验信息组合在一起，即可得到被校验信息的CRC编码。
说明：模2加/减运算就是不带进位和借位的按位二进制加法和减法运算。
例：求有效信息1100的CRC码，选择生成多项式G（x）＝1011。
解： 。被校验信息为4位，所以 ，即r>2，取r＝3，
　　
选择生成多项式
　　
按模2除法，得商Q（x）＝1110，余数R（x）＝010。
　　 ∴　　该信息的CRC码 ：
这种有效信息4位（k＝4），CRC码7位（n＝7）的循环校验码称为（7,4）码。
2）数据校验
校验部件对接收到的CRC码，用约定的多项式G（x）去除，若余数为0，表示传送正确；若余数不为0，表示出错，再由余数的值并结合循环移位来确定哪一位出错，从而加以纠正。详细步骤详见教材。
校验得到的不为零余数具有循环特性，即随机选择某位出错后的余数，在该余数后面补一位零，然后除以生成多项式，将得到下相邻下一位出错时对应的余数，继续对新余数执行上述的操作，余数最后能循环到最开始选择的那个余数，这也是为什么称循环冗余校验的原因。用下边的CRC编码可以验证上述规律，生成多项式取G（x）＝1011）。

3）关于生成多项式的选择
对于CRC校验中的生成多项式有如下特殊要求：
（1）生成多项式的最高位和最低位必须为1；
（2）CRC编码任何一位发生错误时，被生成多项式进行模2除后余数应不为0；
（3）不同位发生的错误，余数不同；
（4）对余数继续做模2除，应使余数循环。
对应于不同码距的常用生成多项式如下表所示。

3．海明校验

海明校验也具有检错与纠错功能，其中具有检测并纠正一位错误的海明校验码中校验信息r的位数与被校验信息k的位数需要满足下列关系：
与奇/偶校验编码中校验位与信息位的排列方式不同，海明校验中信息位与校验位是分组排列的。
　另外，海明校验通过指错字来定位错误并修改错误。