CRC 的简介和应用(转载)

转自做而论道的百度空间 http://hi.baidu.com/do_sermon/item/6eb87a5425d25baeacc85783

CRC,Cyclic Redundancy Check,中文称为“循环冗余校验”。

它的应用很广,一般常见的说法都是用于通信。其实,在压缩、解压文件的时候,也普遍用到了它。

另外,单片机系统在掉电时,一般都要把当前有用的状态信息,保存在 EEPROM 中,为了保证信息的正确,也可以用 CRC 来检验。

1.CRC 的作用

还是用通信来说明 CRC 的作用。

由于线路上的干扰,通信时可能会有错码,那么当接收方收到了信息,怎么来确认这些信息就是正确的呢?
为了确认通信的正确性,发送方还要在信息之后,再发送一组“校验码”,这些校验码,是用前面的信息数据算出来的。
接收方收到信息数据和校验码之后,再按照同样的算法来计算,如果结果符合规则,就认为这次数据传输是正确的。

2.CRC 的计算规则

设信息数据 M(x)有 k 位,后面的 CRC 校验码为 r 位,那么总共发送的位数则为 n = k + r 位,因此,这种编码又叫(n, k)码。

利用 k 位信息码,求取 r 位 CRC 码时,需要先确定一个“生成多项式 G(x)”。

G(x) 也是一个二进制数,要求最高位和最低位都是 1 才行。

在不同的标准里面,G(x)的数值是不同的。常见的 G(x) 如下:

CRC-CCITT:  G(x) = X16 + X12 + X5 + 1 = 1 0001 0000 0010 0001 = 1 1021H
CRC-16:     G(x) = X16 + X15 + X2 + 1 = 1 1000 0000 0000 0101 = 1 8005H

CRC-32:     G(x) = X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1
                 = 1 0000 0100 1100 0001 0001 1101 1011 0111  = 04C1 1DB7H

选定了 G(x) 之后,就可以用信息数据 M(x) 除以 G(x),得出的余数 R(x) 就是 r 位的 CRC 码。
注意,这里使用除法是“模2除”,其实就是“异或”算法。

把 M(x) 和 r 位的 CRC 码合并在一起(即(n, k)码),再除以 G(x),得出的余数就是 0。
如果这组(n, k)码中含有错误,再除以 G(x),得出的余数就不是 0。

根据余数的状态,就可以判定传送的数据信息是否正确。

3.CRC 的算法举例

例:已知信息码为 M(x) = 1100,生成多项式 G(x) = x3 + x + 1,求 CRC 码,及(n, k)码。

解:

根据 G(x) = x3 + x + 1,可知除数为 1011;余数(CRC 码)应为 3 位二进制数。

那么,先在 M(x) 后面填写上 3 个 0,即为:1100 000,再用它“模2除” 1011。

现在填写的这些 0,将来是要用 CRC 码来填充,组成的(n, k)码的。这个步骤也可以写成:

    CRC 码 = M(x) * x3  /  G(x)

乘以 x3,就代表把 M(x) 左移 3 位,后面填上 3 个 0。 /,代表“模2除”。

计算的竖式如下图的左式:

 CRC 的简介和应用(转载)


在此得出的余数 R(x) = 010 即为 CRC 码。

那么,(n, k)码 = M(x) * x3 + R(x) = 1100 000 + 010 = 1100 010。

4.CRC 的验证

还是利用上面的例题来说明验证的方法。

当收到的代码是:1100 010,按照同样的方法求余数,竖式如上图中的右式。

余数为 0,就说明数据传输是正确的。

5.用 CRC 的检错

当有一位数是错误的,模2除的余数,就不是 0 了,可见下面的竖式:

 CRC 的简介和应用(转载)

可以看出,发生错误的位置不同,余数也不同。

使用不同的信息码 M(x) 来实验,能够看出,错误位置和余数的关系是固定的,不会因为信息码的不同而变化。

如果知道了错误的位置,是不是就可以纠错呢?不可,因为难以确定错误是不是仅仅有一位,错了更多的位,余数并不会对此有所表现。

因此,有人说利用 CRC 的方法可以纠错,这是不对的,CRC 只能用于检错,不能用于纠错。

CRC 检错的能力和生成多项式的位数有关,位数越多,检错的概率越高。

6.实用的 CRC 计算步骤

前面介绍的 CRC 算法,仅仅用于说明基本概念,实用时的计算,规模要大的多。
最常用的形式是:数据是 8 位数,CRC 校验码是 16 位数。

