谁内帮我解释一下CRC校验C语言实现的原理,原理好像是把2进制每位分别提取出来与或,但程序不懂啥意思?

谁内帮我解释一下CRC校验C语言实现的原理,原理好像是把2进制每位分别提取出来与或,但程序不懂啥意思?,第1张

这里用的多项式为:X16 + X12 + X5 + X0 = 2^0+2^5+2^12+2^16=1 0001 0000 0010 0001=0x11021,因最高位一定为“1”,故略去计算只采用0x1021即可

X5 代表 Bit5,X12 代表 Bit12,1 自然是代表 Bit0,X16 比较特别,是指移位寄存器移出的数据。可以这样理解,与数据位做XOR运算的是上次 CRC值的 Bit15。

你这个实现里的for循环内容,可以理解成移位前 crc 的 Bit15 与数据对应的 Bit(*ptr&i)做 XOR运算,根据此结果来决定是否执行 crc^=0x1021。只要明白两次异或运算与原值相同,就不难理解这个程序。

if((crc&0x8000)!=0) {crc*=2crc^=0x1021} /* 余式CRC 乘以2 再求CRC */

if((*ptr&i)!=0) crc^=0x1021/* 再加上本位的CRC */

最近刚好有时间,整理了一下关于CRC的资料,详细对比了下程序的实现过程和原理,当然,高手都是不在意的。

本文主要介绍CRC的一些基础知识,个人收获是后面关于网上标准Demo程序的一些详细解析。见下一篇https://www.jianshu.com/p/c0d93c2e89ce

声明:本文定义部分参考网上多处资料,只是为了方便做个笔记,引用网文做一些更改,如有雷同,请私信说明并修改。

一、关于CRC的介绍

CRC即循环冗余校验码(Cyclic Redundancy Check):数据通信领域中最常用的一种差错校验码,其信息字段和校验字段长度可以任意指定,但要求通信双方定义的CRC标准一致。

二、工作原理

对于工控领域,我们主要利用CRC校验来处理各种数据流的数据正确性校验。

CRC原理 :在K位信息码(目标发送数据)后再拼接R位校验码,使整个编码长度为N位,因此这种编码也叫(N,K)码。通俗的说,就是在需要发送的信息后面附加一个数(即校验码),生成一个新的发送数据发送给接收端。这个数据要求能够使生成的新数据被一个特定的数整除。这里的整除需要引入模 2除法的概念,附上百度百科关于模2计算的链接:

https://baike.baidu.com/item/模2运算/18556715?fr=aladdin

那么,CRC校验的具体做法就是

(1)选定一个标准除数(K位二进制数据串)

(2)在要发送的数据(m位)后面加上K-1位0,然后将这个新数(M+K-1位)以模2除法的方式除以上面这个标准除数,所得到的余数也就是该数据的CRC校验码(注:余数必须比除数少且只少一位,不够就补0)

(3)将这个校验码附在原m位数据后面,构成新的M+K-1位数据,发送给接收端。

(4)接收端将接收到的数据除以标准除数,如果余数为0则认为数据正确。

注意: CRC校验中有两个关键点:一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串(或多项式);二是把原始帧与上面选定的除进行二进制除法运算,计算出FCS。前者可以随机选择,也可按国际上通行的标准选择,但最高位和最低位必须均为“1”

实例:对于数据10110011(16#B3),以指定除数110011求它的CRC校验码,其过程如下:

关于校验码的计算(重点来了)

单纯谈CRC的模2除法其实并不困难,但实际计算中经常会遇到计算出来的结果和实际不一致的情况,这也是这几天我在看的东西。

这里需要知道几个组成部分或者说计算概念:多项式公式、多项式简记式、数据宽度、初始值、结果异或值、输入值反转、输出值反转、参数模型。

1、多项式公式

对于CRC标准除数,一般使用多项式(或二项式)公式表示,如上例中除数11011的二项式为G(X)=X4+X3+X+1,X的指数就代表了该bit位上的数据为1,(最低位为0)。这里特别注意一下位数问题,除数的位数为二项式最高次幂+1(4+1=5),这个很重要。

2、多项式简记式

通过对CRC的基本了解我们知道,多项式的首尾必定为1,而这个1的位置在下一步计算一定为0,所以就把前面这个1给省略掉了,出现了一个叫简记式的东西,如上例中除数11011的简记式为1011,很多看过CRC高级语言源码的人会知道,对于CRC_16标准下G(X)=X16+X15+X2+1(16#18005)的poly值实际上是8005,这里使用的就是简记式。后面会对这个用法做一个说明。

3、数据宽度

数据宽度指的就是CRC校验码的长度(二进制位数),知道了CRC的运算概念和多项式,就可以理解这个概念了,CRC长度始终要比除数位数少1,与简记式长度是一致的。

以上三个数据就是我们经常能够用到的基本数据

4、初始值与结果异或值

在一些标准中,规定了初始值,则数据在进行上述二项式运算之前,需要先将要计算的数据与初始值的最低字节进行异或,然后再与多项式进行计算。

而在结果异或值不为零的情况下,则需要将计算得到的CRC结果值再与结果异或值进行一次异或计算,得到的最终值才是我们需要的CRC校验码。

这里可以看出,初始值与结果值的位数要求与数据宽度一致。

5、输入值反转与输出值反转

输入值反转的意思是在计算之前先将二项式反转,然后再用得到的新值和数据进行计算。如对于G(X)=X16+X15+X2+1(16#18005),其正向值为1 1000 0000 0000 0101,反转值则为1010 0000 0000 0001 1

输出值反转则是将最终得到的CRC结果反转。

通常,输入值反转后的结果值也会是反转的,所以这两个选项一般是同向的,我们只有在在线CRC计算器中会看到自由选择正反转的情况存在。

那么,这里引用CSDN博主 bobde163 的一段总结:

CRC16、CRC32等多字节的校验值的计算有几点需要清楚(只针对一次一个字节的算法):

1) 初始值不为0的情况下,该如何计算:

输入数据需要反转:先将要计算的数据与初始值的最低字节进行异或,再与反转后的多项式进行计算。

输入数据不需要反转:先将要计算的数据左移到与初始值对齐的位置(如CRC16算法,则左移8位,低位填充0;如CRC32算法,则左移24位,低位填充0)与初始值进行异或,再与正常的多项式进行计算。

2) 结果异或值不为0的情况:第一步算得到的CRC值再与结果异或值进行异或 *** 作得到最终的校验值:

输出数据反转:如果输入数据是反转的模式,则结果也是反转的

输出数据不反转:如果输入数据是不反转的模式,则结果也是不反转的

3)初始值的选择是可自己定义,很多不同的厂家使用的初始值是不一样,不一样的初始值得到的结果也是不一样的。

---------------------

原文:https://blog.csdn.net/bobde163/article/details/78760213

不同的二项式、初始值、结果异或值、反转原则都会造成最终的结果不一致,这就是为什么明明是正确的计算方式,有时候算出来的结果却总是不正确。

那么,如何去判断应该采用哪些原则呢?这里谈到最后一个概念:

6、参数模型

虽然CRC可以任意定义二项式、数据长度等,但没有一个统一的标准的话,就会让整个计算变得非常的麻烦。但实际上,不同的厂家经常采用不同的标准算法,这里列出了一些国际常用的模型表:

以上为关于CRC的笔记,下一篇讲一讲高级语言实现思路


欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/yw/8160977.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-04-14
下一篇 2023-04-14

发表评论

登录后才能评论

评论列表(0条)

保存