CRC16算法原理

1、CRC算法及C实现学习体会 2008-09-20 15:21:13 阅读 161 评论 0 字号：大中小订阅一、CRC算法原理CRC 校验的基本思想是利用线性编码理论，在发送端根据要传送的k 位二进制码序列，以一定的规则产生一个校 验用的监督码(既 CRC 码)r 位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位,最后发送出去。在接收端，则根据信息码和 CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。16 位的 CRC 码产生的规则是先将要发送的二进制序列数左移16 位(既乘以)后，再除以一个多项式，最后所得到的余数既是 CRC 码。假设数据传输过程中需要发送15 位的二

2、进制信息 g=101001110100001 ,这串二进制码可表示为代数多项式 g(x) = xA14 + xA12 + xA9 + xA8 + xA7 + xA5 + 1，其中 g 中第 k 位的值，对应 g(x)中 xAk 的系数。将 g(x)乘以 x-m,既将 g 后加 m 个 0,然后除以 m 阶多项式 h(x)，得到的(m-1)阶余项 r(x)对应的二进制码 r 就是 CRC码。h(x)可以自由选择或者使用国际通行标准，一般按照 h(x)的阶数 m 将 CRCS 法称为 CRC-m 比如 CRC-32、CRC-64 等。国际通行标准可以参看 http:/en.wikipedia.or

3、g/wiki/Cyclic_redundancy_checkg(x)和 h(x)的除运算，可以通过 g 和 h 做 xor (异或)运算。比如将 11001 与 10101 做 xor 运算：1U=o; o ;1 ;；1 ；0；1 ；0； 1 ; 0 10： 0 ：IVIIII明白了 xor 运算法则后，举一个例子使用CRC-8 算法求 101001110100001 的效验码。CRC-8 标准的h(x) = xA8 + xA7 + xA6 + xA4 + xA2 + 1，既 h 是 9 位的二进制串 111010101。g010100111010000100000000h1110101010

4、1001101110000100000000h 1110101010111000100000100000000h 111010101000010001000100000000h11101010101100010000000000h1110101010010111010000000h111010101g601010000100000h111010101gy0100101110000h111010101g8011111011000h111010101rQ0010001100经过迭代运算后，最终得到的r 是 10001100,这就是 CRC 效验码。通过示例，可以发现一些规律，依据这些规律调整算法：

5、1.每次迭代，根据 gk 的首位决定 b, b 是与 gk 进行运算的二进制码。若 gk 的首位是 1,则 b=h；若 gk 的 首位是 0,则b=0,或者跳过此次迭代，上面的例子中就是碰到0 后直接跳到后面的非零位。gk 首位是 1b 二 h11111011000111010101rgk 首位是 000010001100g/cb = 0011110110000011110110002.每次迭代，gk 的首位将会被移出，所以只需考虑第2 位后计算即可。这样就可以舍弃h 的首位，将 b取 h 的后 m 位。比如 CRC-8 的 h 是 111010101 , b 只需是 11010101。S 1

6、_0100111g:10100111010000100000000s 01001110b 11010101S 首位：1S 1.0011011g:10100111010000100000000s 00110111b 11010101s 首位：1S 1,1100010g:10100111010000100000000s 11000100b 11010101s 首位：1S C)0010001g:10100111010000100000000s 00100010b0S 首位：0s c)0100010g:10100111010000100000000s 01000100b0s 首位：0蓝色表示寄存器 S

7、 的首位，是需要移出的，b 根据 S 的首位选择 0 或者 h。黄色是需要移入寄存器的位。S是经过位移后的 S。查表法同样是上面的那个例子，将数据按每 4 位组成 1 个 block，这样 g 就被分成 6 个 blockgBlB2B3B4B5B6010100111010000100000000下面的表展示了 4 次迭代计算步骤，灰色背景的位是保存在寄存器中的经 4 次迭代，B1 被移出寄存器。被移出的部分，不我们关心的，我们关心的是这4 次迭代对 B2 和 B3 产生了什么影响。注意表中红色的部分，先作如下定义：B23 = 00111010bl = 00000000b2 = 01010100

8、b3 =10101010b4 =11010101b = b1 xor b2 xor b3 xor b44 次迭代对 B2 和 B3 来说,实际上就是让它们与 b1,b2,b3,b4 做了 xor 计算，既：B23 xor b1 xor b2 xor b3 xor b4可以证明 xor 运算满足交换律和结合律，于是：B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor bb1 是由 B1 的第 1 位决定的，b2 是由 B1 迭代 1 次后的第 2 位决定(既是由 B1 的第 1 和第 2 位决

9、定)，同理,b3 和 b4 都是由 B1 决定。通过 B1 就可以计算出 b。另外，B1 由 4 位组成，其一共 2M 有种可能值。于是我们就可以想到一种更快捷的算法，事先将b所有可能的值，16 个值可以看成一个表；这样就可以不必进行那 4 次迭代，而是用 B1 查表得到 b值，将 B1 移出，B3 移入，与 b计算，然后是下一次迭代。SBlB2! g: B1|B2|B3|B4|B5|B6SfB2B3iII使用 Bl 查表得到 B可看到每次迭代，寄存器中的数据以4 位为单位移入和移出，关键是通过寄存器前4 位查表获得,这样的算法可以大大提高运算速度。上面的方法是半字节查表法，另外还有单字节和双

10、字节查表法，原理都是一样的一一事先计算出 28 或 2A16个 b的可能值，迭代中使用寄存器前8 位或 16 位查表获得 b之前讨论的算法可以称为正向CRCM 法，意思是将 g 左边的位看作是高位，右边的位看作低位。G 的右边加 m 个 0,然后迭代计算是从高位开始，逐步将低位加入到寄存器中。在实际的数据传送过程中，是一边接收数据，一边计算 CR 网，正向算法将新接收的数据看作低位逆向算法顾名思义就是将左边的数据看作低位，右边的数据看作高位。这样的话需要在g 的左边加 m 个 0,h 也要逆向，例如正向 CRC-16 算法 h=0 x4c11db8，逆向 CRC-16 算法 h=0 xedb88320。b 的选择 0 还是 h,由 寄存器中右边第 1 位决定，而不是左边第 1 位。寄存器仍旧是向左位移，就是说迭代变成从低位到高位。S 00000000 g： 00000000101001110100001 s 00000001s00000010B2B3g：Bl B2 B3 B4 B5 B6B3Ab使用 B2 查表得到 B使用 B2 查表得到 Bs 末位00000000101001110100001sg00000000101001110100001b10101011 S 末位：1S10101001g：00000000101001110100001s01010011b110101