CRC算法原理与实现02——数学原理与模2运算

一. CRC校验的数学原理

1.1 二进制表示为特殊的多项式

在CRC中，二进制数据和多项式可以互相表示。例如，二进制数据  可表示为：

这里的的幂次对应于数据位的位置，从最高位（最左边）开始，幂次依次递减。系数为 1 表示该位为 1，系数为 0 表示该位为 0。

注意：这里的多项式是一种特殊的多项式，称为模2剩余类域上的一元多项式，其系数来自模2剩余类域 F2即{0，1}，并且只包含一个变量（通常记为x）。其加法和乘法遵循模2规则。这种多项式在编码理论、密码学和计算机科学中具有重要应用，尤其是在CRC校验和纠错码中。

1.2 预先确定的CRC生成多项式

CRC使用一个生成多项式 ，其阶数为 。例如，CRC-4（对应二进制10011）的生成多项式为：

1.3 发送方附加CRC校验码

1.4 验证接收数据能否整除CRC生成多项式

接收方需要验算一下， 收到的是否能整除，如果接收无误，有：

这里用了一个模2剩余类域上的一元多项式的加法运算规则：

即模2多项式加法等于模2多项式减法，都等价于异或运算。

可见，如果接收无误，收到的数据就能够整除生成多项式；如果接收有误，则很大概率无法整除。注意并不是有误就一定无法整除，因为可能存在不同的两组数据，对应同一个CRC码，这是CRC校验的特点之一，本文后续会说明。

二. 什么是模2运算

本章参考：模2运算_百度百科

模2运算，也称模二运算，是一种基于二进制数的算术运算，其核心特点是没有进位和借位，所有运算都按位进行，并且结果只可能是0或1。模二运算在计算机科学、通信和编码理论中广泛应用，尤其是在循环冗余校验（CRC）和纠错码中。

另外，通常模2四则运算的符号和普通四则运算符号（+-×÷）是一样的，没有使用特殊的运算符号。

2.1 模2加法

模2加法和普通加法的唯一区别是不进位，也就是对应的单bit相加，不会影响其它位，规则如下：

• 0 + 0 = 0

• 0 + 1 = 1

• 1 + 0 = 1

• 1 + 1 = 0

其余三个规则很好理解，而对于1+1=0，可以理解为1+1=10，而进位的1被丢掉了，所以在模2加法中1+1=0。

根据这个规则可以总结出：模2加法就是按位异或（XOR），或者更简单的说法：数1的数量，奇数个1相加结果是1，偶数个1相加结果是0，这个方法对于超过2个数的模2加法很实用。

举例：

• 模2加法：1101 + 1011 = 0110
• 模2加法：0011 + 1011 = 1000

2.2 模2减法

模2减法和普通减法的唯一区别是不借位，单bit相减，不影响其它位，规则如下：

• 0 – 0 = 0

• 0 – 1 = 1

• 1 – 0 = 1

• 1 – 1 = 0

其余三个规则很好理解，而对于0-1=1，可以参考模二加法来理解，减法本质来说是加法的逆运算，而模2加法中1+1=0，所以模2减法中0-1=1。

举例：

• 模2减法：1101 - 1011 = 0110
• 模2减法：0011 - 1011 = 1000

从以上说明可以总结出，模二加法和模二减法完全等价，规则完全一样，都是按位异或（XOR）。

2.3 模2乘法

乘法的本质还是加法，根据模2加法我们就可以推导出模2乘法的规则。这里直接给出规则如下：

• 0 × 0 = 0

• 0 × 1 = 0

• 1 × 0 = 0

• 1 × 1 = 1

总结一下，模2乘法是与0相乘是0，与1相乘保持不变，这个普通的二进制乘法是一样的。但在进行多bit二进制的模2乘法时，需要注意，没有进位，其余规则一样。

举例：计算 1101 × 101，结果：111001，计算过程如下：

  1101
×  101
------
  1101  （1101 × 1）
 0000   （1101 × 0，左移一位）
1101    （1101 × 1，左移两位）
------
111001  （模2加法即逐位异或）

对于模2加法，最高位可以是1或者0，而对于模2乘法，两个乘数高位的0都是没有任何意义的，它仅仅是使得乘积的高位也是0，举例：计算0101 × 011，结果：001111，计算过程如下：

  0101
×  011
------
  0101  （0101 × 1）
 0101   （0101 × 1，左移一位）
0000    （0101 × 0，左移两位）
------
001111  （模2加法即逐位异或）

可见，它和101 × 11 = 1111的区别就是高位多了两个0。

2.4 模2除法

模2除法是模2乘法的逆运算，被除数 = 商 × 除数 + 余数，可以得到：

• 余数 = 被除数 – 商 × 除数
• 商 = （被除数 – 余数）÷ 除数

模2除法规则：

1、除数首位必须为1。

2、当被除数的位数小于除数时，商0，被除数就是余数。

3、对于被除数或去除首位后的中间余数，最高位为0则商0，最高位为1则商1。

4、中间步骤的余数首位必定为0，且商一次，得到的余数就去除一次首位的0，然后按照规则3继续运算下去。

5、当余数位数小于除数位数时，除法运算结束，最终余数位数 = 除数位数 – 1。

举例：计算 0100110 ÷ 101，商为01011，余数为01。

      01011
    -------
101|0100110
    000
    ---
    0100
     101
     ---
     0011
      000
      ---
      0111
       101
       ---
       0100
        101
        ---
        001

可以看出，按照模2除法的规则，被除数高位的0，只影响商高位的0，也就是说被除数高位有几个连续的0，商原样保留，而对余数没有任何影响。

所以，在查资料的时候，我发现网上几乎所有讲解模2除法的例子中，被除数的最高位都是1，我最开始也很困惑，最高位为0不行吗？这里就说明了，被除数高位可以是0，但省掉这些0，对于求余数没有影响。

模2除法的验证可参考网站：模2除法(CRC)循环冗余校验码在线计算器