一：说明
论坛上关于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的位置。
If (如果上一步的左移操作中的移出的一位是1)
register = register XOR Poly.
End
现在的register中的值就是我们要求的crc余数。
我的学习笔记：
可为什么要这样作呢？我们从下面的实例来说明：
1100001010
_______________
10011 ) 11010110110000
10011,,.,,....
-----,,.,,....
－》 10011,.,,....
10011,.,,....
-----,.,,....
－》 00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
我们知道G(x)的最高位一定是1，而商1还是商0是由被除数的最高位决定的。而我们并不关心商究竟是多少，我们关心的是余数。例如上例中的G(x)有5位。我们可以看到每一步作除法运算所得的余数其实就是被除数的最高位后的四位于G(x)的后四位XOR而得到的。那被除数的最高位有什么用呢？我们从打记号的两个不同的余数就知道原因了。当被除数的最高位是1时，商1然后把最高位以后的四位于G(x)的后四位XOR得到余数；如果最高位是0，商0然后把被除数的最高位以后的四位于G(x)的后四位XOR得到余数，而我们发现其实这个余数就是原来被除数最高位以后的四位的值。也就是说如果最高位是0就不需要作XOR的运算了。到这我们总算知道了为什么先前要这样建立模型，而算法的原理也就清楚了。
以下是对作者的原文的翻译：
可是这样实现的算法却是非常的低效。为了加快它的速度，我们使它一次能处理大于4 bit的数据。也就是我们想要实现的32 bit的CRC校验。我们还是假设有和原来一样的一个4 "bit"的register。不过它的每一位是一个8 bit的字节。
3 2 1 0 Bytes
+----+----+----+----+
Pop <-- | | | | | <----- Augmented message
+----+----+----+----+
1<------32 bits------> （暗含了一个最高位的“1”）
根据同样的原理我们可以得到如下的算法：
While (还有剩余没有处理的数据)
Begin
检查register头字节，并取得它的值
求不同偏移处多项式的和
register左移一个字节，最右处存入新读入的一个字节
把register的值和多项式的和进行XOR运算
End
我的学习笔记：
可是为什么要这样作呢？ 同样我们还是以一个简单的例子说明问题：
假设有这样的一些值：
当前register中的值： 01001101
4 bit应该被移出的值：1011
生成多项式为： 101011100
Top Register
---- --------
1011 01001101
1010 11100 + (CRC XOR)
-------------
0001 10101101
首4 bits 不为0说明没有除尽，要继续除:
0001 10101101
1 01011100 + (CRC XOR)
-------------
0000 11110001
^^^^
首4 bits 全0说明不用继续除了。
那按照算法的意思作又会有什么样的结果呢？
1010 11100
1 01011100+
-------------
1011 10111100
1011 10111100
1011 01001101+
-------------
0000 11110001
现在我们看到了这样一个事实，那就是这样作的结果和上面的结果是一致的。这也说明了算法中为什么要先把多项式的值按不同的偏移值求和，然后在和register进行异或运算的原因了。另外我们也可以看到，每一个头字节对应一个值。比如上例中：1011，对应01001101。那么对于32 bits 的CRC 头字节，依据我们的模型。头8 bit就该有 2^8个，即有256个值与它对应。于是我们可以预先建立一个表然后，编码时只要取出输入数据的头一个字节然后从表中查找对应的值即可。这样就可以大大提高编码的速度了。
+----+----+----+----+
+-----< | | | | | <----- Augmented message
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+
v +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
+-----> +----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
255+----+----+----+----+
以下是对作者的原文的翻译：
上面的算法可以进一步优化为：
1：register左移一个字节,从原始数据中读入一个新的字节.
2：利用刚从register移出的字节作为下标定位 table 中的一个32位的值
3：把这个值XOR到register中。
4：如果还有未处理的数据则回到第一步继续执行。
用C可以写成这样：
r=0;
while (len--)
r = ((r << 8) | p*++) ^ t[(r >> 24) & 0xFF];
可是这一算法是针对已经用0扩展了的原始数据而言的。所以最后还要加入这样的一个循环，把W个0加入原始数据。
我的学习笔记：
注意不是在预处理时先加入W个0，而是在上面算法描述的循环后加入这样的处理。
for (i=0; i<W/4; i++)
r = (r << 8) ^ t[(r >> 24) & 0xFF];
所以是W/4是因为若有W个0，因为我们以字节（8位）为单位的，所以是W/4个0 字节。注意不是循环w/8次
以下是对作者的原文的翻译：
1：对于尾部的w/4个0字节，事实上它们的作用只是确保所有的原始数据都已被送入register，并且被算法处理。
2：如果register中的初始值是0，那么开始的4次循环，作用只是把原始数据的头4个字节送入寄存器。（这要结合table表的生成来看）。就算register的初始值不是0，开始的4次循环也只是把原始数据的头4个字节把它们和register的一些常量XOR，然后送入register中。
3:(A xor B) xor C = A xor (B xor C)
总上所述，原来的算法可以改为:
+-----<Message (non augmented)
|
v 3 2 1 0 Bytes
| +----+----+----+----+
XOR----<| | | | |
| +----+----+----+----+
| ^
| |
| XOR
| |
| 0+----+----+----+----+
v +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
| +----+----+----+----+
+----->+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
255+----+----+----+----+
算法：
1：register左移一个字节,从原始数据中读入一个新的字节.
2：利用刚从register移出的字节和读入的新字节XOR从而产生定位下标，从table中取得相应的值。
3：把该值XOR到register中
4：如果还有未处理的数据则回到第一步继续执行。
我的学习笔记：
对这一算法我还是不太清楚，或许和XOR的性质有关，恳请大家指出为什么？
谢谢。
到这，我们对CRC32的算法原理和思想已经基本搞清了。下章，我想着重根据算法思想用java语言实现。
chensheng913@yahoo.com.cn
分享到：
相关推荐
用java 编写实现的CRC32算法，很详细
尽管Java标准库已经提供了CRC32的实现类 `java.util.zip.CRC32`，但从教学的角度出发，手动实现一个简化的CRC算法可以更好地帮助理解CRC的工作原理。下面给出一个简化的CRC-4算法的Java实现示例： ```java public ...
CRC算法的核心是使用一个预定义的多项式，将数据与这个多项式进行异或操作，然后对结果进行模2除法，得到的余数即为CRC校验码。 在Java中实现CRC算法，通常涉及以下几个关键步骤： 1. **选择CRC多项式**：CRC有...
CRC32（Cyclic Redundancy Check，循环冗余校验）是一种广泛应用于数据通信和存储领域的错误检测码，主要用于确保数据...通过分析和运行这些文件，可以深入理解CRC32的工作原理，并学习如何在实际项目中应用CRC32算法。
计算字符串或文件的Crc32代码，提供标准的API，适应各语言开发的系统中调用，且与JAVA自身(import java.util.zip.CRC32)的CRC32算法计算结果相同。 // 获取计算字符Crc32代码 // 以10进制返回Crc32代码 CRC32_API ...
在FPGA（Field-Programmable Gate Array，现场可编程门阵列）上实现CRC32校验算法，可以高效地进行实时数据校验，尤其适用于高速数据流处理。 CRC32的基本原理是通过一个预定义的多项式，对数据进行除法运算，并将...
总之，CRC32是一种重要的错误检测技术，而提供的C++代码和DEMO程序为学习和理解CRC32提供了实践基础，同时也展示了不同实现方式的性能差异。通过深入研究这些代码，开发者可以更好地掌握CRC32算法，并将其应用到自己...
JAVA下使用两种方法（计算法、查表法）实现CRC（XMODEM）算法，以及验证代码
CRC32算法的实现可以使用硬件电路，也可以用软件编程实现。在软件实现中，常见的方法有查表法和位操作法。查表法是预先计算好所有可能的CRC值，形成一个查找表，在计算时根据数据直接查表得到结果，效率较高。位操作...
crc32标准算法： 宽度：32 多项式：04C11DB7 初始值：0xFFFFFFFF 异或值：0xFFFFFFFF 输入输出数据反转； 与在线工具算出的crc32值一样，包含文件校验。
在给定的项目中，"CRC32加密算法"是使用Visual Studio开发的一个MFC（Microsoft Foundation Classes）图形用户界面应用。MFC是微软提供的一套面向对象的类库，用于简化Windows应用程序的开发，它基于C++语言。开发者...
CRC32是CRC的一种具体实现，它使用32位的校验码。 CRC的基本原理是基于多项式除法，可以将数据看作是一个二进制数，校验码则是根据选定的生成多项式计算得出的余数。在CRC32中，通常使用的是CRC-32标准，其生成...
与标准的CRC32算法相比，CRC32-MPEG可能使用不同的初始值、反射输入、反射结果以及可能的XOR校验值等步骤。 查表法是一种常见的实现CRC计算的方法，它通过预先计算出所有可能的位移结果并存储在一个查找表中，当...
为了实现这些算法，开发者通常会定义一个结构来表示CRC，包含一个表示当前CRC值的变量，以及一个静态方法来计算CRC。这两个方法会使用位操作，如异或和左移，来模拟除法和取模的过程。`CRC16.cs`和`CRC32.cs`文件很...
CRC32校验算法 C#，文件流传输校验算法
//一个适合单片机使用的CRC32算法，可分步计算 //收到一个email求助CRC32算法，从以前做过的upsd3254远程升级代码中提取一个出来，这个函数参考了在网上搜到的代码，并做了简化，以实现分步计算CRC32：
CRC16校验算法及十六进制和十六进制字符串转换
CRC32算法的基本原理是，将要校验的数据视为一个二进制多项式，然后除以一个预定义的生成多项式，得到的余数即为CRC校验码。在接收端，接收到的数据同样除以这个生成多项式，如果余数为零，则认为数据传输无误；若非...
CRC（Cyclic Redundancy Check，循环冗余校验）是一种广泛用于数据传输和存储中的错误检测技术。...在给定的代码中，我们可以学习到如何用C语言实现这些算法，并将其应用到实际项目中进行数据校验。
在Java中实现CRC16，通常会使用位操作来模拟上述步骤。以下是一个简单的CRC16计算类`CRC16`的代码框架： ```java public class CRC16 { private static final int POLYNOMIAL = 0xA001; // CRC16生成多项式 ...