CRC32算法学习笔记以及如何用java实现

核心提示：一：说明论坛上关于CRC32校验算法的具体介绍不多，前几天偶然看到Ross N. Williams的文章，CRC32算法学习笔记以及如何用java实现，总算把CRC32算法的来龙去脉搞清楚了，本来想把原文翻译出来，3 2 1 0 Bits+---+---+---+---+Pop <-- <- Au

　　一：说明
　　论坛上关于CRC32校验算法的具体介绍不多。前几天偶然看到Ross N. Williams的文章，总算把CRC32算法的来龙去脉搞清楚了。本来想把原文翻译出来，但是时间参促，只好把自己的一些学习心得写出。这样大家可以更快的了解CRC32的主要思想。由于水平有限，还恳请大家指正。原文可以访问：http://www.repairfaq.org/filipg/LINK/F_crc_v31.Html 。
　　
　　二：基本概念及相关介绍
　　2．1 什么是CRC
　　
　　在远距离数据通信中，为确保高效而无差错地传送数据，必须对数据进行校验即差错控制。循环冗余校验CRC(Cyclic Redundancy Check/Code)是对一个传送数据块进行校验，是一种高效的差错控制方法。
　　
　　CRC校验采用多项式编码方法。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模，加减时不进，错位，如同逻辑异或运算。
　　
　　2．2 CRC的运算规则
　　
　　CRC加法运算规则：0+0=0
　　
　　0+1=1
　　
　　1+0=1
　　
　　1+1=0 (注重：没有进位)
　　
　　CRC减法运算规则：
　　
　　0-0=0
　　
　　0-1=1
　　
　　1-0=1
　　
　　1-1=0
　　
　　CRC乘法运算规则：
　　
　　0*0=0
　　
　　0*1=0
　　
　　1*0=0
　　
　　1*1=1
　　
　　CRC除法运算规则：
　　
　　1100001010 (注重:我们并不关心商是多少。)
　　_______________
　　
　　10011 ) 11010110110000
　　
　　10011,,.,,....
　　
　　-----,,.,,....
　　
　　10011,.,,....
　　
　　10011,.,,....
　　
　　-----,.,,....
　　
　　00001.,,....
　　
　　00000.,,....
　　
　　-----.,,....
　　
　　00010,,....
　　
　　00000,,....
　　
　　-----,,....
　　
　　00101,....
　　
　　00000,....
　　
　　-----,....
　　
　　01011....
　　
　　00000....
　　
　　-----....
　　
　　10110...
　　
　　10011...
　　
　　-----...
　　
　　01010..
　　
　　00000..
　　
　　-----..
　　
　　10100.
　　
　　10011.
　　
　　-----.
　　
　　01110
　　
　　00000
　　
　　-----
　　
　　1110 = 余数
　　
　　2．3 如何生成CRC校验码
　　
　　(1) 设G(X)为W阶，在数据块末尾添加W个0，使数据块为M+ W位，则相应的多项式为XrM(X)；
　　
　　　　(2) 以2为模，用对应于G(X)的位串去除对应于XrM(X)的位串，求得余数位串；
　　
　　　　(3) 以2为模，从对应于XrM(X)的位串中减去余数位串，结果就是为数据块生成的带足够校验信息的CRC校验码位串。
　　
　　2．4 可能我们会问那如何选择G(x)
　　
　　可以说选择G(x)不是一件很轻易的事。一般我们都使用已经被大量的数据，时间检验过的，正确的，高效的，生成多项式。一般有以下这些：
　　
　　16 bits: (16,12,5,0) [X25 standard]
　　
　　(16,15,2,0) ["CRC-16"]
　　
　　32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
　　
　　三: 如何用软件实现CRC算法
　　现在我们主要问题就是如何实现CRC校验，编码和解码。用硬件实现目前是不可能的，我们主要考虑用软件实现的方法。
　　
　　以下是对作者的原文的翻译：
　　
　　我们假设有一个4 bits的寄存器，通过反复的移位和进行CRC的除法，最终该寄存器中的值就是我们所要求的余数。
　　
　　3 2 1 0 Bits
　　
　　+---+---+---+---+
　　
　　Pop <-- <----- Augmented message（已加0扩张的原始数据）
　　
　　+---+---+---+---+
　　
　　1 0 1 1 1 = The Poly
　　
　　(注重: The augmented message is the message followed by W zero bits.)
　　
　　依据这个模型，我们得到了一个最最简单的算法：
　　
　　把register中的值置0.
　　
　　把原始的数据后添加r个0.
　　
　　While (还有剩余没有处理的数据)
　　
　　Begin
　　
　　把register中的值左移一位，读入一个新的数据并置于register的0 bit的位置。