CRC 校验：从原理到实现(1) - 东大小小
CRC校验，就是循环冗余校验，Cyclic Redundancy Check，是数据通信领域中最常用的一种差错校验码，用于保障数据的完整性。其特征是信息字段和校验字段的长度可以任意选定，也就是说，不管信息序列（明文序列，plaintext或者message）有多长，只要选定某一种CRC校验，最后得到的校验序列（校验和）的长度是一定的。
通常使用的CRC校验有CRC-8、CRC-12，CRC-16，CRC-32，后面的数字就表示校验之后校验字段的长度（以bit记）。
1、CRC校验的基本原理——多项式求余运算
所有的CRC校验都是基于以下几个等式，但是发送端和接收端的工作机制的不同会使得下面的等式有一些细微变化。为了便于说明，我们选定这种机制：发送端将校验序列附在明文序列之后发出去，接收端对明文序列和校验序列做校验，结果为0说明校验正确：
发送端，
或者
接收端，
或者
M是明文序列的多项式，R是校验序列的多项式，r是校验序列多项式的最高次幂（也就是校验字段的长度，CRC-32对应的r=32，依次类推）。G是生成(Generator)多项式，对某一种确定的CRC校验，其G是固定的。
发送端用G对M做模运算（求余运算），得到校验序列R，将R附加到明文序列M之后传给接收端；接收端收到M+R的序列后么，也用G对M+R做模运算，将公式1或2带入3或4，得出结论：如果的到结果为0，说明序列正确，数据完整。
所以，CRC校验最根本的就是用生成多项式对明文多项式（或者是明文+校验序列的多项式）做除法求余计算，而它的实现方法就是用线性反馈移位寄存器（Liner Feedback Shift Register，LFSR）实现多项式的求余计算。
2、LFSR和多项式取模运算的关系
为什么用LFSR就能实现CRC校验/多项式求余运算呢？我们首先来看一个简单的LFSR，每经过一个时钟周期，3bit的移位寄存器都会按照异或逻辑由低到高做一次值的更新，左侧串行输入多项式序列M。
我们假设寄存器的初始值为（R2，R1，R0）=（0，0，1），输入序列一直为0，则寄存器的值（R2，R1，R0）会按照如下状态机跳转，遍历除000外的所有7个状态
再假设M输入在时间上展开不是全0的，而是以1开始后面有若干个0，就对应了不同的多项式序列x^n，寄存器剩余的值就是用x^3+x+1除以多项式序列对应的余数序列。
|
M在时间上展开的值 |
多项式序列M(x) |
寄存器最后的值/余数R(x) |
|
1 |
1 |
1 |
|
10 |
x |
x |
|
100 |
x^2 |
x^2 |
|
1000 |
x^3 |
x+1 |
|
10000 |
x^4 |
x^2+1 |
|
100000 |
x^5 |
x^2+x+1 |
|
1000000 |
x^6 |
x^2+1 |
如果将这张表延续下去，会看到周期性的效果：x^7对应的R(x)为1，依次类推，x^n对应的R(x)都可以用这张表中的内容来表示，有公式：
又根据伽罗华域的性质，GF(2^m)域的本原多项式为P(x) = x^8 + x^4 +x^3 + x^2 + 1，将a作为P(x)的根，则有a^8=a^4+a^3+a^2+1，所以任何多项式M(x)都可以用x^n（0<=n<=255）来表示，如下表所示：
所以任何M(x)的余数R(x)都可以x^0~x^7的余数准确的表示，所以用LFSR可以实现多项式的取模运算。
参考资料：
http://blog.sina.com.cn/s/blog_62d9edac01015lsd.html
http://blog.csdn.net/highyyy/article/details/6208227
http://www.eefocus.com/Galois/blog/10-02/184555_16c21.html