校验算法

错误检测与修正

二．错误检测的基本原理

发送器向所发送的数据信号祯添加错误检验码，并取该错误检测码作为该被传输数据信号的函数；接收器根据该函数的定义进行同样的计算，然后将两个结果进行比较：如果结果相同，则认为无错误位；否则认为该数据祯存在有错误位。 一般说来，错误检测可能出现三种结果：

在所传输的数据祯中未探测到，也不存在错误位；

所传输的数据祯中有一个或多个被探测到的错误位，但不存在未探测到的错误位； 被传输的数据祯中有一个或多个没有被探测到的错误位。

显然我们希望尽可能好地选择该检测函数，使检测结果可靠，即：所有的错误最好都能被检测出来；如检测出现无错结果，则应不再存在任何未被检测出来的错误。

实际采用的错误检测方法主要有两类：奇偶校验(ECC)、和校验（CheckSum）和CRC循环冗余校验。

二．奇偶校验ECC 单向奇偶校验

单向奇偶校验由于一次只采用单个校验位，因此又称为单个位奇偶校验。发送器在数据祯每个字符的信号位后添一个奇偶校验位，接收器对该奇偶校验位进行检查。典型的例子是面向ASCII码的数据信号祯的传输，由于ASCII码是七位码，因此用第八个位码作为奇偶校验位。

单向奇偶校验又分为奇校验(Odd Parity)和偶校验(Even Parity)，发送器通过校验位对所传输信号值的校验方法如下：奇校验保证所传输每个字符的8个位中1的总数为奇数；偶校验则保证每个字符的8个位中1的总数为偶数。

假设某一字符的标准ASCII编码为0011000，根据奇偶校验规则，如果采用奇校验，则校验位应为1（这样字符中1的个数才能为奇数），即00110001；如果采用偶校验，校验位应为0，即00110000。

显然，如果被传输字符的7个信号位中同时有奇数个(例如1、3、5、7)位出现错误，均可以被检测出来；但如果同时有偶数个(例如2、4、6)位出现错误，单向奇偶校验是检查不出来的。

一般在同步传输方式中常采用奇校验，而在异步传输方式中常采用偶校验。 三．和校验(CheckSum)

通常用来在通信中,尤其是远距离通信中保证数据的完整性和准确性。这些数据项可以是数字或在计算检验的过程中看作数字的其它字符串。它通常是以十六进制为数制表示的形式，如：

十六进制串： 0102030405060708 的校验和是： 24 (十六进制)

如果效验和的数值超过十六进制的FF，也就是255，就要求其补码作为效验和。

累加和校验 38H（+）44H（+）45H（+）46H（+）39H（+）45H = 185H 去除进位位1 最后两位的值85H为累加和校验值，用户在数据处理时可以按长度来作接收，然后也作累加和处理，最后计算的值与接收到的值一样，则接收到的卡号为正确卡号。

三.CRC循环冗余校验

1.CRC循环冗余校验的基本原理

发送器和接收器约定选择同一个由n+1个位组成的二进制位列P作为校验列，发送器在数据祯的K个位信号后添加n个位(n

(注：对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算，即：1 XOR 1=0，0 XOR 0=0，1 XOR 0=1)

可以证明，只要数据祯信号列M和校验列P是确定的，则可以唯一确定祯检验列(也称为CRC冗余检验值)的各个位。

FCS帧检验列可由下列方法求得：在M后添加n个零后对二取模整除以P所得的余数。 例如：如要传输的M=7位列为1011101，选定的P校验二进制位列为10101(共有n+1=5位)，对应的FCS帧校验列即为用1011101 0000(共有M+n=7+4=11位)对二取模整除以10101后的余数0111(共有n=4位)。因此，发送方应发送的全部数据列为10111010111。接收方将收到的11位数据对二取模整除以P校验二进制位列10101，如余数非0，则认为有传输错误位。

2.CRC循环冗余校验标准多项式P(X)

为了表示方便，实用时发送器和接收器共同约定选择的校验二进制位列P常被表示为具有二进制系数(1或0)的CRC标准校验多项式P(X)。 (1)CRC循环冗余校验常用的标准多项式P(X) CRC(16位) = X16+X15+X2+1 CRC(CCITT) = X16+X12 +X5+1

CRC(32位) = X32+X26+X23+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1

以CRC(16位)多项式为例，其对应校验二进制位列为1100 0000 0000 0101。

注意：这儿列出的标准校验多项式P(X)都含有(X+1)的多项式因子；各多项式的系数均为二进制数，所涉及的四则运算仍遵循对二取模的运算规则。

(2)CRC循环冗余校验标准多项式P(X)的检错能力

CRC循环冗余校验具有比奇偶校验强得多的检错能力。可以证明：它可以检测出所有的单个位错、几乎所有的双个位错、低于P(X)对应二进制校验列位数的所有连续位错、大于或等于P(X)对应二进制校验列位数的绝大多数连续位错。

但是，当传输中发生的错误多项式E(X)能被校验多项式P(X)对二取模整除时，它就不可能被P(X)探测出来，例如当E(X)=P(X)时。

2.算法

循环冗余码（CRC）包含2个字节，即16位二进制。CRC码由发送设备计算，放置在发送信息的尾部，接收信息的设备在重新计算接收到信息的CRC码，比较计算得到的CRC码是否与接收到的相符，如果两者不相符，则表示出错。

CRC码的计算方法是先预置16位寄存器全是1，再逐步把8位信息进行处理。在进行CRC码计算时只用8位数据位，起始位、停止位、如果有奇偶校验位的话也包括奇偶校验位都不参与CRC码计算。

在计算CRC码时，8位数据与寄存器的数据相异或，得到的结果向低位移1字节，用0填补最高位。再检查最低位，如果最低位为1，把寄存器的内容与预置数相异或，如果最低位为0，不进行异或运算。

这个过程一直重复8次，第8次移位后，下一个8位再与现在的寄存器相异或。这个过程与上一样重复8次。当所有的数据信息处理完后，最后寄存器的内容即为CRC码值。CRC码中数据的发送接收低字节在先。

计算CRC码的步骤：

⑴预置16位寄存器为十六进制FFFF（即全为1），称此寄存器为CRC寄存器； ⑵把第一个8位数据与16位CRC寄存器相异或，把结果放入CRC寄存器； ⑶把寄存器的内容右移一位（朝低位），以0填补最高位，检查最低位； ⑷如果最低位为0，重复地3布（再次移位），如果最低位为1，CRC寄存器与多项式A001（1010 0000 0000 0001）进行异或；

⑸重复步骤3和4，直到右移8次，这样整个8位数据全部进行了处理； ⑹重复步骤2到步骤5，进行下一个8位数据的处理；

⑺最后得到的CRC寄存器即为CRC码。

本文来源：https://www.bwwdw.com/article/b5ot.html