CRC校验算法详解及代码实现_x8 + x5 + x4 + 1

CRC校验算法详解及代码实现

一、 CRC校验算法前置知识

在学习CRC校验算法之前，先复习一下CRC会涉及的主要几个主要的算法。

1. 异或

异或，就是不同为1，相同为0，运算符号是^。
0^0 = 0
0^1 = 1
1^1 = 0
1^0 = 1

异或运算存在如下几个规律，需要了解。

1. 0^x = x 即0 异或任何数等于任何数
2. 1^x = ~x 即1异或任何数等于任何数取反
3. x^x = 0 即任何数与自己异或，结果为0
4. a ^ b = b ^ a 交换律
5. a ^ (b ^ c) = (a ^ b) ^c 结合律

2. 模2加法

模2加法相对于普通的算术加法，主要的区别在模2加法，不做进位处理。具体结果如下。
0+0 = 0
0+1 = 1
1+1 = 0
1+0 = 1
我们发现模2加法的计算结果，同异或运算结果一模一样。进一步推演，我们会发现，异或运算的5个规律，同样适合于模2加法。这里，就不在一一列举了。

3. 模2减法

模2减法相对于普通的算术减法，主要的区别在模2减法，不做借位处理。具体结果如下。
0-0 = 0
0-1 = 1
1-1 = 0
1-0 = 1
我们发现模2减法的计算结果，同模2加法，以及异或的运算结果一模一样。进一步推演，我们会发现，异或运算的5个规律，同样适合于模2减法。这里，就不在一一列举了。

4. 模2除法

模2除法相对于普通的算术除法，主要的区别在模2除法，它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。下面是一个模2除法的示例。被除数是101001000，除数1101。

选取被除数前面的1010模2除以除数1101，因最高为是1，所以，得到商1，余数通过1010和1101的模2减法获得，根据前面的模2减法运算的介绍，其运算结果和异或运算一模一样。因此，得到余数：1010 ^ 1101 = 0111。去掉最高位的0，得到111，再将上面被除数的下一位，即0拿下来，得到1110。1110模2除以1101，得到商1，余数1110 ^ 1101 = 0011。除掉最高为的0，拿下被除数的下一位，即1，得到0111。此时，因为最高位是0，所以得到商0，余数0111 ^ 0000 = 0111。去掉最高为的，再和被除数的下一位结合，继续模2除法。按照上图依次计算，可以得到最终的商110101，余数001。
从上面的示例，我们看到一个规律：每循环一次模2计算，如果得到的被除数最高位是0，则一轮循环使用0000作为除数。如果得到的被除数最高位是1，则下一轮循环除数使用1101。这样可以保证每一轮循环被除数都能向右平移一位，直到循环到被除数最后一位。
根据之前章节中介绍的异或运算的几条规律，我们可以很容易得到一个结论，如果我们将模2除法的余数和被除数的最后几位（与余数的位数一下，本例中就是3）异或之后，得到一个新的数，这个新的数，再使用模2除法除以除数1101，即可整除，即余数为0。

二、 CRC校验算法及实现

CRC校验的根本思想就是先在要发送的帧后面附加一个数（这个就是用来校验的校验码），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数值整除（注意，这里不是直接采用二进制除法，而是采用 “模2除法”）。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。

具体来说，CRC校验原理就是以下几个步骤：

1. 先选择（可以随机选择，也可按标准选择，具体在后面介绍）一个用于在接收端进行校验时，对接收的帧进行“模2除法”运算的除数（是二进制比较特串，通常是以多项方式表示，所以CRC又称多项式编码方法，这个多项式也称之为“生成多项式”）。
2. 看所选定的除数二进制位数（假设为k位），然后在要发送的数据帧（假设为m位）后面加上k-1位“0”，然后以这个加了k-1个“0“的新帧（一共是m+k-1位）以“模2除法”方式除以上面这个除数，所得到的余数（也是二进制的比特串）就是该帧的CRC校验码，也称之为FCS（帧校验序列）。但要注意的是，余数的位数一定要是比除数位数只能少一位，哪怕前面位是0，甚至是全为0（附带好整除时）也都不能省略。
3. 再把这个校验码附加在原数据帧（就是m位的帧，注意不是在后面形成的m+k-1位的帧）后面，构建一个新帧发送到接收端，最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数，如果没有余数，则表明该帧在传输过程中没出错，否则出现了差错。

从上面可以看出，CRC校验中有两个关键点：
一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；
二是把原始帧并追加k-1位"0"后得到的新帧与上面选定的除数进行模2除法运算，计算出CRC。
前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”，如在IBM的SDLC（同步数据链路控制）规程中使用的CRC-16（也就是这个除数一共是17位，这样的话，得到的余数的位数就是17-1=16）生成多项式g（x）= x16 + x15 + x2 +1（对应二进制比特串为：11000000000000101）。

理论上，使用上述CRC校验步骤的第二步计算CRC的时候，需要将所有的二进制序列（包括后加的k-1个0）作为一个整体按照第一章节中模2除法的方法，除以选定的除数。但是，考虑模2除法中实际使用的运算其实一直都是按位异或，结合异或运算的结合律，我们逐个bit逐个bit地将作为被除数的二进制序列的每个bit依次引入，也可以逐个字节逐个字节的引入。下面是通过逐个字节引入方式计算CRC的代码实现，假设校准使用的多项式为x8+x5+x4+1 (对应二进制为: 0b100110001，对应HEX值为0x131)。

/***************************************
*@DESCRIPTION: -- CRC8计算，
*
*@Parameters: -- *data_ptr：待计算CRC8的数据
*		         len：待计算CRC8数据的长度
*
*@Return: --无
****************************************/	
unsigned char calculate_crc8(unsigned char *data_ptr, unsigned char len)
{
  unsigned int i;
  unsigned char j;
  unsigned char crc = 0x00;
  for (i=0; i<len; i++)
  {
    crc ^= *data_ptr;
    data_ptr++;
    for (j=8; j>0; j--)
    {
      if (crc & 0x80)
      {
        crc <<= 1;
        crc ^= 0x31;    // 0x131最高位1去掉，只与低8bit的0x31异或即可。
      } // if (crc & 0x80)
      else
      { 
        crc <<= 1;
      /*当最高bit为0时，则crc与0按位异或，仍为crc，所以，没有语句"crc ^= 0x31;”。*/
      } // else
    } // for (j=8; j>0; j--)
  } // for (i=0; i<len; i++)
  return crc;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34