搜索
一、CRC码工作原理1.CRC校验原理CRC的英文全称为CyclicRedundancyCheck（Code），中文名称为循环冗余校验（码）。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的，而CRC计算则是异或运算。任何一个除法运算都需要选取一个除数，在CRC运算中我们称之为poly，而宽度W就是poly最高位的位置。比如poly1001的W是3，而不是4。注意最高位总是1，当你选定一个宽度，那么你只需要选择低W各位的值。假如我们想计算一个位串的CRC码，并要保证每一位都要被处理，因此我们需要在目标位串后面加上W个0。CRC校验原理看起来比较复杂，因为大多数书上基本上是以二进制的多项式形式来说明的。其实很简单的问题，其根本思想就是先在要发送的帧后面附加一个数（这个就是用来校验的校验码，但要注意，这里的数也是二进制序列的，下同），生成一个新帧发送给接收端。当然，这个附加的数不是随意的，它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除（注意，这里不是直接采用二进制除法，而是采用一种称之为“模2除法”）。到达接收端后，再把接收到的新帧除以（同样采用“模2除法”）这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数，做了“去余”处理（也就已经能整除了），所以结果应该是没有余数。如果有余数，则表明该帧在传输过程中出现了差错。【说明】“模2除法”与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位；模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。相当于二进制中的逻辑异或运算。也就是比较后，两者对应位相同则结果为“0”，不同则结果为“1”。如100101除以1110，结果得到商为11，余数为1，如图5-9左图所示。如11×11=101，如图5-9右图所示。图5-9“模2除法”和“模2乘法”示例具体来说，CRC校验原理就是以下几个步骤：（1）先选择（可以随机选择，也可按标准选择，具体在后面介绍）一个用于在接收端进行校验时，对接收的帧进行除法运算的除数（是二进制比较特串，通常是以多项方式表示，所以CRC又称多项式编码方法，这个多项式也称之为“生成多项式”）。（2）看所选定的除数二进制位数（假设为k位），然后在要发送的数据帧（假设为m位）后面加上k-1位“0”，然后以这个加了k-1个“0“的新帧（一共是m+k-1位）以“模2除法”方式除以上面这个除数，所得到的余数（也是二进制的比特串）就是该帧的CRC校验码，也称之为FCS（帧校验序列）。但要注意的是，余数的位数一定要是比除数位数只能少一位，哪怕前面位是0，甚至是全为0（附带好整除时）也都不能省略。（3）再把这个校验码附加在原数据帧（就是m位的帧，注意不是在后面形成的m+k-1位的帧）后面，构建一个新帧发送到接收端，最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数，如果没有余数，则表明该帧在传输过程中没出错，否则出现了差错。通过以上介绍，大家一定可以理解CRC校验的原理，并且不再认为很复杂吧。从上面可以看出，CRC校验中有两个关键点：一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）；二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS。前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”，如在IBM的SDLC（同步数据链路控制）规程中使用的CRC-16（也就是这个除数一共是17位）生成多项式g（x）=x16+x15+x2+1（对应二进制比特串为：11000000000000101）；而在ISOHDLC（高级数据链路控制）规程、ITU的SDLC、X.25、V.34、V.41、V.42等中使用CCITT-16生成多项式g（x）=x16+x15+x5+1（对应二进制比特串为：11000000000100001）。2.CRC校验码的计算示例由以上分析可知，既然除数是随机，或者按标准选定的，所以CRC校验的关键是如何求出余数，也就是CRC校验码。下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G（X）=X4+X3+1，要求出二进制序列10110011的CRC校验码。下面是具体的计算过程：（1）首先把生成多项式转换成二进制数，由G（X）=X4+X3+1可以知道（，它一共是5位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1的位，也就是这个二进制的第4位、第3位、第0位的二进制均为1，其它位均为0）很快就可得到它的二进制比特串为11001。（2）因为生成多项式的位数为5，根据前面的介绍，得知CRC校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数，即CRC校验码为0100，如图5-10所示。注意参考前面介绍的“模2除法”运算法则。图5-10CRC校验码计算示例（3）把上步计算得到的CRC校验码0100替换原始帧101100110000后面的四个“0”，得到新帧101100110100。再把这个新帧发送到接收端。（4）当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍，大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了。下面大家做一个练习，假设CRC生成多项式为G（X）=X5+X4+X+1，要发送的二进制序列为100101110，求CRC校验码是多少。二、CRC码典型应用CRC（CyclicRedundancyCheck，直译：循环冗余校验）技术是一项很成熟的技术，在众多领域有广泛的应用，在数据存储和通信传输应用中处处都可以看到它的身影。最常用的CRC校验形式有CRC-16,CRC-32两种形式，采用CRC-16校验，可以保证在1014位码元中只含有一位未被检测出的错误，采用CRC-32校验的出错概率比CRC-16还低105倍。CRC的主要特点就是:检错能力极强，开销很小，易于实现。从性能和开销上综合考虑，其远远优于奇偶校验及算术和校验等方式。因此，很多软件在加密保护时都将CRC技术应用其中。CRC校验的原理解析在实际应用中，根据环境和需求的变化，CRC形成了多种变形方式。比如：通讯协议X.25的帧检错序列采用的是CRC-CCITT方式，ARJ、LHA、ZIP等压缩软件采用的是CRC-32方式，磁盘驱动器的读写采用的是CRC-16方式，GIF、TIFF等图像存储格式也使用CRC作为检错技术。目前，比较流行的CRC形式主要是：CRC-16（CRC-CCITT）、CRC-32两种，CRC-4、CRC-8、CRC-12等形式的应用比较少见。其实，虽然有这么多种变形方式，但其原理是完全相同的，只是在实现上有一点变化而已，下面我们就对其原理进行一番解剖，希求通透。CRC的算法本质是(模-2)除法的余数运算，使用的除数不同，CRC的类型也就不一样。CRC的算法其实是采用了多项式编码的方法，您可以将要被处理的数据块M看成一个n阶的二进制多项式，其形式如下：a是对应的阶数（位数）的值；x是对应的“模（进制）”数，由于我们处理的都是二进制数，所以x就是2了。下面我们用一个数进行解释吧：有一个二进制数M=10010101，其对应的多项式就可以表示为：CRC校验就是基于这种多项式进行的运算，其乘除法运算过程与普通代数多项式的乘除法相同，其加减法运算以2为模，加减时不进（借）位，实际上与逻辑异或（XOR）运算是一致的。通常，根据多项表达（运算）式的不同，就形成了不同的CRC形式，以下是各种常用的多项表达（运算）式：这些多项表达式的值就是(模-2)除法的除数，只要能确定使用哪一种多项式（也就是对应除数），您就可以很简单的获取CRC检验码了。下面就给您介绍CRC检验码的计算过程：1、先确定您要使用的CRC校验形式，以此确定对应除数（用G来表示）和选定阶数（用r来表示）。（如果选择CRC-4的话，r就等于4，选择CRC-16话，r就等于16，以此类推。）2、在待处理的数据块M'后附加上r个0。假设原始数据块的长度是m位的话，附加之后的长度就变成m+r位了，我们用M来代表附加后的值。3、用第一步选择的生成多项式的值（即对应除数G）来除第二步附加0后生成的值（M），循环计算，一直到余数的阶数小于等于r-1，这时所得到的余数（用Y表示）就是原始数据M'经过所选择的CRC校验形式所生成的CRC校验码。如果您想将生成的校验码与原始数据进行复合，只需要用第二步生成的（M）以模2的方法减去得到的CRC校验码（Y），所得到的值就是包含了CRC校验码的数据串M''。（不过在软件加密过程中可能用不到这一步）。只需要三步，就可以得到CRC的校验码。举个例子：设原始数据M'＝1100110100选择CRC-4的形式，则G＝24＋2＋1＝19＝10011（二进制）r＝G的二进制位数减1＝5-1＝4对原始数据M'进行处理，在其尾部附加r个0，即:M=M'+0000=11001101000000再用G循环除M：其实校验码生成的过程就是一个循环移位的运算，位与位之间就是异或（XOR）运算。一个数据的校验过程是这样的，如果有大量数据（比如说一个可执行程序或一个压缩包）将如何进行校验呢？其实很简单，只要将一个文件看成一个被一些数字分割的很长的位字串就可以了，只是这个位字串比较TA而已，你只要按标准的方式对这个比较长的位字串进行(模-2)除法运算，就一定会得到一个余数---CRC校验码，而这个校验码就是这个文件的CRC校验值。CRC校验的代码实现好了，理论上的准备是很多了，现在要用进入实践了。下面，我们将给您提供一段很简单而实用的代码，用来实现CRC-32校验，最终，我会用这段代码实现软件加密保护。大家可以看到，上面生成CRC校验码的过程中，使用了大量的位运算和逻辑操作。而我想告诉大家的是，基于位运算的算法是非常慢的而且效率很低。因此，在实际使用中不推荐使用“计算法”来生成CRC校验码，而建议使用“查表法”来进行CRC校验码计算。查表法又是什么方法呢？这里我不做过多的分析，简单的说，它是利用预先计算出的标准码表（对应不同的校验形式有不同的码表，见附表1、2），用简单的移位和XOR操作，快速计算出CRC校验码的方法。具体的算法就是：（1）将上次计算出的CRC校验码右移一个字节；（2）将移出的这个字节与新的要校验的字节进行XOR运算；（3）用运算出的值在预先生成码表中进行索引，获取对应的值（称为余式）；（4）用获取的值与第（1）步右移后的值进行XOR运算；（5）如果要校验的数据已经处理完，则第（4）步的结果就是最终的CRC校验码。如果还有数据要进行处理，则再转到第（1）步运行。看上面的过程是十分简单的，不好理解的可能是“预先生成的码表”。其实这个码表就是2^8的数组，为什么是8次方呢？因为我们是用字节来进行运算的，而一个字节是8位，所以就是2的8次方了。因此这个码表就是拥有256值的数组，对应的每个值实际上就是0-255以对应的CRC多项表达式（见原理分析）为权的CRC码。如CRC-16的多项表达式就是，CRC-32的多项表达式就是：附表1、2中分别给出了对应两种形式的码表（汇编格式），您只要复制到您的代码中即可使用（可能要做一些修饰）。如果您不想将这么一大堆码表复制到您的代码中，也可以使用动态生成码表（不过是给256个数字进行CRC计算而已）。下面是生成CRC-32码表的代码（c语言）：//------------