CRC校验全解

Python020

CRC校验全解,第1张

这几天一直在看CRC校验算法。CRC版本众多,网站上实现算法一大坨,可一开始根本搞不清楚那个是哪个。连续上百度,哔哩哔哩,知乎看了很多解读CRC算法的,终于有了一些眉目,打算写下来,方便日后参考。

CRC算法核心其实只有一种,即二进制除法的实现,版本众多的原因主要有以下几个原因:

CRC字段的长度

多项式公式

初始值

输出是否水平翻转

输入是否水平翻转

结果异或值

我绝大多数的文章都只谈到了CRC字段的长度和多项式公式,没有涉及剩余的三项在crc算法中的应用。

CRC字段的长度 ,字段越长,对于crc算法的校验能力越强。如果我们用出错的概率来评估校验能力的话。N长度的字段,他的校验能力为1/2**N。此处的运算符号采用Python语言中的含义。

一般而言,我们取的长度主要有8位,16位和32位。当然也有一些比较奇特的,4位,5位和6位,还有7位。

多项式公式 是我们二进制多项式算法中的除数。不同的算法往往取的多项式是不一样的。

初始值 ,是指CRC字段的初始值。常常是从0和全是1中选择。

输入反转。 具体的操作方法实施将输入的数据按照字节为单位进行水平反转。比如01000001,翻转结果是10000010。

输出翻转 。输出翻转的操作与输入翻转操作是一样的。只是输出翻转是将整个CRC字段进行水平翻转。

结果异或值 ,是用来和 通过上述的算法算出来的结果 进行异或的一个数据值。如果这个值是0的话,那么就相当于没有进行异或。

为什么需要这么多看起来乱七八糟的种类呢。这些算法分别针对不同的数据的检验。针对不同的数据的特性,比如说某些数据,一开始就会有大量的零,如果不采用输入翻转或者初始值的话,那么这些0就对于校验结果没有任何影响。这就如我们想要的结果有出入了,我们希望校验结果和数据是一一对应的,并且是唯一的。如果不唯一那么,校验结果也就失去了意义。因此这么多算法的出现,主要原因就是为了适应不同的数据字符串的特点。

下面就是一些例子了。

验证网站: http://www.ip33.com/crc.html

对数据块进行crc16校验:

CRC-16码由两个字节构成,在开始时CRC寄存器的每一位都预置为1,然后把CRC寄存器与8-bit的数据进行异或(异或:二进制运算 相同为0,不同为1;0^0=00^1=11^0=11^1=0), 之后对CRC寄存器从高到低进行移位,在最高位(MSB)的位置补零,而最低位(LSB,移位后已经被移出CRC寄存器)如果为1,则把寄存器与预定义的多项式码进行异或,否则如果LSB为零,则无需进行异或。重复上述的由高至低的移位8次,第一个8-bit数据处理完毕,用此时CRC寄存器的值与下一个8-bit数据异或并进行如前一个数据似的8次移位。所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。

1.设置CRC寄存器,并给其赋值FFFF(hex)。

2.将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或,并把结果存入CRC寄存器。

3.CRC寄存器向右移一位,MSB补零,移出并检查LSB。

4.如果LSB为0,重复第三步;若LSB为1,CRC寄存器与多项式码相异或。

5.重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。

6.重复第2至第5步直到所有数据全部处理完成。

7.最终CRC寄存器的内容即为CRC值。

CRC(16位)多项式为 X16+X15+X2+1,其对应校验二进制位列为1 1000 0000 0000 0101。

7E 00 05 60 31 32 33 计算CRC16校验结果是:5B3E。

CRC校验 1、循环校验码(CRC码):是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。 2、生成CRC码的基本原理:任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如:代码1010111对应的多项式为x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111。 3、CRC码集选择的原则:若设码字长度为N,信息字段为K位,校验字段为R位(N=K+R),则对于CRC码集中的任一码字,存在且仅存在一个R次多项式g(x),使得 V(x)=A(x)g(x)=xRm(x)+r(x) 其中: m(x)为K次信息多项式, r(x)为R-1次校验多项式, g(x)称为生成多项式: g(x)=g0+g1x+ g2x2+...+g(R-1)x(R-1)+gRxR 发送方通过指定的g(x)产生CRC码字,接收方则通过该g(x)来验证收到的CRC码字。 4、CRC校验码软件生成方法: 借助于多项式除法,其余数为校验字段。 例如:信息字段代码为: 1011001;对应m(x)=x6+x4+x3+1 假设生成多项式为:g(x)=x4+x3+1;则对应g(x)的代码为: 11001 x4m(x)=x10+x8+x7+x4 对应的代码记为:10110010000; 采用多项式除法: 得余数为: 1111 (即校验字段为:1111) 发送方:发出的传输字段为: 1 0 1 1 0 0 1 1111 信息字段 校验字段 接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法) 如果能够除尽,则正确, 给出余数(1111)的计算步骤: 除法没有数学上的含义,而是采用计算机的模二除法,即,除数和被除数做异或运算 1011001 1100100 =111101 111101 110010 = 1111