当前位置： 首页 > 游戏攻略> 正文

CRC算法原理、推导及实现

来源：网络 作者：趣玩小编 发布时间：2024-08-17 10:14:45

CRC, Cyclic Redundancy Check, 循环冗余校验

1. 基本原理

CRC的本质是除法，把待检验的数据当作一个很大（很长）的被除数，两边选定一个除数（有的文献叫poly），最后得到的余数就是CRC的校验值。

判定方法：

  1. 将消息和校验和分开。计算消息的校验和（在附加W个零后），并比较两个校验和。

  2. 把校验值放到数据的结尾，对整批进行校验和（不附加零），看看结果是否为零！

1.1. 为什么用CRC

比较常见的是累加和校验，但是有以下缺点：

  1. 80 与 80 00 .. 00 的计算结果一致，即如果数据里参杂了 00 是检测不出来的，对于不定长的检测不友好

  2. 因为是累加和，所以 80 00 有非常多的组合是校验值相等的，比如 70 10 , 79 06 等等

那么什么情况下会导致CRC失败呢？

2. 推导前准备

2.1. 无进位加法及减法

CRC算术中的两个数字相加与普通二进制算术中的数字相加相同，除了没有进位。

无进位的加法及减法其实是异或运算（异或，不一样就或在一起：不一样为1，相同为0）

这意味着每对对应的比特确定对应的输出比特，而不参考任何其他比特位置。例如 

    10011011
   +11001010
    --------
    01010001
    --------

加法的4中情况： 

    0+0=0
    0+1=1
    1+0=1
    1+1=0  (no carry)

减法也是类似的： 

    10011011
   -11001010
    --------
    01010001
    --------

with 

    0-0=0
    0-1=1  (wraparound)
    1-0=1
    1-1=0

这么一来，我们相当于把加法和减法合并成为了一种算法，或者可以理解为加法和减法这里称为了一种互逆运算，比如我们可以通过加减相同的数量，可以从1010到1001： 

    1001 = 1010 + 0011
    1001 = 1010 - 0011

所以在无进位的加减法里，1010不再可以被视为大于1001；

这么做有什么好处？

你会发现无论多长的数据bit在运算时都不再依赖于前一位或者后一位的状态，这和带进位的加法及带借位的减法不同，你可以理解为运行并行计算：

  1. 带进位的加法，高位的计算结果需要累加低位结果产生的进位，这就导致了必须要先计算低位，之后才能计算高位；比如下面的例子，如果带进位的话就必须从最右边开始计算，依次算到最左边得到结果。但是如果我们把进位取消，就会发现我从那边开始算都可以，当然也可以多位同时一起算（并行计算） 

              1011                         1011
        + 1101                       + 1101
          ----                         ----        
        1 1000 (with carry)            0110 (no carry)

  2. 减法也是如此，不再赘述。

2.2. 无进位乘法

定义了加法后，我们可以进行乘法和除法。乘法是简单的，只不过在加法运算的时候使用XOR就行了 

    1101
  x 1011
    ----
    1101
   1101.
  0000..
 1101...
 -------
 1111111  Note: The sum uses CRC addition
 -------

2.3. 无进位除法

除法也是类似的，只不过有两点需要注意：

  1. 当除数和被除数的最高位都是1的时候，就当作是 对齐 了，就可以开始XOR运算，不要比较数据大小，比如 1001 可以被 1011 除，至于商的结果是1或者0，没有人去关注，自己开心就好，因为这个算法压根就不用；

  2. 被除数和除数做减法时，需要使用无进位的减法，即XOR运算； 

               1 = 商 (nobody cares about the quotient)
       ______
 1011 ) 1001 除数
 =Poly  1011
        ----
        0010

3. 算法推导

即使我们知道CRC的算法是基于除法，我们也不能直接使用除法运算，一个是待校验的数据很长，我们没有这么大的寄存器；再则，你知道除法在MCU中是怎么实现的吗？

3.1. 仿人算方法

现在我们假设一个消息数据为 1101011011 ，选取除数为 10011 ，使用CRC算法将消息除以poly： 

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
 =Poly  10011,,.,,..|.
        -----,,.,,|...
         10011,.,,|.|.
         10011,.,,|...
         -----,.,,|.|.
              10110...
              10011.|.
              -----...
               010100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