下面就详细描述一下从一个字节数据求出 16 位数 CRC 码的过程,从而得出编程的思路。

设 8 位的信息数据是 0x4A,G(x) 选用 CRC-CCITT,即 1 0001 0000 0010 0001 = 1 1021H,求 16 位的 CRC 竖式如下:

CRC 的简介和应用(转载)


从竖式的计算过程中可以看出以下的特点:

(1)异或运算进行了多次,是从数据的高位到低位,依次判断进行的;

(2)信息数据中,有一个 1,就进行一次异或 11021H、是 0 就移位,判断下一位;
   信息数据中,只有 3 个 1,但是有一次的异或,在信息数据的范围中,异或出来一个 1,
   对于这个 1,也要进行一次异或 11021H 的运算,所以共进行了 4 次异或;

(3)异或后保留下来的余数,实际上仅仅是用 1021H 异或的结果;

(4)16 个 0,是从左边到右边,逐个参加运算。

7.实用的 CRC 汇编程序

看懂了上述的步骤,编写程序就是轻而易举的了。下面是用 51 单片机的汇编语言编写的 CRC 程序。

    ORG  0000H
    MOV  R2, P2      ;从P2输入数据,假设是4A
    CALL CRC         ;求取CRC
    MOV  P0, R2      ;输出CRC的高8位 E9
    MOV  P1, R3      ;输出CRC的低8位 8E
    NOP
    SJMP $
;------------------------------------
CRC:
    MOV  R3, #0      ;CRC低8位
    MOV  R4, #8
C1: CLR  C

    MOV  A,  R3      ;R2R3左移一位
    RLC  A
    MOV  R3,  A
    MOV  A,  R2
    RLC  A
    MOV  R2,  A
    JNC  C_NEXT      ;移出位为0就转移
    XRL  A,  #10H     ;为1就异或1021H
    MOV  R2, A
    MOV  A,  R3
    XRL  A,  #21H
    MOV  R3, A
C_NEXT:
    DJNZ R4, C1
    RET
;------------------------------------
END

呵呵,上述程序,仅仅用了 30 字节,执行时间平均为 114 个机器周期。

8.求取 CRC 的 C 程序

用 C 语言编程就可以规模大一些,借助计算机的屏幕,可以显示更多的内容。
下面就是显示数据00~FF 的全部 CRC 代码的程序。

//===============================================
#include<stdio.h>
#include<stdlib.h>

void main(void)
{
    unsigned char i;
    unsigned int  j, crc;
//--------------------------------------下面循环求出CRC
    for(j = 0; j < 256; j++)  {         //8位数据00~FF
      crc = 0;                          //每个数据的16位的CRC
      for(i = 0x80; i != 0; i >>= 1)  { //对8位数据从高位到低位进行判断
        if((crc & 0x8000) != 0)  {
          crc <<= 1;      crc ^= 0x1021;
        }
        else  crc = crc << 1;
        if((j & i) != 0)  crc ^= 0x1021;
      }
//--------------------------------------计算完毕,下面进行显示
      if (j % 4 == 0)  printf("\n");
      if (j % 32 == 0)      system("pause");
      printf("0x%02X: 0x%04x,  ", j, crc & 0xFFFF);
    }
}
//===============================================

上述程序执行后,显示的结果如下:

0x00: 0x0000,  0x01: 0x1021,  0x02: 0x2042,  0x03: 0x3063,
0x04: 0x4084,  0x05: 0x50a5,  0x06: 0x60c6,  0x07: 0x70e7,
0x08: 0x8108,  0x09: 0x9129,  0x0A: 0xa14a,  0x0B: 0xb16b,
0x0C: 0xc18c,  0x0D: 0xd1ad,  0x0E: 0xe1ce,  0x0F: 0xf1ef,
0x10: 0x1231,  0x11: 0x0210,  0x12: 0x3273,  0x13: 0x2252,
0x14: 0x52b5,  0x15: 0x4294,  0x16: 0x72f7,  0x17: 0x62d6,
0x18: 0x9339,  0x19: 0x8318,  0x1A: 0xb37b,  0x1B: 0xa35a,
0x1C: 0xd3bd,  0x1D: 0xc39c,  0x1E: 0xf3ff,  0x1F: 0xe3de,

