我学习CRC32CRC16CRC原理和算法的总结与WINRAR结果.PDF

我学习CRC32、CRC16、CRC 原理和算法的总结（与WINRAR 结果一致） wxleasyland(wxlwww@) 2010 9 月2 日 比较愚钝，学了CRC 校验好几天，很痛苦的过程，现终于有眉目了，总结一下。 国外版的“轻松无痛苦学习CRC 指南”，在 /filipg/LINK/F_crc_v31.html （为什么好的资料都是老外写的？）我的英文有限，这种专业性太强的文章，很多都看不太明白，所 以没办法翻译，靠参考国内的翻译和自己瞎琢磨的。 国内的翻译比较不全，而且有点误导， 看英文的还是看英文吧，国内版资料比较零散，可参考： http://www.q.cc/2001/12/08/10190.html /content/10/0703/12/1317564shtml /data/2006/1010/article_1637.htm 我结合国内资料和英文原版进行总结，达到和WINRAR 一样的CRC32 计算结果。 一、 CRC 原理 可参考/articles/show_article.asp?Article_ID=15 计算CRC 的过程，就是用一个特殊的“除法”，来得到余数，这个余数就是CRC。 它不是真正的算术上的除法！过程和算术除法过程一样，只是加减运算变成了XOR （异或）运算！ 算术上的除法： 120÷9＝13 余 3，120 是被除数，9 是除数，13 是商，3 是余数。念作120 除以9，或者9 除120，或 者9 去除120！（除法的过程就不写了） 这个除法计算机当然会做，但是做起来很麻烦，因为减法有借位，很耗时间和指令! 所以，计算CRC 也是除法，但是用XOR 来代替减法，这就简单多了！ CRC 的除法： 120÷9＝14 余 6，商、余数和算术除法不一定相同！！因为除法用的是XOR，而不是真正的减法。 以二进制模拟这个计算过程： 1110 商为1110，即14，商有4 位，表示进行了4 次XOR ________ 1001/1111000 被除数120 是1111000，除数9 是1001 1001 ^ 1100 第一次XOR 后得到011，加入下一位0。最高位的0 可以消掉了，这样最高位是1,所以下个商是1 1001 ^ 1010 第二次XOR 后得到0101，加入下一位0。最高位的0 可以消掉了，这样最高位是1,所以下个商是1 1001 ^ 0110 第三次XOR 后得到0011，加入下一位0。最高位的0 可以消掉了，这样最高位是0,所以下个商是0 0000 ^ 110 - 最后一次XOR 后得到0110，最高位的0 可以消掉了，得到余数为110，即6 注意，余数不是0110，而是110，因为最前面那个0 已 被XOR 后消掉了！ 可见，除法（XOR）的目的是逐步消掉最高位的1或0 ！ 由于过程是XOR 的，所以商是没有意义的，我们不要。我们要的是余数。 余数110 是1111000 的CRC 吗？不是！ 余数110 是1111 （即十进制15）的CRC ！！！ 为什么？因为CRC 是和数据一起传送的，所以数据后面要加上CRC。 数据 1111 加上CRC110 后，变成 1111110，再传送。接收机收到 1111110 后，除以除数1001，余数为 000，正确；如果余数不为0，则说明传送的数据有误！这样完成CRC 校验。 即发送端要发送 1111，先在 1111 后加000，变成 1111000，再除以1001 得到余数110，这个 110 就是CRC，将110 加到数据后面，变成1111110，发送出去。 接收端收到1111110，用它除以1001，计算得余数为000，就说明收到的数据正确。 所以原始数据后面要先扩展出3 位0，以容纳CRC 值！ 会发现，在上面的除法过程中，这3 位0， 保证所有的4 个数据位在除法时都 够被处理到！不然做 一次除法就到结果了，那是不对的。这个概念后面要用到。 所以，实