除数poly的左边的高位的作用其实是给人看的（实际上参与运算的是0011），目的是干掉当前最高位的被除数，本质上是让poly和被除数 对齐 ，然后开始XOR运算。

那么什么情况算是 对齐 呢？ 从例子上看，当被除数和除数的最高位都是1时，就算是对齐了。

转换成算法的思路就是，你也可以理解成一长串的数据不断的从右边移位到寄存器中，当寄存器最左边溢出的数值是1的时候，那么当前寄存器的数据就可以和poly异或运算了，用算法表示，大概是这样： 

                  3   2   1   0   Bits
                +---+---+---+---+
       Pop! <-- |   |   |   |   | <----- Augmented message
                +---+---+---+---+

             1    0   0   1   1   = The Poly

用算法语言描述就是： 

寄存器清零
数据最右边补齐W位0 // W是CRC校验值的位数
when(还有数据){
    左移寄存器1位，读取数据的下一位到寄存器的bit 0
    if (左移寄存器时出现溢出){
        寄存器 ^= poly;    // 这里的poly=0011，按照上面的例子
    }
}
寄存器的值就是校验值了

用C语言： 

// CRC8生成多项式
#define POLYNOMIAL 0x07

// 计算CRC8校验值
uint8_t crc8_data(const uint8_t dat8) {
    uint8_t crc = dat8;
    for (j = 8; j; j--) {
        if (crc & 0x80)
            crc = (crc << 1) ^ POLYNOMIAL;
        else
            crc <<= 1;
    }
    return crc;
}

但是这个方法太笨了，按位进行计算，效率有待提升。

3.2. 使用Table驱动计算CRC4

3.2.1. 4-bit 数据计算

为了方便描述，我们举例 W=4 且 poly=3 的情况，比如我们计算一个 3 的CRC值为 5 ，我们写成XOR的计算过程： 

0011 0000    // 补W=4个零 (值1)
,,10 011     // poly对齐  (值2)
---------
0001 0110    
,,,1 0011    // poly对齐  (值3)
---------
0000 0101    // CRC值     (值4)

上面的计算经过了N次迭代运算(其实多少次迭代我们并不关心)，等价于 

CRC值 = 值1 ^ 值2  ^ 值3
      = 值1 ^ (值2  ^ 值3)
      = 值1 ^ 查表值            // 令 `查表值` = 值2 ^ 值3

需要注意的是，在CRC计算时，末尾补了4个0，但是我们是清楚的，任何数和0的XOR运算都是其本身，所以补0不会影响最后CRC的值，只不过相当于把CRC的值提取出来。 CRC计算等价于一系列的移位和XOR运算，所以上面的表达式实际上为： 

CRC值 = (值1 ^ 0) ^ 值2  ^ 值3
      = (值1 ^ 0) ^ (值2  ^ 值3)
      = (值1 ^ 0) ^ 查表值      
      = 值1 ^ 查表值            // 令 `查表值` = 值2 ^ 值3

也就是说，我们可以实现把 0~15 的CRC的值先预先算一遍，然后存起来，这样下次再计算就可以直接查表计算，这很好理解。

3.2.2. 8-bit 数据计算

想象一下，一个8-bit的字节是可以拆分成两个4-bit数据的，如果我们可以利用查表的方法，是不是通过两次计算就可以得到一个8-bit的CRC值了？具体要怎么做呢，我们举例 W=4 且 poly=3 的情况，比如我们计算一个 33h 的CRC值，我们写成XOR的计算过程： 

0011 0011 0000    // 补W=4个零 (值1)
,,10 011          // poly对齐  (值2)
--------------
0001 0101 0000   
,,,1 0011         // poly对齐  (值3)
--------------
0000 0110 0000    // 变回4-bit CRC计算    (值4)

下面的计算我们就熟悉了，回到 计算4-bit数据为 6 的CRC值： 

0110 0000    // 补W=4个零
,100 11      // poly对齐
---------
0010 1100    
,,10 011     // poly对齐  
---------
0000 1010    // CRC值

我们发现一个有意思的事情，原来4-bit数据 3 的CRC值是 5 ，但是当 33h 先进行计算高4-bit的CRC值却是 6 ，和之前的不一样（也幸亏不一样，如果后面无论跟什么数据都一样还有校验干嘛用），这是什么原因？

