我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致资源-CSDN文库

CRC

5星 · 超过95%的资源需积分: 50 106 浏览量 2013-10-10 20:35:49 上传评论收藏 174KB PDF 举报

资源推荐

资源详情

资源评论

我学习 CRC32、CRC16、CRC 原理和算法的总结（与 WINRAR 结果一致）

wxleasyland(wxlwww@gmail.com)

2010 年 9 月 2 日

比较愚钝，学了 CRC 校验好几天，很痛苦的过程，现终于有眉目了，总结一下。

国外版的“轻松无痛苦学习 CRC 指南”，在

http://www.repairfaq.org/filipg/LINK/F_crc_v31.html

（为什么好的资料都是老外写的？）我的英文有限，这种专业性太强的文章，很多都看不太明白，所

以没办法翻译，靠参考国内的翻译和自己瞎琢磨的。

国内的翻译比较不全，而且有点误导，能看英文的还是看英文吧，国内版资料比较零散，可参考：

http://www.q.cc/2001/12/08/10190.html

http://www.360doc.com/content/10/0703/12/1317564_36621098.shtml

http://www.yuanma.org/data/2006/1010/article_1637.htm

我结合国内资料和英文原版进行总结，达到和 WINRAR 一样的 CRC32 计算结果。

一、 CRC 原理

可参考 http://www.luocong.com/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 个数据位在除法时都能够被处理到！不然做

一次除法就到结果了，那是不对的。这个概念后面要用到。

所以，实际上，数据是 1111，CRC 是 110。

对于除数 1001，我们叫它生成多项式，即生成项，或 POLY，即 g(x)。

数据 1111 根据 POLY1001，计算得到 CRC110。

如果 POLY 不是 1001，而是 1011，那得到的 CRC 也是不同的！

所以生成项不同，得到的 CRC 也不同。要预先定义好 POLY，发送端和接收端要用一样的 POLY！

三、直接计算法 Straightforward CRC Implementation

“直接计算法”就是直接模拟上面的除法的过程，来得到余数即 CRC！

上面的例子中，除数是 4 位，但最高位是要一直消掉的，所以我们只需要一个 3 位的寄存器就好了。

计算过程：

待测数据后扩展 W=3 个比特 0，变成 1111000；

寄存器初始化置 0；

先在寄存器中移入数据 111；

寄存器左移一位，并且右边移入下一位数据 1。这样最高位 1 移出，由于最高位是 1，故本次的商

是 1，要用除数 1001 来进行 XOR，最高位肯定 XOR 得 0，故不管它，只要用低 3 位 001 来进行 XOR 就可

以，即 001 对寄存器进行 XOR，寄存器中得到 110，即第一次 XOR 后的结果（相当于是数据 1111 与生

成项 1001 进行了一次 XOR，并把最高位 0 消掉了）。如果移出的最高位是 0，则用 0000 来进行 XOR（0

XOR 后，得到的还是原值）。

一直重复这个过程，就能得到最后余数了。

总共处理次数＝商的位数＝待测数据的位数－生成项位数＋1＋宽度 W＝待测数据的位数＝4 次。

我们假设待测数据是 1101 0110 11，生成项是 10011，假设有一个 4 bits 的寄存器，通过反复的移位

和进行 CRC 的除法，最终该寄存器中的值就是我们所要求的余数。

3 2 1 0 Bits

+---+---+---+---+

Pop <-- | | | | | <----- Augmented message（已加 0 扩张的原始数据）

+---+---+---+---+

1 0 0 1 1 = The Poly 生成项

依据这个模型，我们得到了一个最最简单的算法：

把 register 中的值置 0.

把原始的数据后添加 w 个 0.

While (还有剩余没有处理的数据)

Begin

把 register 中的值左移一位，读入一个新的数据并置于 register 最低位的位置。

If (如果上一步的左移操作中的移出的一位是 1)

End

实际上就是模拟 XOR 除法的过程，即被测数据一位一位放到寄存器中来做除法。

比如生成项是 10011，则生成的余数是 4 位 XXXX，所以寄存器是 4 位。

待测数据是 1101 0110 11，后面加上 0000，即扩张 4 位，以容纳余数。

只要与生成项的 0011 做 XOR 就好了，最高位经过 XOR 肯定出 0，可不用最高位。

过程如下：

待测数据先移 4 位即 1101 到寄存器中，准备开始除法。

