澳门新葡亰网址下载如何计算CRC校验码?

by admin on 2020年1月28日

    如何计算CRC校验码?

一、什么是CRC校验

CRC校验(即循环冗余校验)是数据通讯中最常采用检错纠错的一种校验方式,它广泛应用于数据链路层的数据传输中,以保证数据传输可靠性的一种差错检测措施。其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是一种数据传输检错功能,对数据进行多项式计算,并将得到的结果附在帧的后面,接收设备也执行类似的算法,以保证数据传输的正确性和完整性。CRC
算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。

循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。
校验码的具体生成过程为:假设要发送的信息用多项式C(X)表示,将C(x)左移R位(可表示成C(x)*2R),这样C(x)的右边就会空出R位,这就是校验码的位置。用
C(x)*2R 除以生成多项式G(x)得到的余数就是校验码。

任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如:代码1010111对应的多项式为x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111。

CRC校验

是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是一种数据传输检错功能,对数据进行多项式计算,并将得到的结果附在帧的后面,接收设备也执行类似的算法,以保证数据传输的正确性和完整性。

我先给你举个例子:
已知信息位为1100,生成多项式G(x) = x3+x+1,求CRC码。
M(x) = 1100 M(x)*x3 = 1100000 G(x) = 1011
M(x)*x3 / G(x) = 1110 + 010 /1011 R(x) = 010
CRC码为: M(x)*x 3+R(x)=1100000+010 =1100010
其原理是:CRC码一般在k位信息位之后拼接r位校验位生成。编码步骤如下:
(1)将待编码的k位信息表示成多项式 M(x)。
(2)将 M(x)左移 r 位,得到 M(x)*澳门新葡亰网址下载,xr 。
(3)用r+1位的生成多项式G(x)去除M(x)*xr 得到余数R(x)。
(4)将M(x)*xr 与R(x)作模2加,得到CRC码。

二、基本概念

CRC码的基本原理

在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。
校验码的具体生成过程为:假设要发送的信息用多项式C(X)表示,将C(x)左移R位(可表示成C(x)2R
),这样C(x)的右边就会空出R位,这就是校验码的位置。用 C(x)
2R
除以生成多项式G(x)得到的余数就是校验码。
任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如:代码1010111对应的多项式为x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111。

1.对应关系

多项式和二进制数有直接对应关系:X的最高幂次对应二进制数的最高位,以下各位对应多项式的各幂次,有此幂次项对应1,无此幂次项对应0。可以看出:X的最高幂次为R,转换成对应的二进制数有R+1位。

多项式包括生成多项式G(X)和信息多项式C(X)。

如生成多项式为G(X)=X4+X3+X+1,
可转换为二进制数码11011。

而发送信息位
101111,可转换为数据多项式为C(X)=X5+X3+X2+X+1。

 

校验方法

CRC校验采用多项式编码方法。
被处理的数据块可以看作是一个二进制多项式,例如,10110101可以看作是27+25+24+22+2^0,多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。
采用CRC校验时,发送方和接收方用同一个生成多项式g(x),并且g(x)的首位和最后一位的系数必须为1。CRC的处理方法是:发送方以g(x)去除t(x),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。
CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于k(k为g(x)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。

2.生成多项式

是接受方和发送方的一个约定,也就是一个二进制数,在整个传输过程中,这个数始终保持不变。

在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接收方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。

应满足以下条件:

A、生成多项式的最高位和最低位必须为1。

B、当被传送信息(CRC码)任何一位发生错误时,被生成多项式做除后应该使余数不为0。

C、不同位发生错误时,应该使余数不同。

D、对余数继续做除,应使余数循环。

例子

现假设选择的CRC生成多项式为G(X) = X^4 + X^3 +
1,要求出二进制序列10110011的CRC校验码。下面是具体的计算过程:

(1)首先把生成多项式转换成二进制数,由G(X) = X^4 + X^3 +
1可以知道(它一共是5位(总位数等于最高位的幂次加1,即4+1=5),然后根据多项式各项的含义(多项式只列出二进制值为1的位,也就是这个二进制的第4位、第3位、第0位的二进制均为1,其它位均为0)很快就可得到它的二进制比特串为11001

(2)因为生成多项式的位数为5,根据前面的介绍,得知CRC校验码的位数为4(校验码的位数比生成多项式的位数少1)。因为原数据帧10110011,在它后面再加4个0,得到101100110000,然后把这个数以“模2除法”方式除以生成多项式,得到的余数,即CRC校验码为0100

澳门新葡亰网址下载 1

例子

(3)把上步计算得到的CRC校验码0100替换原始帧101100110000后面的四个“0”,得到新帧101100110100。再把这个新帧发送到接收端。

(4)当以上新帧到达接收端后,接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除,验证余数是否为0,如果为0,则证明该帧数据在传输过程中没有出现差错,否则出现了差错。

3.校验码位数

CRC校验码位数 = 生成多项式位数 –
1。注意有些生成多项式的简记式中将生成多项式的最高位1省略了。

4.生成步骤

1、将X的最高次幂为R的生成多项式G(X)转换成对应的R+1位二进制数。

2、将信息码左移R位,相当于对应的信息多项式C(X)*2R

3、用生成多项式(二进制数)对信息码做除,得到R位的余数(注意:这里的二进制做除法得到的余数其实是模2除法得到的余数,并不等于其对应十进制数做除法得到的余数。)。

4、将余数拼到信息码左移后空出的位置,得到完整的CRC码。

三、举例

【例】假设使用的生成多项式是G(X)=X3+X+1。4位的原始报文为1010,求编码后的报文。

解:

1、将生成多项式G(X)=X3+X+1转换成对应的二进制除数1011。

2、此题生成多项式有4位(R+1)(注意:4位的生成多项式计算所得的校验码为3位,R为校验码位数),要把原始报文C(X)左移3(R)位变成1010
000

3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除(高位对齐),相当于按位异或:

1010000

1011


0001000

0001011


0000011

得到的余位011,所以最终编码为:1010 011

四、原则

若设码字长度为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次校验多项式(即CRC校验和),

g(x)称为生成多项式:

g(x)=g0+g1x1+ g2x2+…+g(R-1)x(R-1)+gRxR

发送方通过指定的g(x)产生CRC码字,接收方则通过该g(x)来验证收到的CRC码字。

五、生成方法

借助于模2除法则,其余数为校验字段。

例如:信息字段代码为:
1011001;对应m(x)=x6+x4+x3+1

假设生成多项式为:g(x)=x4+x3+1;则对应g(x)的代码为:
11001

x4m(x)=x10+x8+x7+x4
对应的代码记为:10110010000;

采用模2除法则: 得余数为: 1010(即校验字段为:1010)

发送方:发出的传输字段为: 1 0 1 1 0 0 1 1010

信息字段 校验字段

接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)

如果能够除尽,则正确,

给出余数(1010)的计算步骤:

除法没有数学上的含义,而是采用计算机的模二除法,即除数和被除数做异或运算。进行异或运算时除数和被除数最高位对齐,按位异或。

10110010000

^11001


01111010000

1111010000

^11001


0011110000

11110000

^11001


00111000

111000

^11001


001010

则四位CRC校验码就为:1010。

利用CRC进行检错的过程可简单描述为:在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息后边,构成一个新的二进制码序列数共k+r位,然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式”。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图