白话 CRC

前言

我们经常碰到 CRC 这个概念，尤其是在通信领域。但是 CRC 的原理是什么呢？我们有必要了解一下。

简介

CRC（Cyclic Redundancy Check，循环冗余校验）是一种数据错误检测方法，主要用来检测数据传输或者保存后是否出现错误。

CRC 相对于其他检测手段（如奇偶校验、算术和校验等），因其检错能力强、开销小、易于编码器和检测电路实现，从检错的正确率与性能等方面，都比其他校验方式具有优势，所以 CRC 成为计算机通信领域最为普遍的校验方式。

原理

CRC 原理看起来比较复杂难懂，因为大多数书上基本上是以二进制的多项式形式来说明。其实 CRC 原理比较简单，其根本思想就在要发送的帧后面附加一个数（这个就是 CRC 校验码），生成一个新帧发送给接收端。接收端收到数据后，采用相同的方式生成 CRC 校验码，因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。

理解 CRC，最为关键的就是理解 CRC 校验码的生成方法。 CRC 校验码生成方法是对原始数据采用特定的多项式（对应一个二进制数）进行模2除法运算，得到的余数即为 CRC 校验码。

从上面可以看出，CRC 校验中有两个关键点：一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（多项式）；二是把原始帧与上面选定的除数进行模2除法运算，计算出 CRC校验码。多项式可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为 1。

模2除法

模2除法与算术除法类似，但每一位除的结果不影响其它位，即不向上一位借位，所以实际上就是异或。

例如被除数 100101(2) 对除数 1110(2) 采用模2除法后，商为 11(2)，余数为 1。

在这里插入图片描述

CRC 校验码计算示例

由以上分析可知，既然除数是随机的，或者按标准选定，所以 CRC 校验的关键是如何求出余数，也就是 CRC 校验码。

下面以一个例子来具体说明整个过程。现假设选择的 CRC 生成多项式为 P(X) = X4 + X3 + 1，要求出二进制序列 10110011 的 CRC 校验码。下面是具体的计算过程：

（1）首先把生成多项式转换成二进制数，由P(X) = X4 + X3 + 1可以知道，它一共是5位（总位数等于最高位的幂次加1，即 4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为 1 的位，也就是这个二进制的第 4 位、第 3 位、第 0 位的二进制均为 1，其它位均为 0）很快就可得到它的二进制比特串为11001。

（2）因为生成多项式的位数为 5，根据前面的介绍，得知 CRC 校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧 10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数，即 CRC 校验码为 0100，如下图所示。注意参考前面介绍的“模2除法”运算法则。

在这里插入图片描述

（3）把上步计算得到的 CRC 校验码 0100 替换原始帧 101100110000 后面的四个 0，得到新帧101100110100。再把这个新帧发送到接收端。

（4）当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数 11001 以模2除法方式去除，验证余数是否为 0，如果为 0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。

常用CRC版本

CRC 校验码的生成关键是选择一个二进制多项式作为除数。目前不同版本的 CRC 已经有标准的二进制多项式，下面给出常用 CRC 版本：

小结

通过以上 CRC 校验原理的剖析和 CRC 校验码的计算示例，大家应该对这种看似很复杂的 CRC 校验原理和计算方法应该比较清楚了。

参考文献

[1] 百度百科.模2除法 [2] CSDN.CRC码计算及校验原理的最通俗诠释