CRC算法原理

昵称7324690 2014-05-16

展开全文

经过两天的学习，理解了CRC的原理及实现方法，记录于此备日后使用。(本文所有的运算，位数等讨论均是基于二进制的)

CRC是Cyclic Redundancy Check的缩写，其中文翻译是循环冗余校验，该算法在通信及数字存储领域被广泛使用。以下引用维基百科中对CRC的定义：CRC为校验和的一种，是两个字节数据流采用二进制除法（没有进位，使用异或来代替减法）相除所得到的余数。其中被除数是需要计算校验和的信息数据流的二进制表示；除数是一个长度为n + 1的预定义（短）的二进制数，通常用多项式的系数来表示。在做除法之前，要在信息数据之后先加上n个0.

用通俗的话讲CRC的校验过程就是将待校验的数据也就是我们需要存储或者发送的信息看做一个有限长的二进制数A，然后选择一个除数B，通过定义的一种CRC除法运算求得A/B的余数，这个余数也就是我们需要求的CRC校验和。在进一步了解CRC算法之前我们需要知道三个CRC的基本概念。

1.CRC的位宽

根据余数的二进制位数不同我们又将CRC算法用CRC-N来表示，N就表示算法的余数位数，这个位数就是CRC算法的位宽。目前被广泛应用余数位数N有16和32两种。

2.除数的选择

CRC位宽确定之后，我们就需要确定除数了。由原来已有的数学知识我们就已经知道余数和除数存在一定的关系——余数要小于除数。CRC算法的求余数过程不是我们认识的严格意义的除法运算，我们对除数和余数的关系进行如下定义：假设余数位数为N，则除数位宽应该为N+1。为什么需要这样的定义，我们可以从后文的CRC除法运算过程找到答案。(位宽的计算方式为：假设二进制序列最低位位置序号记为1，高位位置序号递增，则最高不为0位的位置序号称为该二进制序列的位宽。)

3.补零操作

CRC计算过程中为了让每一个原始信息都能够参与余数计算我们需要对原来的信息添加N个0到信息末尾。这个操作我们称之为补零操作。

4.CRC除法运算

CRC除法运算实际上就是不计进位的模2除法计算过程，逻辑上表现为位和位之间的异或运算。

下边用一个简单的例子直观的例子给出CRC的计算过程，为了方便直观我们进行一次CRC-4的求取过程，同时取原始信息为10位的二进制序列1101011011。按照之前的约定我们首先需要根据余数位宽来确定除数，余数位宽为4位，则除数必须为5位，现选用10011来作为除数，然后我们需要对原始信息进行补零操作，补零后的信息为11010110110000。CRC除法过程是这样执行的，首先看被除数最高位是否为1，如果为1则商1否则商0，商和除数的乘积称为临时乘积，计算得到临时乘积以后我们用被除数和临时乘积进行模2减法运算得到临时余数，然后将之前没有参与减法运算的被除数部分补到余数末端形成新的被除数，最后检查当前被除数位宽是否小于5，如果小于5则当前的被除数即为余数，否则按照前边的步骤进行除法运算。经过运算我们得到了商为1100001010，余数为1110,我们不关心商，只关心余数。当前得到的余数1110即为CRC-4的校验和，通常在通信或者数据传输过程中我们将该校验和附于数据末端。

1100001010——商

10011 ) 11010110110000——被除数

10011,,.,,....——临时乘积

10011,.,,....——临时余数

10011,.,,....

00001.,,....

00000.,,....

00010,,....

00000,,....

00101,....

00000,....

01011....

00000....

10110...

10011...

01010..

00000..

10100.

10011.

01110

00000

1110 = 余数

以上被除数只是一个10位的二进制序列，现实生活中通常一个数据帧或者一个数据存储块才会有一个CRC32的校验和。一个数据帧或者块多达1000个字节，8000bits，这样长的数据序列我们是没有办法用上边的那种计算方式来求取最终的CRC校验和的。对于以上CRC计算过程我们可以用另一种方式来描述：设字节型变量a,b按照以下步骤我们可以完成以上计算过程

1.将被除数高8位赋值给变量a