0x20: 0x2462,  0x21: 0x3443,  0x22: 0x0420,  0x23: 0x1401,
0x24: 0x64e6,  0x25: 0x74c7,  0x26: 0x44a4,  0x27: 0x5485,
0x28: 0xa56a,  0x29: 0xb54b,  0x2A: 0x8528,  0x2B: 0x9509,
0x2C: 0xe5ee,  0x2D: 0xf5cf,  0x2E: 0xc5ac,  0x2F: 0xd58d,
0x30: 0x3653,  0x31: 0x2672,  0x32: 0x1611,  0x33: 0x0630,
0x34: 0x76d7,  0x35: 0x66f6,  0x36: 0x5695,  0x37: 0x46b4,
0x38: 0xb75b,  0x39: 0xa77a,  0x3A: 0x9719,  0x3B: 0x8738,
0x3C: 0xf7df,  0x3D: 0xe7fe,  0x3E: 0xd79d,  0x3F: 0xc7bc,

0x40: 0x48c4,  0x41: 0x58e5,  0x42: 0x6886,  0x43: 0x78a7,
0x44: 0x0840,  0x45: 0x1861,  0x46: 0x2802,  0x47: 0x3823,
0x48: 0xc9cc,  0x49: 0xd9ed,  0x4A: 0xe98e,  0x4B: 0xf9af,
0x4C: 0x8948,  0x4D: 0x9969,  0x4E: 0xa90a,  0x4F: 0xb92b,
0x50: 0x5af5,  0x51: 0x4ad4,  0x52: 0x7ab7,  0x53: 0x6a96,
0x54: 0x1a71,  0x55: 0x0a50,  0x56: 0x3a33,  0x57: 0x2a12,
0x58: 0xdbfd,  0x59: 0xcbdc,  0x5A: 0xfbbf,  0x5B: 0xeb9e,
0x5C: 0x9b79,  0x5D: 0x8b58,  0x5E: 0xbb3b,  0x5F: 0xab1a,

0x60: 0x6ca6,  0x61: 0x7c87,  0x62: 0x4ce4,  0x63: 0x5cc5,
0x64: 0x2c22,  0x65: 0x3c03,  0x66: 0x0c60,  0x67: 0x1c41,
0x68: 0xedae,  0x69: 0xfd8f,  0x6A: 0xcdec,  0x6B: 0xddcd,
0x6C: 0xad2a,  0x6D: 0xbd0b,  0x6E: 0x8d68,  0x6F: 0x9d49,
0x70: 0x7e97,  0x71: 0x6eb6,  0x72: 0x5ed5,  0x73: 0x4ef4,
0x74: 0x3e13,  0x75: 0x2e32,  0x76: 0x1e51,  0x77: 0x0e70,
0x78: 0xff9f,  0x79: 0xefbe,  0x7A: 0xdfdd,  0x7B: 0xcffc,
0x7C: 0xbf1b,  0x7D: 0xaf3a,  0x7E: 0x9f59,  0x7F: 0x8f78,

0x80: 0x9188,  0x81: 0x81a9,  0x82: 0xb1ca,  0x83: 0xa1eb,
0x84: 0xd10c,  0x85: 0xc12d,  0x86: 0xf14e,  0x87: 0xe16f,
0x88: 0x1080,  0x89: 0x00a1,  0x8A: 0x30c2,  0x8B: 0x20e3,
0x8C: 0x5004,  0x8D: 0x4025,  0x8E: 0x7046,  0x8F: 0x6067,
0x90: 0x83b9,  0x91: 0x9398,  0x92: 0xa3fb,  0x93: 0xb3da,
0x94: 0xc33d,  0x95: 0xd31c,  0x96: 0xe37f,  0x97: 0xf35e,
0x98: 0x02b1,  0x99: 0x1290,  0x9A: 0x22f3,  0x9B: 0x32d2,
0x9C: 0x4235,  0x9D: 0x5214,  0x9E: 0x6277,  0x9F: 0x7256,

0xA0: 0xb5ea,  0xA1: 0xa5cb,  0xA2: 0x95a8,  0xA3: 0x8589,
0xA4: 0xf56e,  0xA5: 0xe54f,  0xA6: 0xd52c,  0xA7: 0xc50d,
0xA8: 0x34e2,  0xA9: 0x24c3,  0xAA: 0x14a0,  0xAB: 0x0481,
0xAC: 0x7466,  0xAD: 0x6447,  0xAE: 0x5424,  0xAF: 0x4405,
0xB0: 0xa7db,  0xB1: 0xb7fa,  0xB2: 0x8799,  0xB3: 0x97b8,
0xB4: 0xe75f,  0xB5: 0xf77e,  0xB6: 0xc71d,  0xB7: 0xd73c,
0xB8: 0x26d3,  0xB9: 0x36f2,  0xBA: 0x0691,  0xBB: 0x16b0,
0xBC: 0x6657,  0xBD: 0x7676,  0xBE: 0x4615,  0xBF: 0x5634,

