循环冗余校验（Cyclic Redundancy Check，CRC）码是一种线性分组码，也是系统码。CRC基于二进制多项式除法。在代数编码理论中，一个码组可表示为一个多项式，码元0或1当做多项式的系数。例如，1100101表示为1·x⁶+1·x⁵+0·x⁴+0·x³+1·x²+0·x+1，即x⁶+x⁵+x²+1。一个k位的帧可以被看成从x^k-1到x⁰的k-1次多项式。

CRC码的计算方法是用事先约定的一个生成多项式函数G（x）去除0、1数据串，舍弃商，将余数作为监督位（通常称为帧校验序列FCS）。

CRC的除法是用异或逻辑实现的，即模2除法。模2除法的规则是：被除数（或部分余数）的最高位为1，则上商1；被除数的最高位为0，则上商0；当余数的位数小于除数的位数时停止运算。可见，FCS的位数与生成多项式的最高次幂相等。

CRC码的具体生成办法是：将k位的数据左移n位，低位补0，再用n+1位的生成多项式进行模2除，所得的n位余数就是FCS。k位的数据和n位的FCS组成新的k+n位的数据帧，也就是CRC码

接收端用同样的生成多项式除以接收进来的数据帧，若没有余数，则认为无错。其正确性可以用下面的方法进行验证。

定义M为要传输的数据，有k位；P为生成多项式，有n+1位；F为FCS，有n位；T为CRC形成的数据帧，有k+n位。现在证明无差错时，T/P的余数为0。

数据M左移后为2ⁿM，用P除以2ⁿM，得商Q和余数R/P：

现在把R作为FCS，即组成的数据帧T=2ⁿM+R，因此

任何一个数与其自身进行模2加，结果肯定为0。因此得到：T/P=Q，T被P整除，没有余数。上述方法得到验证。

下面举一个求CRC码的例子。

若数据M=110011（6位），生成多项式P=11001（5位），则求CRC码的步骤如下。

1）数据M左移5-1=4位，变为1100110000。

2）用生成多项式P进行模2除运算，得余数R=1001。

3）将数据M和余数R拼接，得CRC码1100111001，将其发送。(www.daowen.com)

CRC码不仅在数据通信系统中经常用做校验码，而且在其他场合也应用广泛，如压缩/解压软件的正确性、硬盘扇区存储数据的可靠性等。CRC码所用的生成多项式有不同的标准，常用的生成多项式有：

CRC-16=x¹⁶+x¹⁵+x²+1

CRC-ITU=x¹⁶+x¹²+x⁵+1

CRC-32=x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1

这些生成多项式都是由不同的标准机构制定的。CRC-16在IBM公司的产品中常用。CRC-ITU当然是ITU-T（以前写为CRC-CCITT，CCITT是ITU-T的前身）制定的。CRC-32是IEEE 802标准规定的生成多项式，以太网用的就是CRC-32。

CRC码的检错能力很强，r位生成多项式可检测出所有的单错、双错、奇数位错和突发长度小于或等于r的突发错，对于突发长度为r+1的突发错的检出概率是（1-2^-（r-1）），对于突发长度大于r+1的突发错的检出概率是（1-2^-r）。以CRC-16为例，它能够检测以下错。

1）所有的单错、双错（相邻的两位一起错）和奇数错。

2）100%的16位以内的突发错。

3）99.997%的17位的突发错。

4）99.998%的18位以上的突发错。

CRC码的生成方法有很多，图3-5是用硬件电路生成CRC码，生成多项式为CRC-ITU。

图3-5　生成CRC码的硬件电路

下面的C语言程序是对生成CRC码的硬件电路的模拟，程序本身来源于通信程序YMODEM。YMODEM是一种文件传输协议，目前很少使用。作为一个选项，该程序同时也提供了校验和的计算方法。

CRC码也可以通过查表的方法生成，以提高运算速度。其思想是根据生成多项式先生成一张表，通常表中有256项数据，CRC按字节进行运算，根据字节的值查询表项数据就可以了。表的大小与生成多项式的位数没有关系。