CRC算法详解（1）

作为blog再次发出来，详细描述一下CRC32算法的推导过程。

CRC算法的数学基础

CRC算法的数学基础就不再多啰嗦了，到处都是，简单提一下。它是以GF(2)多项式算术为数学基础的，GF(2)多项式中只有一个变量x，其系数也只有0和1，比如：

1 *x^6 + 0*x^5 + 1*x^4 + 0*x^3 + 0*x^2 +1*x^1 + 1*x^0

= x^6 + x^4 + x + 1

加减运算不考虑进位和退位。说白了就是下面的运算规则：

0 + 0 = 0 0 - 0 = 0

0 + 1 = 1 0 - 1 = 1

1 + 0 = 1 1 - 0 = 1

1 + 1 = 0 1 - 1 = 0
看看这个规则，其实就是一个异或运算。

每个生成多项式的系数只能是0或1，因此我们可以把它转化为二进制形式表示，比如g(x)=x^4 + x + 1，那么g(x)对应的二进制形式就是 10011，于是我们就把GF(2)多项式的除法转换成了二进制形式，和普通除法没有区别，只是加减运算没有进位和退位。

比如基于上述规则计算11010/1001，那么商是11，余数就是101，简单吧。

CRC校验的基本过程

采用CRC校验时，发送方和接收方用同一个生成多项式g(x) ，g(x)是一个GF(2)多项式，并且g(x)的首位和最后一位的系数必须为1。

CRC的处理方法是：发送方用发送数据的二进制多项式t(x)除以g(x)，得到余数y(x)作为CRC校验码。校验时，以计算的校正结果是否为0为据，判断数据帧是否出错。设生成多项式是r阶的（最高位是x^r）具体步骤如下面的描述。

发送方：

1）在发送的m位数据的二进制多项式t(x)后添加r个0，扩张到m+ r位，以容纳r位的校验码，追加0后的二进制多项式为 T(x)；

2）用T(x)除以生成多项式g(x)，得到r位的余数y(x)，它就是CRC校验码；

3）把y(x)追加到t(x)后面，此时的数据s(x)就是包含了CRC校验码的待发送字符串；由于s(x) = t(x) y(x)，因此s(x)肯定能被g(x)除尽。

接收方：

1）接收数据n(x)，这个n(x)就是包含了CRC校验码的m+r位数据；

2）计算n(x)除以g(x)，如果余数为0则表示传输过程没有错误，否则表示有错误。从n(x)去掉尾部的r位数据，得到的就是原始数据。

生成多项式可不是随意选择的，数学上的东西就免了，以下是一些标准的CRC算法的生成多项式：

原始的CRC校验算法

根据多项式除法，我们就可以得到原始的CRC校验算法。假设生成多项式g(x)是r阶的，原始数据存放在data中，长度为len个bit，reg是r+1位的变量。以CRC-4为例，生成多项式g(x)=x^4 + x + 1，对应了一个5bits的二进制数字10011，那么reg就是5 bits。

reg[1]表明reg的最低位，reg[r+1]是reg的最高位。

通过反复的移位和进行除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：

改进一小步——从r+1到r

由于最后只需要r位的余数，所以我们可以尝试构造一个r位的reg，初值为0，数据data依次移入reg[1]，同时把reg[r]移出 reg。

根据上面的算法可以知道，只有当移出的数据为1时，reg才和g(x)进行XOR运算；于是可以使用下面的算法：

这种算法简单，容易实现，对任意长度生成多项式的G（x）都适用，对应的CRC-32的实现就是：

从bit扩张到byte的桥梁

但是如果发送的数据块很长的话，这种方法就不太适合了。它一次只能处理一个bit的数据，效率太低。考虑能不能每次处理一个byte的数据呢？事实上这也是当前的CRC-32实现采用的方法。

这一步骤是通往基于校验表方法的桥梁，让我们一步一步来分析上面逐bit的运算方式，我们把reg和g(x)都采用bit的方式表示如下：

考虑把上面逐bit的算法执行8次，如果某次移出的不是1，那么reg不会和g(x)执行XOR运算，事实上这相当于将reg和0执行了XOR运算。执行过程如下所示，根据hi-bit的值，这里的G可能是g(x)也可能是0。

从上面的执行过程清楚的看到，执行8次后，old-reg的高8bit被完全移出，new-reg就是old-reg的低24bit和数据data新移入的8bit和G一次次执行XOR运算所得到的。

XOR运算满足结合律，那就是：A XOR B XOR C = A XOR (B XOR C)，于是我们可以考虑把上面的运算分成两步进行：

1）先执行R高8bit与G之间的XOR运算，将计算结果存入X中，如下面的过程所示。

2）将R左移8bit，并移入8bit的数据，得到的值就是 ，然后再与X做XOR运算。

根据XOR运算的结合率，最后的结果就等于上面逐bit的算法执行8次后的结果，根据这个分解，我们可以修改逐bit的方式，写出下面的算法。