使用CRC检测传输错误的方法

检测错误的最简单技术是在传输的比特中加入校验位。校验位的开销很小，而且不需要太多的计算。然而，它可能无法检测区间误差（Burst Error）。当两个或更多的比特在传输中发生改变时，它们可能会相互抵消；接收者可能无法检测到帧发生混乱的现象。因此，另一种称为循环冗余校验（Cyclic Redundancy Check，CRC）的技术经常用于错误检测。

在这种技术中，被称为生成多项式的一个字符串首先被确定下来。它被称为生成多项式，是因为CRC被看做一种多项式运算，其中输入和生成字符串表示成系数为0或1的多项式。一个生成多项式用来生成校验和，它附加于帧的末尾。接收者通过使用相同的生成多项式对输入进行检查，检测传输错误。选取生成多项式有两个准则：

1）它必须比帧长度短；

2）它必须以1开始并以1结束。

生成多项式也有其他期望的特性：

1）我们可以使用x+1作为生成多项式的因子，即生成多项式的最后2bit为11。

2）我们可以选择一个不能除尽x^m+1的生成多项式，即不是x^m+1的一个因子，这里的m表示最大帧长度。

这种算法基于除运算的一个基本性质。如果一个除运算中的余数从被除数中减去，结果对于除数来说就是可整除的。CRC在接下来的三步算法中使用了这种性质来产生校验和。

假设存在一个ibit的帧F（x）和一个kbit的生成多项式G（x）。

1）在帧的末尾处添加k-1个0。得到的多项式为M（x）=x^k-1F（x），同时其长度为m=i+k-1。

2）将M（x）除以G（x），注意这里是一个多项式除法，例如模2除法，不存在加法进位和减法借位。余数为R（x）。

3）使用模2减法将R（x）从M（x）中减去。结果就是要传输的帧，长度为m的T（x）。

目的节点接收T（x）并对它除以G（x）。如果能够除尽，即没有余数产生，就表明传输没有出现错误。CRC确保了以下几点：

1）可以检测到所有单一比特错误；(www.xing528.com)

2）当x+1是生成多项式中的一个因式时，可以检测所有颠倒奇数比特的错误；

3）当G（x）不能整除x^m+1时，所有单独的2bit错误都会检测出来；

4）所有小于k的区间误差都能检测到。

总的来说，当生成多项式选择适当时，CRC无法检测到错误的概率非常低。也有实用的硬件方案来实现算法。因此，它用于许多标准和协议栈中，例如IEEE 802。

例4-2

生成多项式G（x）：1011，k=4

输入帧F（x）：1110010100，i=10

步骤1：附加k-1个0于输入帧的尾部输入帧M（x）：1110010100000，m=13

步骤2：用G（x）除M（x）

余数R（x）：100

步骤3：从M（x）中减去R（x）

传输帧T（x）：1110010100100，m=13T（x）可以被G（x）整除。因此，如果没有出现传输错误，接收端的T（x）就能够被G（x）整除，这表示传输成功。