CRC编码多项式生成

5． 循环冗余校验法

循环冗余校验（CRC ，Cyclic Redundancy Check）法由分组线性码的分支而来，主要应用于二元码组。它是利用除法及余数的原理来作错误侦测（Error Detecting）的。

这是一种比较精确、安全的检错方法，能够以很大的可靠性识别传输错误，并且编码简单，误判概率很低，但是这种方法不能够校正错误。循环冗余校验法在通信系统中得到了广泛的应用，特别适用于传输数据经过有线或无线接口时识别错误的场合。下面重点介绍循环冗余校验法

6． CRC 法的工作原理

循环冗余校验法是一种较为复杂的校验方法，它不产生奇偶校验码，而是将整个数据块当成一个连续的二进制数据M （x ），在发送时将多项式M （x ）用另一个多项式（被称为生成多项式G （x ））来除，然后利用余数进行校验。从代数的角度可将M （x ）看成是一个多项式，即M （x ）可被看作系数是0或1的多项式，一个长度为昭的数据块可以看成是x m-1到x 0的m 次多项式的系数序列。例如一个8位二迸制数10110101可以表示为：1x 7＋0x 6＋1x 5＋1x 4十0x 3＋1x 2＋0x ＋1。

实际应用时，发送装置计算出CRC 校验码，并将CRC 校验码附加在二进制数据M （x ）后面一起发送给接收装置，接收装置根据接收到的数据重新计算CRC 校验码，并将计算出的CRC 校验码与收到的CRC 校验码进行比较，若两个CRC 校验码不同，则说明数据通信出现错误，要求发送装置重新发送数据。该过程也可以表述为：发送装置利用生成多项式G （x ）来除以二进制数据M （x ），将相除结果的余数作为CRC 校验码附在数据块之后发送出去，接收时先对传送过来的二进制数据用同一个生成多项式G （x ）去除，若能除尽即余数为0，说明传输正确；若除不尽说明传输有差错，可要求发送方重新发送一次。其工作过程如图7所示。

图7 循环冗余校验法的工作方法

采用循环冗余校验法，能检查出所有的单位错误和双位错误，以及所有具有奇数位的差错和所有长度小于等于校验位长度的突发错误，能查出99％以上比校验位长度稍长的突发性错误。其误码率比水平垂直奇偶校验法还可降低1～3个数量级，因而得到了广泛采用。

7． 相关计算

CRC 校验码的计算是一种循环过程。CRC 校验的计算包括了要计算其CRC 值的数据字节以及所有前面的数据字节的CRC 值。数据块中的每一被校验过的字节都用来计算整个数据块的CRC 值。

从数学角度来看，CRC 校验码就是利用所谓的生成多项式G （x ）去除一个多项式M （x ）（数据字节）来获取的。CRC 校验码就是相除后所得的余项。

要计算阴位数据块M （x ）的CRC 校验码，生成多项式G （x ）必须比该多项式短，且生成多项式G （x ）的高位和低位必须为1。CRC 的基本思想是：将CRC 校验码加在数据块的尾部，使这个带CRC 校验码的多项式能够被生成多项式除尽。当接收设各收到带校验码的数据块时，用生成多项式去除，如果有余数，则数据传输出错。

计算CRC 校验码和带CRC 校验码的发送数据T ｛x ｝的算法如下：

（1）设G （x ）为r 阶，在数据块M （x ）的末尾附加r 个零，使数据块变为m ＋r 位，则相应的多项式为xrM （x ）；

（2）按模2除法用对应于G （x ）的位串去除对应于x r M （x ）的位串。

（3）按模2减法从对应于x r M （x ）的位串中减去余数（总是小于等于1）。结果就是要传送的带循环冗余校验码的数据块，即多项式T （X ）。

8. 计算举例

下面举例说明CRC 校验码和带CRC 校验码的发送数据T （X ）的计算过程，如图8所示。

图8 CRC校验码以及发送数据T （X ）的计算

设数据块M （x ）的二进制表示形式为1101011011，生成多项式G （x ）=x4＋x ＋1，则G （x ）的二进制表示形式为：10011，数据块：1101011011，除数：10011，附加4个零以后形成的数据块：[1**********]000，传输的数据块为：1 10101 101 1 1 1 10。

显然，如果利用G （x ）对发送数据T （X ）执行新的CRC 计算，所得结果为零。CRC 校验的这种独特性质可以用来检测串行数据传输中的错误。CRC 校验的—大优点是识别错误的可靠性，即使有多重错误，也只需要少量的操作就可以识别。16位的CRC 就适用于校验4000字节长的数据块的完整性。超过此长度时，性能明显下降。射频识别系统中传输的数据块都比4000字节短，这意味着除了16位的CRC 以外，也可以使用12位和8位的CRC 。

9． 常用的CRC 生成多项式

CRC 在数据通信中得到了广泛的应用。表2列出了已经成为国际标准的四种CRC 生成多项式，其中CRC －12用于字符长度为6位的情况，其余三种则用于字符长度为8位的情况。CRC －32出错的概率比CRC －16低10-5倍。由于CRC －32的可靠性，把CRC －32用于重要数据的传输十分合适，所以CRC －32在通信、计算机等领域应用十分广泛。在一些UART 通信控制芯片内都采用了CRC 校验码进行差错控制；以太网卡芯片、MPEG 解码芯片中，也采用CRC －32进行差错控制。

表2 常用的CRC 生成多项式