首先，我们看一下8-bit计算和原来4-bit计算的区别在于末尾补数：

  • 4-bit CRC计算时，末尾补的是0，是不影响计算结果的；

  • 8-bit CRC计算时，末尾补的是后面跟的低4-bit数据，是会影响原来计算结果的：

    为了方便描述，我们把8-bit的 值1 的高4-bit数据记为H4，低4-bit数据记为L4 

    `值4` = `值1` ^ 值2 ^ 值3
    = `值1` ^ `查表值`                // 令 `查表值` = 值2 ^ 值3
    = `(H4<<4 ^ L4)` ^ `查表值`    
    = `(H4<<4)` ^ `查表值` ^ L4       // (H4<<4)其实就是计算H4的CRC值且末尾补0的情况

所以，我们可以得2段4-bit的计算流程：

  1. 去掉字节的高4-bit值为H4
  2. 将H4值进行查表计算，得到值TMP1
  3. 把TMP1的值 异或上 低4位的值L4，得到值TMP2
  4. 然后用TMP2的值进行查表计算，得到值CRC

4. 算法改进

4.1. CRC8计算

现在我们可以根据CRC4的计算过程类比到CRC8计算，其实主要的区别就是寄存器的位数从4位提升到了8位，一个典型的CRC8计算模型如下，现在你应该可以读懂了。 

#include <stdio.h>
#include <stdint.h>

// CRC8生成多项式
#define POLYNOMIAL 0x07

// 初始化CRC8查找表
void init_crc8_table(void) {
    uint8_t i, j;
    for (i = 0; i < 256; i++) {
        uint8_t crc = i;
        for (j = 8; j; j--) {
            if (crc & 0x80)
               crc = (crc << 1) ^ POLYNOMIAL;
            else
               crc <<= 1;
        }
        crc8_table[i] = crc;
    }
}

// 计算CRC8校验值
uint8_t crc8(const void *data, size_t len) {
    const uint8_t *byte = data;
    uint8_t crc = 0x00;

    for (; len > 0; len--) {
        crc = crc8_table[(crc ^ *byte++) & 0xFF];
    }

    return crc;
}

int main(int argc, ｃｈａｒ *argv[]) {
    int fd;
    uint8_t buffer;
    size_t bytes_read;
    uint8_t crc;

    if (argc != 2) {
        fprintf(stderr, "Usage: %s filename\n", argv);
        exit(1);
    }

    fd = open(argv, O_RDONLY);
    bytes_read = read(fd, buffer, sizeof(buffer));
    crc = crc8(buffer, bytes_read);
    printf("CRC: 0x%02X\n", crc);<q refer="1"></q><span class="_q_s_"></span>

    close(fd);
    return 0;
}

4.2. CRC8计算-改进型

上面的算法还是不够好，因为Table的表太大了占用256字节，对于FLASH空间紧张的MCU来说不怎么友好，能不能把一个8-bit数据拆分成两次4-bit数据的计算，这样是不是就可以搞成 16 字节的表了？我们来试一下！

实际上使用了32字节

idx L4 H4 H4说明
0 0 0 (L4<<4) ^ 07*0
1 07 70 (L4<<4) ^ 07*0
2 0E E0 (L4<<4) ^ 07*0
3 09 90 (L4<<4) ^ 07*0
4 1C C7 (L4<<4) ^ 07
5 1B B7 (L4<<4) ^ 07
6 12 27 (L4<<4) ^ 07
7 15 57 (L4<<4) ^ 07
8 38 89 (L4<<4) ^ ((07<<1) ^ 07)
9 3F F9 (L4<<4) ^ ((07<<1) ^ 07)
A 36 69 (L4<<4) ^ ((07<<1) ^ 07)
B 31 19 (L4<<4) ^ ((07<<1) ^ 07)
C 24 4E (L4<<4) ^ (07<<1)
D 23 3E (L4<<4) ^ (07<<1)
E 2A AE (L4<<4) ^ (07<<1)
F 2D DE (L4<<4) ^ (07<<1) 
// 计算CRC8校验值
uint8_t crc8(const void *data, size_t len) {
    const uint8_t *byte = data;
    uint8_t crc = 0x00;

    for (; len > 0; len--) {
        crc = crc8_table_h4[(crc ^ *byte)>>4] ^ 
              crc8_table_l4[(crc ^ *byte) & 0xF] ; 
              
              byte++;
    }

    return crc;
}

