循环冗余码查看源代码讨论查看历史

循环冗余码原图链接图片来源优酷网

循环校验码（CRC码），是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。

中文名:循环冗余码

外文名:CRC码

领 域:数据通信领域

性 质:差错校验码

1. 含义

循环冗余码，又称为多项式码。CRC的工作方法是在发送端产生一个冗余码，附加在信息位后面一起发送到接收端，接收端收到的信息按发送端形成循冗余码同样的算法进行校验，如果发现错误，则通知发送端重发。

在数据存储和数据通讯领域，为了保证数据的正确，就不得不采用检错的手段。在诸多检错手段中，CRC是最著名的一种，其特点是:检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器 的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。

CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。

根据应用环境与习惯的不同，CRC又可分为以下几种标准：

1）CRC-12码；

2）CRC-16码；

3）CRC-CCITT码；

4）CRC-32码。

CRC-12码通常用来传送6-bit字符串。

CRC-16及CRC-CCITT码则是用来传送8-bit字符串，其中CRC-16为美国采用，而CRC-CCITT为欧洲国家所采用。CRC-32码大都被采用在一种称为Point-to- Point的同步传输中。

2. 生成CRC码的基本原理

任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。

常用的CRC循环冗余校验标准多项式如下：

CRC(12位) =X^12+X^11+X^3+X^2+X+1

CRC(16位) = X^16+X^15+X^2+1

CRC(CCITT) = X^16+X^12 +X^5+1

CRC(32位) = X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+ X^8+X^7+X^5+X^4+X^2+X+1

以CRC(16位)多项式为例，其对应校验二进制位列为1 1000 0000 00000101。

各多项式的系数均为二进制数，所涉及的四则运算仍遵循对二取模的运算规则。

(注：对二取模的四则运算指参与运算的两个二进制数各位之间凡涉及加减运算时均进行XOR异或运算，即：1 XOR 1=0，0 XOR 0=0，1 XOR 0=1，0 XOR 1=1，即相同为0，不同为1)

3. CRC码集选择的原则

若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码任一码字，存在且仅存在一个R次多项式g(x)，使得

V(x)=A(x)g(x)=xRm(x)+r(x);其中:m(x)为K次信息多项式，r(x)为R-1次校验多项式，g(x)称为生成多项式：g(x)=g0+g1x+g2x2+...+g(R-1)x(R-1)+gRxR发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。

4. CRC校验码软件生成方法

借助于多项式除法，其余数为校验字段。例如：信息字段代码为:1011001；对应m(x)=x6+x4+x3+1假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为:11001x4m(x)=x10+x8+x7+x4对应的代码记为：10110010000；采用多项式除法:得余数为:1010(即校验字段为：1010）发送方：发出的传输字段为:10110011010信息字段校验字段接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）如果能够除尽，则正确，给出余数（1010）的计算步骤：除法没有数学上的含义，而是采用计算机的模二除法，即，除数和被除数做异或运算10110010000/11001=111101111011100=1010

5. 特点

如果生成多项式选择得当，CRC是一种很有效的差错校验方法。理论上可以证明循环冗余校验码的检错能力有以下特点：

1）可检测出所有奇数个错误；

2）可检测出所有双比特的错误；

3）可检测出所有小于等于校验位长度的连续错误；

4）以相当大的概率检测出大于校验位长度的连续错误。