循环冗余校验CRC（Cyclic Redundancy Check）是数据通信领域常用的一种数据传输检错技术。通过在发送端对数据按照某种算法计算出校验码，并将得到的校验码附在数据帧的后面，一起发送到接收端。接收端对收到的数据和校验码按照相同算法进行验证，以此判断接收到的数据是否正确、完整。

CRC简介

我们知道，数据在传输过程中可能会因为传输介质故障或外界的干扰而产生比特差错（使原来的0变为1，原来的1变为0），从而导致接收方接收到错误的数据。为尽量提高接收方收到数据的正确率，在接收数据之前需要对数据进行差错检测，仅当检测的结果为正确时才接收数据。

差错检测的方式有多种，常见的有奇偶校验、求和校验、CRC校验等。他们的工作原理都是发送端对数据按照某种算法计算出来校验码，将校验码和数据一起发送到接收端，然后接收端进行检验确定数据是否发生变化。

CRC是由W. Wesley Peterson在1961年发表的论文中提出，由于CRC校验在速度、成本、正确率等方面比其他校验方式更具有优势，因此，CRC成为计算机信息、通信领域最为普遍的校验方式。例如在标准的以太帧格式中，最后有4个字节长度的冗余位，用于存储CRC校验的值，这个冗余位又常称为帧检验序列FCS（Frame Check Sequence）。

以太帧结构

CRC是如何计算的？

CRC的思想就是先在要发送的K比特长度的数据后面附加一个R比特长度的校验码，然后生成一个新帧发送给接收端。接收端接收到新帧后，根据收到的数据和校验码来验证接收到的数据是否正确。

数据+校验码示例

当然，这个附加的校验码不是随意添加的，要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（“模2除法”）。接收端把接收到的新帧除以这个选定的除数。因为在发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。

在K比特数据后面再拼接R比特的校验码，整个编码长度为N比特，这种编码也叫(N,K)码。对于一个给定的(N,K)码，可以证明存在一个最高次幂为N-K=R的多项式g(x)，根据g(x)可以生成R比特的校验码。其算法是以GF(2)多项式算术为数学基础的，原理如下图所示。

CRC计算公式

g(x)叫做这个校验码的生成多项式。不同的CRC生成多项式，其检错能力是不同的。要使用R位校验码，生成多项式的次幂应为R。以下为常见的一些标准多项式。

常见生成多项式

这些多项式的值便是模2除法的除数。而根据这个除数获得校验码并进行校验的原理可以分为以下几个步骤：

发送端、接收端在通信前，约定好除数P，也就是前面说的多项式的值。P应该是R+1位长度；
发送端首先在原来的K位数据后面加R个0，相当于原来的数据左移了R位；
然后进行模2除法运算（其实就是异或XOR运算），将加0之后的K+R位的数除以P，循环计算，直到余数的阶数小于R，这个余数就是附加的校验码，如果长度不足R位需要在前面加0补齐；
发送端将R位校验码附加在原数据后面发送给接收方；
接收方接收到数据后，将数据以模2除法方式除以除数P。如果没有余数，说明在传输过程中没有出现错误，否则说明有错误。

下面以一个简单示例来展示CRC的计算过程：

以g(x)为CRC-4=X4+X+1为例，此时除数P=10011。假设源数据M为10110011。

在发送端将M左移4位，然后除以P。