CRC算法原理和代码实现

前言

​ 由于现在的工作涉及到协议的对接，而协议使用CRC进行校验。并且在MATLAB传C的过程中有可能需要使用到CRC来校验数据。所以在这篇文章中对CRC校验的有关知识进行梳理，也是自己对这方面知识点的梳理和总结吧。

什么是CRC校验

​ CRC（Cyclic Redundancy Checksum循环冗余校验）校验是一种常用的数据校验方法，用于检测和纠正传输或存储过程中可能发生的错误。

​ CRC校验通过对数据进行一系列的计算，生成一个固定长度的校验码。发送方将原始数据和该校验码一起发送给接收方。接收方在接收到数据后，也会对接收到的数据进行CRC计算，并与接收到的校验码进行比较。如果两者相同，则说明数据在传输或存储过程中没有发生错误；如果不同，则说明数据可能存在错误或被篡改。

​ 可以想象一个例子：

​ 你将一封信件寄给朋友，但在邮递过程中有可能发生信件损坏或篡改的情况。为了确保信件的完整性和准确性，在信件中附上一个附加的校验码。这个校验码比如你可以把你这份字的字数当成检验，朋友在收到信件的时候检测一下字数对不对，不对就说明存在信件的损坏，但是字数正确也无法保证信件没有损坏，如果里面字发生笔画的问题，字数没变但是内容依然出现问题。所以CRC就是和每一个字（二进制）相关一种校验，只有有一个字发生变换，CRC也不同，这样就可以核对信件的完整性了。

协议方式

​ 循环冗余校验是一种用于校验通信链路上数字传输准确性的计算方法（通过某种数学运算来建立数据位和校验位的约定关系的 ）。

​ 发送方计算机使用某公式计算出被传送数据所含信息的一个值，并将此值 附在被传送数据后，接收方计算机则对同一数据进行 相同的计算，应该得到相同的结果。

​ 如果这两个 CRC结果不一致，则说明发送中出现了差错，接收方计算机可要求发送方计算机重新发送该数据。

CRC的优点

• CRC的应用简单高效

  • 位运算的使用：CRC校验算法主要基于位运算，如异或（XOR）和位移操作。这些位运算在硬件实现和计算机指令级别上都是非常高效和快速的，不需要复杂的乘法和除法运算。
  • 线性特性：CRC校验算法具有线性特性，即对数据进行拆分、处理和组合的过程可以并行地进行。这意味着可以同时处理多个数据块，从而提高计算效率。
  • 基于多项式除法：CRC校验算法的核心是利用多项式除法来计算校验码。多项式除法相对于传统的数值除法更加简单，且计算规则固定。通过一系列的位运算，可以高效地完成多项式除法的计算过程。
  • 可预先计算的表格：CRC校验算法中使用了一个查找表（Lookup Table），也称为预先计算表（Precomputed Table）。这个表格存储了所有可能的余数和对应的校验码，避免了重复计算。通过查表的方式，可以大大提高CRC校验的计算速度。
  • 可选择性能优化：CRC校验算法的性能可以根据需求进行优化。可以通过选择合适的生成多项式、预先计算表格的大小等方式，优化CRC校验的速度和错误检测能力。

• 强大的错误检测能力

  • CRC虽然具有良好的错误检测能力，但仍然存在一定的错误概率。无法给出具体的错误概率数值，一般情况下，对于一个正确实现的CRC校验算法，在理想的传输环境下，CRC的误码率非常低，接近于零。这意味着CRC可以有效地检测出绝大部分的传输错误。

• 应用广泛

  • 在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS（帧检错序列）采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。

CRC概念

多项式公式

​ 对于CRC标准除数，一般使用多项式（或二项式）公式表示，如下图中除数11011（poly值为0x1b）的二项式为G(X)=X4+X3+X+1，X的指数就代表了该bit位上的数据为1,（最低位为0）。这里特别注意一下位数问题，除数的位数为二项式最高次幂+1（4+1=5），这个很重要。

多项式简记式

​ 通过之前的对于的CRC基本了解后，我们可以知道多项式的对应的二项式首位必定为1，而这个1的位置一定为0，所以可以将前面的1给省略掉，这样就得到一个简记式的东西，如上图的11011的简记式就为1011，在很多实际的场景中，我们是使用简记式来表达POLY值。例如一个多项式G(X)=X16+X15+X2+1（16#18005）的poly值实际上是8005，这里使用的就是简记式。后面会对这个用法做一个说明。

数据的宽度

​ 数据的宽度的这个词很好理解，就是CRC码长度（这里的长度指二进制的位数）知道了CRC的运算概念和多项式，就可以理解这个概念了，CRC长度始终要比除数位数少1，与简记式长度是一致的。

以上的三个概念就是的我们使用CRC的所需要的常用的概念。

初始值与结果异或值

​ 在一些标准中，CRC规定了初始值，在数据进行二项运算之前，需要将计算的数据与初始值的最低字节进行异或，然后再将多项式进行计算。

​ 而在结果异或值不为0的情况下，则需要将计算得到的CRC的结果与结果异或值在进行一次异或计算，最终得到的才是我们最后的CRC的校验码。

输入值反转与输出值反转

​ 输入值反转的意思是在计算之前先将二项式反转，然后再用得到的新值和数据进行计算。如对于G(X)=X16+X15+X2+1（16#18005），其正向值为1 1000 0000 0000 0101，反转值则为1010 0000 0000 0001 1

输出值反转则是将最终得到的CRC结果反转。

​ 通常，输入值反转后的结果值也会是反转的，所以这两个选项一般是同向的，我们只有在在线CRC计算器中会看到自由选择正反转的情况存在。

常见的CRC算法

学习CRC算法的前置知识

​ 在学习的CRC算法前，我们必须存在几个前置的理论概念，这里针对基础比较弱或者零基础的小白，有基础的兄弟可以直接跳过

异或运算

​ 异或运算简说就是不同为1，相同为0，使用^符号进行表示，所以我们可以以下的二进制异或运算的结果

0^0 = 0
0^1 = 1
1^1 = 0
1^0 = 1

除了这个异或运算还存在几个规律需要记住

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

模2加法

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

模2减法

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

模2除法

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

CRC原理

CRC原理：在K位信息码（目标发送数据）后再拼接R位校验码，使整个编码长度为N位，因此这种编码也叫（N,K）码。

​ 通俗的说，就是在需要发送的信息后面附加一个数（即校验码），生成一个新的发送数据发送给接收端。这个数据要求能够使生成的新数据被一个特定的数整除。这里的整除需要引入模 2除法的概念。

那么，CRC校验的具体做法就是

（1）选定一个标准除数（K位二进制数据串）

（2）在要发送的数据（m位）后面加上K-1位0，然后将这个新数（M+K-1位）以模2除法的方式除以上面这个标准除数，所得到的余数也就是该数据的CRC校验码（注：余数必须比除数少且只少一位，不够就补0）

（3）将这个校验码附在原m位数据后面，构成新的M+K-1位数据，发送给接收端。

（4）接收端将接收到的数据除以标准除数，如果余数为0则认为数据正确。

注意：CRC校验中有两个关键点：

一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；

二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS。

前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”

循环冗余计算

​ 由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样，下面就举例，来说明CRC校验码生成过程。

​ 对于数据1110 0101（16#E5），以指定除数11011求它的CRC校验码，其过程如下：![图片]

​ 使用上面计算的校验和和消息数据，可以创建要传输的码字。

​ 有时候，我们需要填充checksum到制定的位置，这就涉及到字节序问题，建议用memcpy()进行拷贝。

代码实现（后续补充）