你知道，没有人会永远不出错。 同样，也没有永远不会出错的计算机和永远不会出错的数据。
人有认识错误就能改正的自觉，电脑上也有，但电脑没有人脑，只能用特定的方法自我修复。 这就是存在核对数字的必要性。
一般常用的校验码有奇偶校验码、CRC循环冗馀校验码、汉明校验码等。
这里只介绍使用最多的CRC循环冗馀校验码。
什么是校验码
校验码通过计算方法，发行方可以在原始数据的末尾添加一些数据，然后接收方通过计算计算出数据是否有误，将有错误的数据恢复为正确的数据。
例如，原始数据是1010，我们在其末尾添加一些数据，例如101，数据就变成了1010101，发送这个新数据； 如果发送过程中发生错误，数据变为1110101，则接收方可以根据1110101返回原始正确的数据1010。
CRC循环冗馀校验码的特点
CRC码是基于模式2运算建立编码规则的校验码。 (模式2运算可以简单地理解为异或运算。
编码方法：
1 .将原始数据用一个多项式m(x )=a*x^(n-1 ) b* x ^ (n-2 )… N*X^(1)1) P*X^(0)0)表示
例如，如果原始数据为1010，则表示为m(x )=1*X^(1)3)0* x ^ (2)=1*X^(1)0* x ^ (0)
2 .原始数据左移k位，得到m(x ) x^k，形成了n k位的信息。
上面的1010，向左移动了3位，得到了1010，000
3 .多项式m(x ) x^k除以特定生成多项式g ) x )的馀数是需要连接到原始数据末尾的CRC校验码。
示例：
已知原始数据为1100，生成多项式g(x )=1011时，求出CRC码的过程如下。
已知m(x )=1100=x^3x^2) n=4)
g(x )=1011=X^3 X^1 1
得k 1=n=4
要达到k=3，必须向左移动3位
因此，m(x ) x^3=1100,000
(m ) x ) x^3)/g ) x )的计算过程：
100，000 m (x ) x^3
是1011g(x )
-----------------
111 0多个，前0个省去； 然后，将馀数向左偏移1位，继续异或g(x )
1011g(x ) )。
-----------------
010左移1位，继续异或g(x )
10 11
-----------------
因为10k=3，所以到此为止将盈馀移动了2次。 还需要一次
最后计算的结果为010，原始数据为1100 010，最后三位是CRC代码。
在需要计算k位代码的情况下，很容易看出g(x )的位数是K 1。
最后的数据为7位，但有效数据还是4位，因此上述的1100 010代码也称为“7、4”代码，与“7、3”代码、“7、6”代码等对应。
CRC码的解码规则和纠错方法
还是刚才的例子，如果把最后出来的数据除以G(X )，剩下的数是0，这是正确的数据。
试着变更其中的1位，例如第2位。 得到1000 010。 如果将此数除以g(x )，则馀数为111，如果馀数不为0，则表示数据有误
与各位的错误对应的馀数如下所示。
序列号
N1 N2 N3 N4 N5 N6 N7
剩馀
错误位
正确的
1 1 0 0 0 1 0
000
无
错误
1 1 0 0 0 1 1
001
7
错误
1 1 0 0 0 0 0
010
6
错误
1 1 0 0 1 1 0
100
5
错误
1 1 0 1 0 1 0
011
4
错误
1 1 1 0 0 1 0
110
3
错误
1 0 0 0 0 1 0
111
2
错误
0 1 0 0 0 1 0
/p>101
1
假如我们现在收到一个错误的信息是1000 010，通过计算可以得出余数是111，但是如何得知是第几位出错了？
我们试着对余数111补0后继续除下去，发现下一次的余数变成了101，继续下去，又变成了001，以后依次出现为010，100，011。。。反复循环，这就是“循环码”名字的由来。
这样，假如N2出现错误，则出现了不为0的余数后，一方面对余数补0继续模2除，另一方面将被检测的校验码字循环左移，当余数为101(即数据的首位为0)时，通过异或门可以将其纠正后在下一次移位时送回N2。这样当移满一个循环后，就得到一个纠正后的数据了。
最后给出几个标准
在上面的计算中可以发现，G(X)的作用非常重要，生成CRC码和译码都需要它。值得指出的是，并不是随便一个(K+1)位数据都可以作为生成多项式，它要满足的条件：
1.任何一位出错，都不能使余数为0，这是非常显然的；
2.不同位发生错误后，余数不能相同；
3.对余数继续模2除，应使余数循环。
为了方便起见，也为了标准化工作，现在一般用的生成多项式有以下几个：
CRC-16 = X16 + X15 + X2 + X0 美国二进制同步系统中采用
CRC-CCITT = X16 + X12 + X5 + X0 由欧洲CCITT 推荐
CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0
下面贴出生成CRC码的代码
#include #include
using namespacestd;#define CRC_16 0x18005
//CRC-16 = X16 + X15 + X2 + X0
#define CRC_CCITT 0x11021
//CRC-CCITT = X16 + X12 + X5 + X0
#define CRC_32 0x104C11DB7
//CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0
#define CHECK_CODE 0x8000
//check_code = x15，判断被除数位数>=16//check_code是为了每次做异或运算时保证位数是足够的
unsignedlong table[256];void build_16(unsigned longpoly)
{
unsignedlongx;
unsignedlongt;/*这里是将原始数据直接写入到t中
for (unsigned long i=0; i<256; i++)
{
x = i << 8;
t = 0;
for (unsigned long j = 0; j < 8; j++)
{
if ( (x ^ t) & CHECK_CODE)
t = (t << 1) ^ poly;
else
t <<= 1;
x <<= 1;
}
table[i] = ( unsigned long ) t;
}*/
//下面的是把余数和原始数据分开的写法//原始数据只有8位
for (int i=0; i<256; i++)
{
x= i<<8;//只移8位是为了位数对齐，因为下面的运算都是低位对齐的
for (int j=0; j<8; j++)
{if (x&CHECK_CODE)
{
x<<= 1;
x= x^poly;
}else x <<= 1;
}
table[i]= (i<<16)+x;
}
}void build_32(unsigned longpoly)
{
unsignedlongx;for (unsigned long i=0; i<256; i++)
{
x= i<<24;for (unsigned long j=0; j<8; j++)
{if (x & 0x80000000) //判断位数是否足够，32位
{
x<<= 1;
x= x^poly;
}else x <<= 1;
}
table[i]= (i<<32)+x;
}
}intmain()
{
build_16(CRC_16);
build_16(CRC_CCITT);
build_32(CRC_32);for (int i=0; i<256; i++)
{if (i % 10 == 0)
cout<
printf("%lx", table[i]);
}return 0;
}