第 1 次除法：寄存器中是 1101，先从寄存器移出最高位 1，移进下一位待测数据位 0，则寄存器中是

1010，由于移出的位是 1，则需要与生成项的 0011 做 XOR，得到 1001，即做了第 1 次除法后，寄存器中是

1001，这个就是余数。

第 2 次除法：寄存器中是 1001，从寄存器移出最高位 1，移进下一位待测数据位 1，则寄存器中是 0011，

由于移出的位是 1，则需要与生成项的 0011 做 XOR，得到 0000，即做了第 2 次除法后，寄存器中是 0000，

这个就是余数。

第 3 次除法：寄存器中是 0000，从寄存器移出最高位 0，移进下一位待测数据位 1，则寄存器中是 0001，

由于移出的位是 0，则需要不做 XOR，直接下一步移位。也可以等同于：本次的商是 0,0*生成项＝0，即是

0000 与寄存器做 XOR，得到寄存器的数不变，还是 0001，即做了第 3 次除法后，寄存器中是 0001，这个就

是余数。

第 4 次除法：寄存器中是 0001，从寄存器移出最高位 0，移进下一位待测数据位 0，则寄存器中是 0010，

由于移出的位是 0，则需要不做 XOR，直接下一步移位。

第 5 次除法：移位，不用做 XOR，得到寄存器中是 0101

第 6 次除法：移位，不用做 XOR，得到寄存器中是 1011

第 7 次除法：移位，移出的位是 1，又要与生成项做 XOR 了

一直做下去。。。。。。直到最后，寄存器中的就是整个计算后的余数了。即 CRC 值。

注意：

这个算法，计算出的 CRC32 值,与 WINRAR 计算出来的不一样，为什么？算法是正确的，不用怀疑！只

是 CRC32 正式算法还涉及到数据颠倒和初始化预置值等，后述。

程序实现：

程序 1：

（注：网上下的程序是有错的，我有修改了，这里是正确的）

//网上的程序经修改

BYTE POLY=0x13; //生成项，13H＝10011，这样 CRC 是 4 比特

unsigned short data = 0x035B; //待测数据是 35BH，12 比特，注意，数据不是 16 比特

unsigned short regi = 0x0000; // load the register with zero bits

// augment the data by appending W(4) zero bits to the end of it.

//按 CRC计算的定义，待测数据后加入 4个比特 0，以容纳 4 比特的 CRC；

剩余30页未读，继续阅读

评论收藏

内容反馈

jixiaoxiang001

2015-08-26

算法原理将的比较细，仔细看可以看懂，可以用，对于模2除法能在详细些的话，理解起来会快很多

happylch21

粉丝: 3
资源: 9

我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致

我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致).pdf

CRC原理-我学习CRC32、CRC16、CRC 原理和算法的总结（与WINRAR 结果一致）.pdf

CRC32、CRC16、CRC原理和算法的总结

CRC8/CRC16/CRC32最全总结（源码和生成器）

CRC8/CRC16/CRC32常见几个标准的算法及C语言实现

CRC算法简介，MODBUS的CRC16算法，CDT规约CRC8

CRC校验工具(CRC8,CRC16,CRC32)

各种CRC生成工具，包括CRC8,CRC16,CRC-CCITT,CRC32

常用数据校验源代码（CRC8 CRC16 和校验 异或校验）

CRC8 CRC16

CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致

【很好】我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致).pdf

我学习CRC32、CRC16、CRC原理和算法的总结&#40;与WINRAR结.doc

CRC算法验证工具V3.0. 用于计算或验证CRC8 CRC16 CRC32 结果

手把手教你学会计算理解crc32

CRC算法及工作原理

查看文件的MD5码、SHA1码、CRC32码.zip

WINRAR5.0正式注册版

用fpga实现crc-32校验

CRC校验源码，包括CRC8和CRC16两种，采用查表法

CRC32计算DELPHI汇编优化版

Delphi CRC32-Static静态加密实例

VBS中解决带空格路径的三种方法

WinRAR(64位)破解版v5.00 烈火简体中文版

winrar3.7 Beta8

WinRAR_4.0.exe

给windows添加文件校验功能Hashtab v6.0汉化版.rar

rar压缩软件.rar

最新资源

常用数据校验源代码（CRC8 CRC16 和校验异或校验）

我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结.doc