循环冗余校验CRC算法分析及实现

李晓珍 苏建峰

1，中国科学院研究生院 100080

2，中国科学院国家授时中心 710600

循环冗余校验CRC算法分析及实现

李晓珍1苏建峰2

1，中国科学院研究生院 100080

2，中国科学院国家授时中心 710600

在数据通信与网络中，为了尽可能地降低通信的误码率，提高数字通信的可靠性，可以采用一种循环冗余校验码CRC（Cyclic Redundancy Ch）eck，简称循环码或CRC码。由于它是一种编码简单，且高效、可靠的差错控制方法，检错能力强，误码概率低，因而被广泛应用于工业测控及数据通信领域。本文阐述用循环冗余校验CRC进行差错控制的原理，CRC算法分析及CRC算法的C++程序设计方法。

循环冗余校验；CRC算法；差错控制

1 引 言

在数据通信和计算机通信过程中，由于信道上各种噪声和干扰等复杂因素的影响，使接收端收到的信息与发送端发送的信息不一致，即接收端收到的信息产生了误码。用误码率（PC）来度量信道传输信息的准确度，即

PC=错误接收码元数/接收码元数。

为了尽可能地降低通信的误码率，提高数字通信的可靠性，往往要采用差错控制编码（又叫信道编码）。用差错控制编码可以发现可能产生的误码（检错码），或发现并纠正错码（纠错码）。

差错控制的目的是提高通信的可靠性。差错控制最常用的方法有三种：自动请求重发方式（ARQ）、向前纠错方式（FEC）和混合纠错方式（HEC）。其中FEC和HEC是基于纠错编码，而ARQ是基于检错编码。

FEC依赖于在发送码字中有控制地加入冗余信息。信号在噪声信道中进行传输时会产生误码现象，从而需要进行误码检测和纠正。不管接收码字的译码是否成功，接收机都不进行任何进一步处理。因此，使用于FEC的信道编码技术只要求发射机和接收机之间是单向的链接。

ARQ的基本思想完全不同于FEC。ARQ采用冗余的目的仅仅是为了进行误码检测。当在传输的码字中检测到错误时，接收机就要求重传错误的码字，这就需要使用一条返回路径（反馈信道）。因此，ARQ只能用于半双工或全双工的链路。实现检错功能的差错控制方法有很多，常用的有：奇偶校验、校验和检测、重复码检验、横比码校验、行列冗余码校验等。

HEC是FEC和ARQ的结合。

为了不破坏数据的完整性，差错控制借助于前向纠错FEC的方法来实现。图1给出了采用这种方法的数字通信系统模型。离散信源产生二进制的信息，发射几种的信道编码器收到比特信息后，按照指定的规则加上冗余发送到接收端。接收机中的译码器对收到的数据进行误码检测和纠错。

循环冗余校验CRC是由分组线性码的分支而来，其主要应用是二元码组。由于检错能力强，误判概率很低等优点，被广泛应用于工业测控和数据通信领域。下面重点介绍CRC校验的原理、算法分析，及其C++源程序设计。

2 CRC算法原理

CRC码是一种线性、分组的系统码。在K位信息码之后再拼接R位的校验码，整个编码长度为N 位，因此，这种编码又叫（N,K）码。CRC校验采用多项式编码方法，被处理的n比特的数据块可以看作是一个n-1阶的二进制多项式。例如一个8比特的二进制数10111001可以表示为：x7+x5+x4+x3+1。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进、借位，和逻辑异或运算一致。

模2除步骤如下：

1）用除数对被除数最高几位做模2减，没有借位。

2）除数右移一位，若余数最高位为1，商为1，并对余数做模2减。若余数最高位为0，商为0，除数继续右移一位。

3）一直做到余数的位数小于除数时，该余数就是最终余数。

对于一个给定的（N,K）码，可以证明存在一个最高次幂为N-K=R的多项式G(X)。根据G(X)可以生成K为信息的校验码，而G(X)叫做这个CRC码的生成多项式。

假设待发送的K位信息多项式用C(X)表示，将C(X)左移R位，则可表示为C(X)*2R，这样C(X)的右边就会空出R位，这就是校验码的位置。通过C(X)*2R除以生成多项式G(X)得到的余数就是校验码。Q(X)为商，R(X)为余数。即

图1 数字通信系统的简化模型