0xC0: 0xd94c,  0xC1: 0xc96d,  0xC2: 0xf90e,  0xC3: 0xe92f,
0xC4: 0x99c8,  0xC5: 0x89e9,  0xC6: 0xb98a,  0xC7: 0xa9ab,
0xC8: 0x5844,  0xC9: 0x4865,  0xCA: 0x7806,  0xCB: 0x6827,
0xCC: 0x18c0,  0xCD: 0x08e1,  0xCE: 0x3882,  0xCF: 0x28a3,
0xD0: 0xcb7d,  0xD1: 0xdb5c,  0xD2: 0xeb3f,  0xD3: 0xfb1e,
0xD4: 0x8bf9,  0xD5: 0x9bd8,  0xD6: 0xabbb,  0xD7: 0xbb9a,
0xD8: 0x4a75,  0xD9: 0x5a54,  0xDA: 0x6a37,  0xDB: 0x7a16,
0xDC: 0x0af1,  0xDD: 0x1ad0,  0xDE: 0x2ab3,  0xDF: 0x3a92,

0xE0: 0xfd2e,  0xE1: 0xed0f,  0xE2: 0xdd6c,  0xE3: 0xcd4d,
0xE4: 0xbdaa,  0xE5: 0xad8b,  0xE6: 0x9de8,  0xE7: 0x8dc9,
0xE8: 0x7c26,  0xE9: 0x6c07,  0xEA: 0x5c64,  0xEB: 0x4c45,
0xEC: 0x3ca2,  0xED: 0x2c83,  0xEE: 0x1ce0,  0xEF: 0x0cc1,
0xF0: 0xef1f,  0xF1: 0xff3e,  0xF2: 0xcf5d,  0xF3: 0xdf7c,
0xF4: 0xaf9b,  0xF5: 0xbfba,  0xF6: 0x8fd9,  0xF7: 0x9ff8,
0xF8: 0x6e17,  0xF9: 0x7e36,  0xFA: 0x4e55,  0xFB: 0x5e74,
0xFC: 0x2e93,  0xFD: 0x3eb2,  0xFE: 0x0ed1,  0xFF: 0x1ef0,

Press any key to continue
//===============================================

9.求取数组的 CRC

实际的数据传输,往往是要把几十个字节的信息数据,求出一个 16 位的 CRC 码,再把它附在信息的后面进行传送。

网上可以找到这样的 C 程序,做而论道加上了一些注释,如下所示:

//===============================================
unsigned char test[16] = {
    0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77,
    0x88, 0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff};
unsigned char len = 16;
//----------------------------
unsigned int crc16l(unsigned char *ptr, unsigned char len)
{                              //ptr 为数据指针,len 为数据长度
    unsigned char i;
    unsigned int crc = 0;

    while(len--)   {           //按照数据的个数进行循环
      for(i = 0x80; i != 0; i >>= 1)   { //由高位到低位
        if((crc & 0x8000) != 0) { crc <<= 1;   crc ^= 0x1021; }
        else  crc <<= 1;
        if((*ptr & i) != 0 )  crc ^= 0x1021;//针对数据进行处理
      }
      ptr++;                   //下一个数据
    }
    return(crc);
}
//----------------------------
void main(void)
{
    printf("0x%04x", crc16l(test, len) & 0xFFFF);
}
//===============================================

程序运行后,将显示出来:0x1248,这就是数组中 16 个字节数据的 CRC 码。

10.在 51 单片机中的 CRC 应用

上述的 C 程序,也可以移植到单片机系统中,但是 C 程序的速度和占用空间就不敢恭维了。

针对同样一个字节(即0x4F)进行处理的时候,C 程序使用的时间是 263 T,大约是汇编程序的 2.5 倍 !

当然,也可以采用查表的方法,速度就可以提高几十倍,但是表格占用的空间,也是很可惜的。

所以,做而论道关于这方面的应用程序,都是用汇编语言编写的。

这种程序,虽然执行的效率较高,但是篇幅却较长。恐怕多数人都没有耐心看,所以做而论道的程序,也就不在此处公布了。

CRC 的简介和应用(转载)

上一篇:IOS开发的基础知识


下一篇:iOS5 ARC,IBOutlets 应该定义strong还是weak