验证：

  1. CRC8计算单字节 

    crc8(88) = 38 ^ 89 = B1

  2. CRC8计算多字节 

    crc8(8888) = crc8(B1 ^ 88) = crc8(39) = 90^3F=AF
crc8(1234) = crc8(crc8(12) ^ 34) = crc8(7E ^ 34 = 4A) = C7^36=F1

4.3. CRC16计算-改进型

进一步地，我们可不可以使用相同的原理实现CRC16算法？ W=16, poly=8005

idx X[3:0] X[7:4] X[7:4]说明 X[11:8] X[11:8]说明 X[15:12] X[15:12]说明
0 0 0
1 8005 8063 X[3:0]<<4 ^ 8033 8603 X[3:0]<<8 ^ 8303 E003 X[3:0]<<12 ^ B003
2 800F 80C3 X[3:0]<<4 ^ 8033 8C03 X[3:0]<<8 ^ 8303 4003 X[3:0]<<12 ^ B003
3 0A 00A0 X[3:0]<<4 A00 X[3:0]<<8 A000 X[3:0]<<12
4 801B 8183 X[3:0]<<4 ^ 8033 9803 X[3:0]<<8 ^ 8303 8006 X[3:0]<<12 ^ B003 ^ 8005
5 1E 1E0 X[3:0]<<4 1E00 X[3:0]<<8 6005 X[3:0]<<12 ^ 8005
6 14 140 X[3:0]<<4 1400 X[3:0]<<8 C005 X[3:0]<<12 ^ 8005
7 8011 8123 X[3:0]<<4 ^ 8033 9203 X[3:0]<<8 ^ 8303 2006 X[3:0]<<12 ^ B003 ^ 8005
8 8033 8303 X[3:0]<<4 ^ 8033 B003 X[3:0]<<8 ^ 8303 8009 X[3:0]<<12 ^ B003 ^ A
9 36 360 X[3:0]<<4 3600 X[3:0]<<8 600A X[3:0]<<12 ^ A
A 3C 3C0 X[3:0]<<4 3C00 X[3:0]<<8 C00A X[3:0]<<12 ^ A
B 8039 83A3 X[3:0]<<4 ^ 8033 BA03 X[3:0]<<8 ^ 8303 2009 X[3:0]<<12 ^ B003 ^ A
C 28 280 X[3:0]<<4 2800 X[3:0]<<8 000F X[3:0]<<12 ^ 800F
D 802D 82E3 X[3:0]<<4 ^ 8033 AE03 X[3:0]<<8 ^ 8303 E00C X[3:0]<<12 ^ B003 ^ 800F
E 8027 8243 X[3:0]<<4 ^ 8033 A403 X[3:0]<<8 ^ 8303 400C X[3:0]<<12 ^ B003 ^ 800F
F 22 220 X[3:0]<<4 2200 X[3:0]<<8 A00F X[3:0]<<12 ^ 800F

验证：

  1. CRC16计算双字节

    比如计算 ABCD 的CRC16： 

    crc16(A000) = C00A
crc16(0B00) = BA03
crc16(00C0) = 0280
crc16(000D) = 802D
故crc16(ABCD) = C00A ^ BA03 ^ 0280 ^ 802D = F8A4

  2. CRC16计算四字节

    如果数据是连贯的呢，比如 ABCD 

      crc(ABCD) = F8A4
  
  crc(ABCD1234) 
= crc(F8A4 ^ 1234) = crc(EA90) = 400C ^ 3C00 ^ 360 ^ 0 = 7F6C
标签： CRC算法原理、推导及实现
相关攻略 更多 +
玩家最喜欢 更多 +
热门攻略 更多 +
热搜
查看完整榜单

本站所有软件信息来自互联网，版权归原著所有。如有侵权，敬请来信告知，我们将及时撤销！

Copyright ©2023 All rights reserved. 版权所有 趣玩手游网

蜀ICP备15000856号