首页 > 编程语言 >CRC算法原理、推导及实现

CRC算法原理、推导及实现

时间:2024-08-16 16:53:53浏览次数:14  
标签:推导 crc L4 poly CRC 算法 计算 bit


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

1. 基本原理

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

判定方法:

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

  2. 把校验值放到数据的结尾,对整批进行校验和(不附加零),看看结果是否为零!

1.1. 为什么用CRC

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

  1. 8080 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=4poly=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=4poly=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, char *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,L4,poly,CRC,算法,计算,bit
From: https://www.cnblogs.com/qiyuexin/p/18363214

相关文章

  • 加密算法
    加密算法概述加密算法是保护信息安全的重要工具,广泛应用于数据传输、存储和身份验证等领域。根据不同的目的和特性,加密算法可以分为几类。一、对称加密算法对称加密算法是指加密和解密使用相同的密钥。其优点是速度快,适合大数据量的加密,但密钥管理是一个挑战。1.DES(数据加密......
  • 算法模板
    拓扑排序点击查看代码publicBooleanbfsOptimize(intn,int[][]edges){//初始化入度数组,每个节点有两个元素,第一个元素表示入度,第二个元素暂时未使用int[][]indegrees=newint[n][2];//初始化邻接表,用于存储图的连接关系List<List<Integer>>adj......
  • 基于协同过滤推荐算法+springboot+vue的篮球球队网站
    博主主页:猫头鹰源码博主简介:Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万+、专注Java技术领域和毕业设计项目实战,欢迎高校老师\讲师\同行交流合作​主要内容:毕业设计(Javaweb项目|小程序|Python|HTML|数据可视化|SSM|SpringBoot|Vue|Jsp|PHP......
  • 掌握一致性哈希算法
    如何分配请求?大多数网站背后肯定不是只有一台服务器提供服务,因为单机的并发量和数据量都是有限的,所以都会用多台服务器构成集群来对外提供服务。但是问题来了,现在有那么多个节点(后面统称服务器为节点,因为少一个字),要如何分配客户端的请求呢?其实这个问题就是「负载均衡问......
  • C/C++算法概述
    摘要1.性能优势:C/C++语言以其接近硬件的特性而著称,提供了对底层硬件的直接控制能力。这意味着算法可以实现更高的执行效率,特别是在需要处理大量数据或实时性能要求较高的场景中。2.灵活性:C/C++提供了丰富的数据结构和操作,允许开发者以灵活的方式实现复杂的算法。同时,C++的......
  • 红温刷算法题(C/C++)
    此文章主要是给刷算法题的小萌新写的题解,博主每日刷题,把所刷的题以及所获都会发到博客里面,文章有详解思路,并且有对应的AC代码,希望我的博客对算法小萌新有所帮助。感谢CSDN平台给我这个机会,我会努力创作,创作高质量文章。 P1002[NOIP2002普及组]过河卒题目描述棋盘上 A ......
  • 《机器学习》 KNN算法、数据可视化 No.1
    一、了解机器学习1、什么是机器学习        机器学习是一种人工智能(AI)的分支,旨在让计算机通过数据自动学习和改进。机器学习算法被设计用于从数据中提取模式和规律,然后利用这些模式和规律来做出预测或做出决策,而无需明确的程序指令。        机器学习的基本......
  • 看demo学算法之 循环神经网络(RNN)
    今天我们来聊聊神经网络中的“记忆大师”——循环神经网络(RNN)。想象一下,你正在看电影,每一帧都连贯着前一帧的故事情节。RNN就像是这样一位观众,它能记住之前看到的内容,帮助理解当前的画面。是不是很酷?......
  • 【Python SHA256 摘要算法】
    SHA256是一种广泛使用的密码散列函数,用于生成数据的唯一指纹,即散列值。它属于SHA-2家族,该家族还包括SHA-384和SHA-512算法。SHA256算法在许多领域都有应用,例如:数据完整性验证:用于验证数据在传输或存储过程中是否被篡改。例如,在下载软件时,通常会提供软件的SHA256哈......
  • 数据结构与算法详解
    目录一、引言二、数据结构1.数组(Array)定义特点应用场景总结表格2.链表(LinkedList)定义特点应用场景总结表格3.栈(Stack)定义特点应用场景总结表格4.队列(Queue)定义特点应用场景总结表格5.树(Tree)定义特点应用场景总结表格6.哈希表(HashTable)定......