0011 0101 0101 *1+1=0 1-1=0
在(1)中,右数第二列可以看成是0-1=-1,因此要从高位借1,就变成(10+0)-1=1.(这就象普通
的'by-paper'十进制减法).特例(2,3)中,1+1会有正常的结果10,'1'是计算后的进位.这个值
被忽略了.特殊情况0-1应该有正常结果'-1'就要退到下一位.这个值也被忽略了.假如你对编程
有一定了解,这就象,XOR 操作或者更好. 现在来看一个除法的例子: 在普通算法中:
1001/1111000\\1101 13 9/120\\13 1001 - 09 -| ---- -- | 1100 30 | 1001 - 27 - ---- --
0110 3 -> 余数 0000 - ---- 1100 1001 - ----
011 -> 3, 余数
在CRC算法中:
1001/1111000\\1110 9/120\\14 余数为 6 1001 - ---- 1100 1001 - ---- 1010 1001 - ---- 0110 0000 - ----
110 -> 余数 (例 3)
这个除法的商并不重要,也没必要去记住,因为他们仅仅是一组无关紧要的位串.真正
重要的是余数!它就是这个值,可以说比原文件还重要的值,他就是基本的CRC.
过度到真正的CRC码计算.
进行一个CRC计算我们需要选则一个除数,从现在起我们称之为\宽度W就是最高位
的位置,所以这个poly 1001的W 是3,而不是4.注意最高位总是1,当你选定一个宽
度,那么你只
需要选择低W各位的值.
假如我们想计算一个位串的CRC码,我们想确定每一个位都被处理过,因此,我们要在目标
位串后面加上W个0位.在此例中,我们假设位串为1111.请仔细分析下面一个例子: Poly = 10011, 宽度 W=4 位串 Bitstring
Bitstring + W zeros = 110101101 + 0000
10011/1101011010000\\110000101 (我们不关心此运算的商) 10011|||||||| - -----|||||||| 10011||||||| 10011||||||| - -----||||||| 00001|||||| 00000|||||| - -----|||||| 00010||||| 00000||||| - -----||||| 00101|||| 00000|||| - -----|||| 01010|||
00000||| - -----||| 10100|| 10011|| - -----|| 01110| 00000| - -----| 11100 10011 - -----
1111 -> 余数 -> the CRC! (例 4)
重要两点声明如下:
1.只有当Bitstring的最高位为1,我们才将它与poly做XOR运算,否则我们只是将 Bitstring左移一位.
2.XOR运算的结果就是被操作位串bitstring与低W位进行XOR运算,因为最高位总为0.
算法设计:
你们都应知道基于位运算的算法是非常慢的而且效率低下.但如果将计算放在每一字节上
进行,那么效率将大大提高.不过我们只能接受poly的宽度是8的倍数(一个字节;).
可以形
象的看成这样一个宽度为32的poly(W=32): 3 2 1 0 byte +---+---+---+---+
Pop! <--| | | | |<-- bitstring with W zero bits added, in this case 32 +---+---+---+---+
1<--- 32 bits ---> this is the poly, 4*8 bits (figure 1)
这是一个你用来存放暂时CRC结果的记存器,现在我称它为CRC记存器或者记存器.你从右
至左移动位串,当从左边移出的位是1,则整个记存器被与poly的低W位进行XOR运算.(此例
中为32).事实上,我们精确的完成了上面除法所做的事情.
移动前记存器值为:10110100
当从右边移入4位时,左边的高4位将被移出,此例中1011将被移出,而1101被移入.
情况如下:
当前8位CRC记存器 : 01001101 刚刚被移出的高4位 : 1011
我们用此poly : 101011100, 宽度 W=8 现在我们用如前介绍的方法来计算记存器的新值. 顶部 记存器