|
一：说明 论坛上关于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 +----+----+----+----+ | +----+----+----+----+ | +----+----+----+----+ | +----+----+----+----+ | +----+----+----+----+ | +----+----+----+----+ +-----> +----+----+----+----+ +----+----+----+----+ +----+----+----+----+ +----+----+----+----+ < |