CRC校验算法

素颜马尾好姑娘i 2022-07-16 14:09 322阅读 0赞

# 基本原理及概念 #

--------------------

CRC校验算法是在通信方面常用的一种差错检测的手段。原理是在将原始帧数据发送之前，在n个bit位的原始数据后面再加上通过特定运算得到的k位校验序列，组成新的帧再发送给接受端。接受端会根据原始数据后的校验序列再次进行特定运算，若结果正确，则接受；若结果错误，则丢弃。  
![这里写图片描述][SouthEast]  
我们将上面所述的k位校验序列称为**帧检验序列FCS**。  
特定运算为**多项式模2运算**。（我更喜欢将它理解为异或运算）

CRC校验算法的重点是如何得到这k位帧检验序列，以及如何进行检测运算。

# 算法 #

--------------------

## 生成多项式 ##

一般在数据传输之前，发送端与接收端会相互约定好一个除数（也是一个二进制序列，用来进行模2算法）。这个除数就是**生成多项式**。称为G(X)，**这个多项式的最高位和最低位必须为1**。我们可以定义自己的多项式，也有规定好的。常用的有：  
CRC8=X8+X5+X4+1（100110001）

CRC-CCITT=X16+X12+X5+1（1001000000100001）

CRC16=X16+X15+X5+1（11000000000100001）

CRC12=X12+X11+X3+X2+1（1100000001101）

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

至于多项式与01序列的转换就不多讲了，二进制序列的位数就是最高次幂加1。

--------------------

## 模2算法 ##

模2算法不同于我们常用的算法，将其理解为异或算法会更加容易。不管是加法还是减法，记住一条规则：相同为0，不同为1。  
如下面的例子：  
![这里写图片描述][SouthEast 1]

--------------------

### 计算帧检验序列FCS ###

理解了上面的两个概念后，计算FCS就好说了，下面以实例来讲解：  
假设发送端与接收端约定好的生成多项式为G(X)=x4 + x +1。现要发送的原始数据为10110011，求出帧校验序列以及实际发送的帧数据。

*  我们先将生成多项式转换成 二进制序列（除数）。假设为k位。  
    例：G(X)=x4 + x +1。转换成二进制序列为10011。为5位。
 *  在原始数据后面补上k-1位个0。我们最后要得到的帧检验序列就是k-1位。  
    例：10110011补5-1=4个0得到101100110000。
 *  利用补0得到的新序列除去我们约定好的除数（10011），即进行模2运算。设得到的余数为m位。若m = k-1。则该余数就为FCS帧检验序列；若m小于k-1，在余数前面补k-1-m个0。让其等于k-1。处理完后的余数就是帧检验序列FCS。（**所以我们的FCS必须满足为k-1位**，思考一下刚才为什么我们补k-1个0？）  
    ![这里写图片描述][SouthEast 2]

--------------------

## 数据发送与接收检测 ##

通过上面的算法我们已经得到了帧检验序列0100，那么将检验序列与原始数据相结合就是我们实际发送的帧数据了。

![这里写图片描述][SouthEast 3]

接收端在接收到这个帧数据后，会拿这个二进制数再次与约定好的除数相除，若余数为0，则数据正确；若余数不为0，则结果错误。

[SouthEast]: /images/20220709/24d8a67b9f354fc6bc6356234ae729a7.png
[SouthEast 1]: /images/20220709/a54866b1242e4f9ab6d0b808d39bb352.png
[SouthEast 2]: /images/20220709/a2b80591b47e44d6bce301483af150e7.png
[SouthEast 3]: /images/20220709/e381701be51d44b5801883552967c9e0.png