2.检查a的最高位是否为1,如果为1则将除数与a按照高位对齐的方式与a进行异或并将结果赋值给a

3.a左移一位，同时如果存在剩余数据则则将剩余数据最高位填充到a的最低位并转2,否则结束

以上过程就是移位计算CRC的全过程，在实际编写代码的时候，因为被除数最高位在异或以后时钟都会被移除不会对后边的运算产生影响，因此我们在编码时不必计入最高位的1。

直接移位计算CRC校验和很浪费时间，很慢，为了提高速度我们现在假设待校验的数据二进制序列为t1t2t3t4t5t6...tn,除数m1m2m3m4m5...mk，于是原CRC处罚运算过程可以这样表示：

   c1c2c3c4..cq
m1m2m3m4m5...mk)t1t2t3t4t5t6.....tn
   c1(m1m2m3m4m5m6..mk)
   c2(m1m2m3m4m5m6..mk)
   c3(m1m2m3m4m5m6..mk)
   c4(m1m2m3m4m5m6..mk)
   ..................
         cq(m1m2m3m4m5m6..mk)

以上运算过程中我们依然按照标准的CRC除法运算执行，只是在排版的时候做了变化，现解释如下：

t1..tn为待计算CRC校验和的原始数据序列

m1..mk为除数二进制序列，在CRC中称为生成多项式序列，m1必须为1.

c1..cq为商的二进制序列

除法过程全部采用模二除法

与原来的竖式计算不一样的地方是每商一位的零时余数结果没有表示出来了，我们将每一次零时乘积和之前的乘积一级原始被除数视为一个二进制序列，只是他们组成的二进制序列需要经过二进制模二加法才能得到直观的结果。观察上式我们不难发现4次模二除法的结果我们可以用下式:

t1t2t3t4t5t6.....tn

^ c1(m1m2m3m4m5m6..mk)

^ c2(0 m1m2m3m4m5m6..mk)

^ c3(0 0 m1m2m3m4m5m6..mk)

^ c4(0 0 0 m1m2m3m4m5m6..mk)

实际上就是原始数据与一些二进制序列的连续异或的结果。其中商C1,C2，Cq只和原始数据前边q位一级生成多项式有关。根据异或运算的交换定律我们可以先计算下边几行的异或，再将结果与原始数据异或结果不变。据此我们可以根据前边q位于的不同组合预先计算好q种其异或结果，并去掉高q位我们就可以直接得到最后与下一个q位异或的结果，将这个结果存为一张表，让表和q位原始数据建立一个一一对应的关系就得到了基于表驱动的快速CRC计算方法。

到此CRC原理全部介绍完毕，所有CRC计算均是基于以上方法的一些变化，这里就不再一一列举，我们只要了解原理，无论什么变化应该都能一看即明白。值得一提的是当前针对相同生成多项式CRC计算方法中的不同是寄存器初始值不同、默认位序列不同、字节序列不同等导致的，在应用中我们只需要稍加注意就可以在这些算法之间进行转换。同时目前网络上已经有很多成熟的待参数的CRC计算方法，通过配置参数可以对大部分CRC算法进行对接。

以下示例代码在keil和vs2005中运行均可得到和STM32一致的CRC32计算结果：

代码实现的条件是假定系统DWORD的存储方式是小端存储。
typedef unsigned long DWORD;
 DWORD dwPolynomial = 0x04c11db7;
 DWORD cal_crc(DWORD *ptr, int len)
 {
     DWORD    xbit;
     DWORD    data;
     DWORD    CRC = 0xFFFFFFFF;    // init
     int bits = 0;
     while (len--) {
         xbit = 1 << 31;
 
         data = *ptr++;
         for (bits = 0; bits < 32; bits++) {
             if (CRC & 0x80000000) {
                 CRC <<= 1;
                 CRC ^= dwPolynomial;
             }
             else
                 CRC <<= 1;
             if (data & xbit)
                 CRC ^= dwPolynomial;
 
             xbit >>= 1;
         }
     }
     return CRC;
 }
 
 
 int main()
 {
 DWORD data,result;
 data = 0x31;
 
 result = cal_crc(&data,1);
 result = 0;
 return 0;
 }