CRC原理详解(附crc16校验代码) |
您所在的位置:网站首页 › 土建工程师的面试问题和答案 › CRC原理详解(附crc16校验代码) |
CRC原理详解
算法原理查表法反向算法附录1:crc16校验表及用法
算法原理
Cyclic Redundancy Check循环冗余检验,是基于数据计算一组效验码,用于核对数据传输过程中是否被更改或传输错误。 假设数据传输过程中需要发送15位的二进制信息g= 101 0011 1010 0001,这串二进制码可表示为代数多项式g(x) = x14 + x12 + x9 + x8 + x7 + x5 + 1,其中g中第k位的值,对应g(x)中xk 的系数。将g(x)乘以xm,既将g后加m个0,然后除以m阶多项式h(x),得到的(m-1)阶余项r(x)对应的二进制码r就是CRC编码。 h(x)可以自由选择或者使用国际通行标准,一般按照h(x)的阶数m,将CRC算法称为CRC-m,比如CRC-32、CRC-64等。 g(x)和h(x)的除运算,可以通过g(x)和h(x)做xor(异或)运算。比如将1 1001与1 0101做xor运算:
通过示例,可以发现一些规律,依据这些规律调整算法: 每次迭代,根据
g
k
g_k
gk的首位决定b,b是与
g
k
g_k
gk进行运算的二进制码。若
g
k
g_k
gk的首位是1,则b=h;若
g
k
g_k
gk的首位是0,则b=0,或者跳过此次迭代,上面的例子中就是碰到0后直接跳到后面的非零位。 每次迭代,
g
k
g_k
gk的首位将会被移出,所以只需考虑第2位后计算即可。这样就可以舍弃h的首位,将b取h的后m位。比如CRC-8的h是1 1101 0101,b只需是1101 0101。 个人理解扩展:根据item1,
g
k
g_k
gk是1,而常用的h首位也是1,所以首位的nor运算结果必定是0,为了提高运算速度,运算时忽略
g
k
g_k
gk与h的首位 每次迭代,只取
g
k
g_k
gk的前m位作运算,所以构建一个m位的寄存器S,此寄存器储存
g
k
g_k
gk的前m位。每次迭代计算前先将S的首位抛弃,将寄存器左移一位,同时将g的后一位加入寄存器。若使用此种方法,计算步骤如下: ※蓝色表示寄存器S的首位,是需要移出的,b根据S的首位选择0或者h。黄色是需要移入寄存器的位。S’是经过位移后的S。 查表法同样是上面的那个例子,将数据按每4位组成1个block,这样g就被分成6个block。 下面的表展示了4次迭代计算步骤,灰色背景的位是保存在寄存器中的。 B 23 B_{23} B23 = 0011 1010 b 1 b_1 b1 = 0000 0000 b 2 b_2 b2 = 0101 0100 b 3 b_3 b3 = 1010 1010 b 4 b_4 b4 = 1101 0101 b’ = b 1 b_1 b1 xor b 2 b_2 b2xor b 3 b_3 b3xor b 4 b_4 b4 4次迭代对 B 23 B_{23} B23 来说,实际上就是让它与 b 1 b_1 b1, b 2 b_2 b2, b 3 b_3 b3, b 4 b_4 b4做了xor计算,既: B 23 B_{23} B23 xor b 1 b_1 b1 xor b 2 b_2 b2 xor b 3 b_3 b3 xor b 4 b_4 b4 可以证明xor运算满足交换律和结合律,于是: B 23 B_{23} B23 xor b 1 b_1 b1 xor b 2 b_2 b2 xor b 3 b_3 b3 xor b 4 b_4 b4= B 23 B_{23} B23 xor ( b 1 b_1 b1 xor b 2 b_2 b2 xor b 3 b_3 b3 xor b 4 b_4 b4) = B 23 B_{23} B23 xor b’ b 1 b_1 b1是由 B 1 B_1 B1的第1位决定的, b 2 b_2 b2 是由 B 1 B_1 B1迭代1次后的第2位决定(既是由 B 1 B_1 B1的第1和第2位决定),同理, b 3 b_3 b3和 b 4 b_4 b4都是由 B 1 B_1 B1决定。通过 B 1 B_1 B1就可以计算出b’。另外, B 1 B_1 B1由4位组成,其一共有 2 4 2^4 24=16种可能值。于是我们就可以想到一种更快捷的算法,事先将b’所有可能的值,16个值可以看成一个表;这样就可以不必进行那4次迭代,而是用 B 1 B_1 B1查表得到b’值,将 B 1 B_1 B1移出, B 3 B_3 B3移入,与b’计算,然后是下一次迭代。 可看到每次迭代,寄存器中的数据以4位为单位移入和移出,关键是通过寄存器前4位查表获得 ,这样的算法可以大大提高运算速度。 上面的方法是半字节查表法,另外还有单字节和双字节查表法,原理都是一样的——事先计算出28或216个b’的可能值,迭代中使用寄存器前8位或16位查表获得b’。 反向算法之前讨论的算法可以称为正向CRC算法,意思是将g左边的位看作是高位,右边的位看作低位。G的右边加m个0,然后迭代计算是从高位开始,逐步将低位加入到寄存器中。在实际的数据传送过程中,是一边接收数据,一边计算CRC码,正向算法将新接收的数据看作低位。 逆向算法顾名思义就是将左边的数据看作低位,右边的数据看作高位。这样的话需要在g的左边加m个0,h也要逆向,例如正向CRC-16算法h=0x4c11db8,逆向CRC-16算法h=0xedb88320。b的选择0还是h,由寄存器中右边第1位决定,而不是左边第1位。寄存器仍旧是向左位移,就是说迭代变成从低位到高位。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |