CRC16算法原理.doc

文档介绍：CRC算法及C实现
学习体会--::阅读评论字号：大中小订阅
CRC算法原理
CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CR
r
OWlOOOllOO
经过迭代运算后，最终得到的是
通过示例，可以发现一些规律，依据这些规律调整算法:
每次迭代，根据的首位决定，是与进行运算的二进制码。若的首位是，则；若的首位是则，或者跳过此次迭代，上面的例子中就是碰到后直接跳到后面的非零位。
这就是效验码。
g左首位是
b=h
r
gk首位是
gfc
b=
每次迭代，的首位将会被移出，所以只需考虑第位后计算即可。这样就可以舍弃的首位，将取的后位。比如的是只需是。
S
g:
b
S首位：
S
g:
s「
b
S首位：
S
g:
b
S首位：
S
g:
s「
b
S首位：
S
g:
s「
b
S首位：
※蓝色表示寄存器的首位，是需要移出的，根据的首位选择或者h黄色是需要移入寄存器的位是经过位移后的S
查表法
同样是上面的那个例子，将数据按每位组成个，这样就被分成个
g
Bl
B
B
B
B
B
下面的表展示了次迭代计算步骤，灰色背景的位是保存在寄存器中的
经次迭代，B被移出寄存器。被移出的部分，不我们关心的，我们关心的是这次迭代对B和B产生了什么影响。注意表中红色的部分，先作如下定义：
B=
bl=
b=
b=
b=
b'=bxorbxorbxorb
次迭代对B和B来说,实际上就是让它们与b,b,b,b做了xor计算，既：
Bxorbxorbxorbxorb
可以证明xor运算满足交换律和结合律，于是：
Bxorbxorbxorbxorb=Bxo