在一个p位二进制数据序列之后附加一个r位二进制校检码，构成一个总长为p+r的二进制序列。附加在数据序列之后的这个校检码与p位二进制序列之间存在一个特定的关系，如果因干扰等原因使得数据序列中的一些位发生错误，这种特性的关系就会破坏。因此，可以通过检查该关系，实现对接收到的数据正确性的检验。

根据校检码与p位二进制序列之间的关系，可以将通讯校检方式分为：

a. 奇偶校检：每个字节的校检码与该字节（包括校检码）中1的个数对应；

b.  累加和校检：每个数据包的校检码为该数据包中所有数据忽略进位的累加和；

c.  CRC-xx校检：每个二进制序列的校检码为该序列与所选择的GF(2)多项式模2除法的余数。

奇偶校验检测错误概率大约为50%，简单但传输效率低。奇偶校验多用于低速度数据通讯，如RS232。

累加和校验检测错误概率大概为1/256，实现简单，也被广泛的采用。

CRC校检，只要选择的除数GF(2)多项式位数足够多，检测错误的概率几乎不存在。

二、    CRC算法背景

1.  几个基本的概念

1)  帧检测序列FCS（Frame CheckSequence）:为进行差错检验而添加的冗余码。

2)  多项式模2除法：不考虑进位、错位的二进制加减法；

3)  生成多项式：当进行CRC检验时，发送方和接受方事先约定一个除数，即生成多项式G（x），常用的CRC码的生成多项式为：

CRC8=X8+X5+X4+1

CRC-CCITT=X16+X12+X5+1

CRC16=X16+X15+X5+1

CRC12=X12+X11+X3+X2+1

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

每一个生成二项式与一个二进制序列对应，如CC8对应的二进制序列为：100110001。

2.  CRC校检码的计算

设信息字段为K位，校验字段为R位，则码字长度为N(N=K+R)。设双方事先约定了一个R次多项式g(x)，则CRC码：

V(x)=A(x)g(x)=xRm(x)+r(x)

其中:   m(x)为K次信息多项式， r(x)为R-1次校验多项式。

这里r(x)对应的代码即为冗余码，加在原信息字段后即形成CRC码。

r(x)的计算方法为：在K位信息字段的后面添加R个0，再除以g(x)对应的代码序列，得到的余数即为r(x)对应的代码(应为R－1位；若不足，而在高位补0)。

计算示例:

设需要发送的信息为M = 1010001101，产生多项式对应的代码为P = 110101，R＝5。在M后加5个0，然后对P做模2除法运算，得余数r(x)对应的代码：01110。故实际需要发送的数据是101000110101110。

当接收方收到数据后，用收到的数据对P（事先约定的）进行模2除法，若余数为0，则认为数据传输无差错；若余数不为0，则认为数据传输出现了错误，由于不知道错误发生在什么地方，因而不能进行自动纠正，一般的做法是丢弃接收的数据。

3. 数学推理

    设欲传输的信息有K位,如下图所示，首先将欲传输的数据序列m(x)乘以 XR , 其中R为g(x)的最高次冥。将得到的多项式XR m(x)除以约定的多项式g(x)，忽略除法结果的“商”，取出其余数，并与XRm(x)相加，形成K+R位的发送序列，即：m’(x) = XRm(x) +r(x)。

CRC编码过程如下：

设待校验的信息码有k位，即：m = (mk-1、mk-2、mk-3……m1、m0), 多项式m(x)可表示为

m(x) = mk-1xk-1+ mk-2xk-2 +……m1x1+ m0x0   --------式（1）

用多项式g(x)的最高次幂R对应的XR 乘以m(x)，将得到式（2）

XR m(x) = mk-1xk+R-1+mk-2xk+R-2 +……m1x1+R+ m0x0+R -- 式（2）

将XR m(x) 模2除以g(x)，得到多项式商为A(x),余数为r(x)，即：

A(x)g(x) = XR m(x) +r(x) -----------------------------式（3）

余数多项式r(x)可表示为

r(x) = rR-1xR-1+rR-2xR-2 +……r1x1+ r0x0 -------------式（4）

将式（2）和式（4）代入式（3）得

A(x)g(x) = mk-1xk+R-1+mk-2xk+R-2 +……m1x1+R+ m0x0+R  + rR-1xR-1+rR-2xR-2 +……r1x1+ r0x0   -----------------------式（5）

式（5）对应的码组为K+R位，即：

N = (mk-1+ mk-2 +……m1+ m0  + rR-1+rR-2 +……r1+ r0)-式（6）

从M到N就是CRC的编码过程mk-1+ mk-2 +……m1+ m0  为k位信息码；rR-1+ rR-2 +……r1+ r0为R位校验码。

   在信息接收端，将接受到的K+R位码除以相同的多项式g(x),根据式（3）所产生的余数为0，则接受到的数据信息正确无误，否则则认为信息在传输过程中产生的误码。

    根据式（1）~式（6），CRC编码必须进行模2除运算，CRC的校验位就是模2除得到的余数，如果余数用寄存器的存数表示，模2除用异或门表示，那么通用的CRC串行电路就可以同下图所示的电路来实现。

