CRC 校验原理
CRC校验原理
1、循环校验码(CRC码):是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。
2、生成CRC码的基本原理:任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如:代码1010111对应的
532多项式为x6+x4+x2+x+1,而多项式为x+x+x+x+1对应的代码101111。 3、CRC码集选择的原则:若设一个带有CRC的码字长度为N,信息字段为K位,校验字段为R位(N=K+R),则对于CRC码集中的任一码字,存在且仅存在一个R次多项式g(x),使得
Rt(x)=A(x)g(x)=xm(x)+r(x); 其中: m(x)为K次信息多项式;
2(R-1)R g(x)称为生成多项式:g(x)=g+gx+x+...+gx+gx; 01 2(R-1)R
r(x)为R-1次校验多项式 ;
t(x)为编码后的带CRC的信息多项式。
发送方通过指定的g(x)产生CRC码字,接收方则通过该g(x)来验证收到的CRC码字。
4、CRC校验码软件生成方法:
借助于多项式除法,其余数为校验字段。
643例如:信息字段代码为: 1011001;对应m(x)=x+x+x+1;
43 假设生成多项式为:g(x)=x+x+1;则对应g(x)的代码为: 11001;
R410874 xm(x)=xm(x)=x+x+x+x 对应的代码记为:10110010000; 采用多项式除法除以g(x): 得余数为: 1010 (即校验字段为:1010) 发送方:发出的传输字段为: 1 0 1 1 0 0 1 1 0 10
信息字段 校验字段
接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法);
如果能够除尽,则正确,否则出错。
5、CRC校验码生成示意图:
CRC 代数学的一般性算法:
在代数编码理论中,将一个码组
示为一个多项式,码组中各码元当作多项式的
65432系数。例如 1100101 表示为 1?x+1?x+0?x+0?x+1?x+0?x+1,
652即 x+x+x+1。
设编码前的原始信息多项式为m(x),m(x)的最高幂次等于K;生成多项式为g(x),g(x)的最高幂次等于R;CRC多项式为r(x), r(x)为R-1次校验多项式;编码后的带CRC的信息多项式为t(x)。
R发送方编码方法:将m(x)乘以x(即对应的二进制码序列左移R位),再除以g(x),
R所得余式即为r(x)。用公式表示为 t(x)=xm(x)+r(x)
接收方解码方法:将t(x)除以g(x),如果余数为0,则说明传输中无错误发生,否则说明传输有误。
举例来说,设信息码为1100,生成多项式为1011,即m(x)=x3+x2,g(x)=x3+x+1,则计算CRC的过程为:
r3xm(x) = x(x3+x2) = x6+x5 = (x3+x2+x) + x g(x) x3+x+1 x3+x+1 x3+x+1
即 r(x)=x。注意到g(x)最高幂次R=3,得出CRC为010。
除法
除法是乘法的逆运算,二进制除法和十进制除法也一样,而且更简单,每一位商数不是0,就是1。
二进制除法
(1)10100010?1001;
(2)10010011?111。
解 (1) (2)
10100010?1001,10010; 10010011?111,10101。
求二进制除法的商数和余数
111010?101
解
111010?101 所得商数是1011,余数是11。
二进制除法是乘法的逆运算,规则如下: 1?1=1 0?1=0 1?0 不允许 0?0 不允许
2.3 二进制数算术运算
二进制数的加、减、乘、除四则运算,在数字系统中是经常遇到的,它们的运算规则与十
进制数很相似。加法运算是最基本的一种运算,利用它的运算规则可以实现其它三种运算。
例如,减法运算可以借助改变减数的符号再与被减数相加,乘法运算可视为被乘数的连加,
而除法则可视为被除数重复地减去除数。
1.二进制加法
二进制加法运算的规则可简单描述如下:
1
0 1 1 1 0被加数
加 数 + 0 + 1 + 0 + 1 + 1
和 0 1 1 10 11
2.二进制减法
这里先介绍无符号数的减法,其规则如下:
借 入
0 1 1 10 被减数
减 数 - 0 - 0 - 1 - 1
差 0 1 0 1
3.二进制乘法
二进制乘法与十进制乘法相同,下面列出了四条规则:
,×,,, ,×,,,
,×,,, ,×,,,
4.二进制除法
二进制除法与十进制除法相同。
5.用带符号位的二进制数实现减法运算
(1)带符号位的二进制数
一个二进制数既可表示为正数,也可表示为负数,其方法是在二进制数之前加一符号位。通常用,表示正数,而用,表示负数,其余数位表示数的大小,例如, +5=0101,-5=1101。
(2)补码的概念
补码是负数的一种表示方法。现以人们熟悉的十进制数为例来说明补码的概念。
常规减法运算 以10为模的减法运算
87 87 87
- 24 - 24 = + 76
63 163
可见,将减数24变为以10为模(称为模10)的补码为+76,然后相加并丢弃进位数,其结果相同。模10的补码是这样求得的,模数10减1作为底数9,然后将减数的每一位数码从底数9中减去得到相应的数码,然后加1便得到补码。在上例中99-24+1=75+1=76。 (3)二进制的模2补码及减法运算
与模10的补码相类似,当二进制形成模2的补码时,模数2减1作为底数1,然后将减数的每一位从底减去,得到相应的位的数码,然后加1,便得到补码。例如,011的模2补码为101。实际上,一种简便的方法是将二进制数码中的0变为1、1变为0,再加1即可得到模2的补码。
常规的减法运算 模2补码的减法运算
0111 被减数 7 0111
减 数 + 1101- 0011, - 3
差 4 100 10100
丢弃进位
由上可知,模2补码的减法运算与常规运算的结果一致。在此例中还需注意到在运算中,符号参加运算。有关二进制数的四则运算细节,可参阅有关文献[8]、[9]。
1.数字电路处理的信号是离散信号,这种信号的有无可以用二进制信息0和1表示,其大小也可以用二进制数表示。
2.十进制、二进制、八进制、十六进制的构成法是相同的,不同点仅在于它们的基数和权不相等。基数是指数制中使用的数码的个数,权是指数制中每一位所具有的值的大小。
3.在数字系统中,任何数字、字母、符号都必须变成0和1的形式,才能传送和处理,为表达众多的信息,产生了二进制编码。