在发送端发送信息时，将校验码R(X)加到信息码C(X)之后一同发出。并将这时发出的信息称为T(X)码，其码元形式如下。T(X)正好能被G(X)整除。

接收方收到信息码为T’(X)。如果传输中未发生错误，则接收码T’(X)与发送码T(X)相同，故能被G(X)整除；如果传输中发生错误，则接收码T’(X)与发送码T(X)不相同，且不能被G(X)整除。因此，我们就以T’(X)除以G(X)的余数是否为0来判断接收码元中是否有错误。也有可能收到的错误码元除以G(X)余数为0，这种问题是CRC所不能解决的，只能通过选择G(X)和增加冗余位来降低这种错误的概率。

3 CRC算法分析

CRC码是用待发送的二进制数据C(X)左移R位，然后除以生成多项式G(X)，得到的余数就是CRC码。CRC码的具体生成步骤如下：

1）将x的最高幂次为R的生成多项式G(X)转换成对应的R+1位二进制数。

2）将待发送的二进制数据C(X) 左移R位，相当于对应的信息多项式C(X)*2R。

3）用生成多项式（二进制数）对信息码做模2除，得到R位的余数R(X)。

4）将余数拼接到信息码左移后空出的位置，得到完整的CRC码。

例如，假设使用的生成多项式是G(X)=x3+x+1，4位的原始报文为1010，求编码后的报文。

解的过程如下：

1）将生成多项式G(X)=x3+x+1转换成对应的二进制数1011.

2）生成多项式有4位，要把原始报文C(X)左移3位变为1010000.

3）用生成多项式对应的二进制数对左移3位后的原始报文进行模2除。

4）得到余数011，即校验码。

5）编码后的报文（C R C码）为1010011

通过CRC编码规则可以看出，CRC编码实际上是将待发送的K位二进制数据C(X)转换成了可以被生成多项式G(X)除尽的K+R位的二进制多项式C(X)*2R，所以，解码时，可以用接收到的数据除以G(X)，如果余数为0，则表示传输过程没错误，如果余数不为0，则表示传输过程肯定存在错误。解码时，将接收到的二进制数据去掉尾部的R位数据，得到的就是原始的二进制数据信息。

4 CRC算法性能分析

生成多项式的选取会影响检错纠错的性能。生成多项式应该满足下列要求：任何一位发生错误都应使余数不为0；不同位发生错误应当使余数不同；应满足余数循环规律。

生成多项式的幂次越高，其检错能力越强。若生成多项式G(X)的最高幂次为R，则该CRC校验码的检错性能如下：

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

2）可检测出所有单个突发错误。

3）可检测出所有两个错误。

4）可检测出所有长度小于等于R个比特的突发错误。

5）对于长度等于R+1个比特的突发错误，其漏检率仅为1/2r-1。

6）对于长度大于等于R+1个比特的突发错误，其漏检率仅为1/2r。

CRC码具有良好的检错能力，因而在工业测控和数据通信领域得到了广泛的应用。下面是已经成为国际标准的CRC码生成多项式：

CRC—16 为美国采用，而CRC—CCITT为欧洲国家所采用，CRC—32大都被采用在一种

称为Point-to-Point的同步传输中。在实际应用，可根据需要来选用相应的生成多项式。

5 结束语

CRC校验由于实现简单，纠错能力强，被广泛应用于各种数据校验场合及工业测控领域。本文阐述了CRC的校验原理及算法性能分析，并给出了用C++实现的CRC-14源程序，已在PC机上验证通过。并且中科院国家授时中心“BPL长波授时系统现代化改造项目”中，用到了CRC编码技术。用软件实现的CRC不仅可以降低成本，还可广泛应用于微机及各种数据通信领域，为系统长期稳定运行提供了可靠保障。

[1] 李永忠，苏惠娟. CRC在数据通信中的应用及软件实现. 西北民族学院学报.1998.19（1）

[2] 李寿强 .循环冗余校验CRC的算法分析及其实现方法. 成都电子机械高等专科学校学报.2003年第4期

[3] 瞿中告，袁威，徐问之. CRC算法在计算机网络通信中的应用. 微机发展.2002年第2期

[4] 张平安.16位循环冗余校验码CRC的原理和性能分析 .山西科技.2005年第5期

10.3969/j.issn.1001-8972.2010.13.041