4.  “余数初始值”和“结果异或值”

“余数初始值”就是在计算CRC值的开始，给CRC寄存器一个初始值。“结果异或值”是在其余计算完成后将CRC寄存器的值在与这个值进行一下异或操作作为最后的校验值。

三、    CRC的参数模型

CRC32 的参数模型是：Name : "CRC-32"Width : 32Poly : 04C11DB7Init : FFFFFFFFRefIn : TrueRefOut : TrueXorOut : FFFFFFFFCheck : CBF43926

NAME名称WIDTH宽度， 即 CRC 比特数POLY   生成项的简写。以 16 进制表示， 即是 0x04C11DB7。 忽略了最高位的"1"，即完整的生成项是0x104C11DB7。   重要的一点是，这是“未颠倒”的生成项！ 前面说过，“颠倒的” 生成项是 0xEDB88320。INIT   这是算法开始时寄存器的初始化预置值，十六进制表示。这个值可以直接赋值给“直驱查表法” 算法中的寄存器， 作为寄存器的初始值！REFIN   这个值是真 TRUE 或假 FALSE。如果这个值是 FALSE， 表示待测数据的每个字节都不用“颠倒”， 即 BIT7 仍是作为最高位， BIT0作为最低位。  如果这个值是 TRUE，表示待测数据的每个字节都要先“颠倒”， 即 BIT7 作为最低位， BIT0作为最高位。REFOUT   这个值是真 TRUE 或假 FALSE。如果这个值是 FALSE， 表示计算结束后， 寄存器中的值直接进入 XOROUT 处理即可。如果这个值是 TRUE， 表示计算结束后， 寄存器中的值要先“颠倒”， 再进入 XOROUT 处理。注意，这是将整个寄存器的值颠倒， 因为寄存器的各个字节合起来表达了一个值， 如果只是对各个字节各自颠倒， 那结果值就错误了。XOROUT   这是 W 位长的 16 进制数值。这个值与经REFOUT 后的寄存器的值相 XOR， 得到的值就是最终正式的 CRC 值！CHECK这不是定义值的一部分，这只是字串 "123456789"用这个 CRC 参数模型计算后得到的 CRC 值， 作为参考。   我们发现， CRC32 模型的 Init=0xFFFFFFFF， 就是说寄存器要用 0xFFFFFFFF 进行初始化，而不是 0。为什么？ 因为待测数据的内容和长度是随机的， 如果寄存器初始值为 0，那么， 待测字节是 1 字节的0x00， 与待测字节是 N 字节的 0x00， 计算出来的CRC32 值都是 0， 那 CRC 值就没有意义了！所以寄存器用0xFFFFFFFF 进行初始化， 就可以避免这个问题了！RefIn=True，表示输入数据的每个字节需要“颠倒”！ 为什么要“颠倒”， 因为很多硬件在发送时是先发送最低位 LSB 的！ 比如 UART 等。    字节顺序不用颠倒， 只是每个字节内部的比特进行颠倒。例如待测的字串是"1234"，这时也是一样先处理"1"，再处理"2"，一直到处理"4"。处理字符"1"时， 它是 0x31， 即 0011 0001， 需要先将它颠倒， 变成低位在前， 即 1000 1100，即 0x8C， 再进行处理。

也就是说， 待处理的数据是0x31 32 33 34， 颠倒后就变成 0x8C 4C CC 2C， 再进行 CRC 计算。RefOut=True， 表示计算完成后， 要将寄存器中的值再颠倒。注意， 这是将整个寄存器的值颠倒， 即如果寄存器中的值是 0x31 32 33 34， 颠倒后就变成 0x2C CC 4C 8C！XorOut=FFFFFFFF， 表示还需要将结果值与 0xffffffff 进行 XOR，这样就得到最终的 CRC32 值了！

不同的通讯方式采用不同的CRC模型，更多CRC模型：

http://reveng.sourceforge.net/crc-catalogue/

常见的三种CRC 标准用到个各个参数如下表。

四、    CRC算法的编程实现

1.  直接计算法

假设有一个4 bits的寄存器，通过反复的移位和进行CRC的除法，最终该寄存器中的值就是我们所要求的余数。

最最简单的算法：

把register中的值置0.

把原始的数据后添加w个0.

While (还有剩余没有处理的数据)

Begin

把register中的值左移一位，读入一个新的数据并置于register最低位的位置。

If (如果上一步的左移操作中的移出的一位是1)

register = register XOR Poly.

End

/****************************************************************

* 函数名             : CalcCrcDirectly

* 函数描述       : 直接计算法计算CRC-32校验码

* 输入参数     : data-待计算数据块的首地址

               size-待计算数据块的32字数量                   

* 输出结果     : 无

* 返回值       : 无

****************************************************************/

u32 CalcCrcDirectly (u32* data, u32size)

{

   u32 i,j,temp,crc = 0xFFFFFFFF;

   for(i=0; i