CRC 校验原理

《CRC 校验原理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CRC校验原理1、循环校验码（CRC码）：是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。2、生成CRC码的基本原理：任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如：代码1010111对应的多项式为x6+x4+x2+x+1，而多项式为x5+x3+x2+x+1对应的代码101111。3、CRC码集选择的原则：若设一个带有CRC的码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得t

2、(x)=A(x)g(x)=xRm(x)+r(x);其中:   m(x)为K次信息多项式；        g(x)称为生成多项式：g(x)=g0+g1x+2x2+...+g(R-1)x(R-1)+gRxR；r(x)为R-1次校验多项式；t(x)为编码后的带CRC的信息多项式。 发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。4、CRC校验码软件生成方法：借助于多项式除法，其余数为校验字段。例如：信息字段代码为:1011001；对应m(x)=x6+x4+x3+1；     假设生成多项式为：g(x)=x

3、4+x3+1；则对应g(x)的代码为:11001；     xRm(x)=x4m(x)=x10+x8+x7+x4对应的代码记为：10110010000；采用多项式除法除以g(x): 得余数为:1010    (即校验字段为：1010）发送方：发出的传输字段为: 10110011010                         信息字段      校验字段接收方：使用相同的生成码进行校验:接收到的字段/生成码（二进制除法）；                 如果能够除尽，则正确，否则出错。5、CRC校验码生成示意图：CRC 代数学的

4、一般性算法:在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如 1100101 表示为 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。 设编码前的原始信息多项式为m(x)，m(x)的最高幂次等于K；生成多项式为g(x)，g(x)的最高幂次等于R；CRC多项式为r(x),r(x)为R-1次校验多项式；编码后的带CRC的信息多项式为t(x)。 发送方编码方法：将m(x)乘以xR(即对应的二进制码序列左移R位)，再除以g(x)，所得余式即为r(x)。用公式表示为 t(x)

5、=xRm(x)+r(x) 接收方解码方法：将t(x)除以g(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。 举例来说，设信息码为1100，生成多项式为1011，即m(x)=x3+x2，g(x)=x3+x+1，则计算CRC的过程为:xrm(x)  =    x3(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。 除法　　除法是乘法的逆运算

6、，二进制除法和十进制除法也一样，而且更简单，每一位商数不是0，就是1。二进制除法　　（1）10100010÷1001；　　（2）10010011÷111。解（1）（2）　　10100010÷1001＝10010；10010011÷111＝10101。求二进制除法的商数和余数　　111010÷101解　　111010÷101所得商数是1011，余数是11。二进制除法是乘法的逆运算，规则如下：1÷1=10÷1=01÷0不允许0÷0不允许2.3二进制数算术运算    二进制数的加、减、乘、除四则运算，在数字系统中是经常遇到的，它们的运算规则与

7、十进制数很相似。加法运算是最基本的一种运算,利用它的运算规则可以实现其它三种运算。例如，减法运算可以借助改变减数的符号再与被减数相加,乘法运算可视为被乘数的连加，而除法则可视为被除数重复地减去除数。    1.二进制加法    二进制加法运算的规则可简单描述如下：        1被加数   0   0   1   1   1加  数+  0+  1+  0+  1+  1和   0   1   1  10  11    2.二进制减法    这里先介绍无符号数的减法，其规则如下：    借  入被减数   0   1   1   10

8、减 数-  0-  0-  1 -  1差   0   1   0    1    3.二进制乘法    二进制乘法与十进制乘法相同，下面列出了四条规则：０×０＝００×１＝０１×０＝０１×１＝１    4.