CRC校验原理及推导过程.docx

CRC校验原理及推导过程1代数引论参考文献1对伽罗华域、线性码、循环码、缩短循环码进行了很好的论述。1.1伽罗华域GF(2m)在伽罗华域GF(2m)中的元素由GF(2)上的本原多项式构造，域中的元素两两运算之后的结果依然是该域中的元素，域中运算是基于模2的。例如当m=4,本原多项式为：Gx=x4+x+1，GF(24)中的元素集合0,1,2,3,14，转换为十六进制数依次对应为0,1,2,4,8,3,6,C,B,5,A,7,E,F,D,9，转换为多项式依次对应为0,1,2,3,+1,2+,3+2,3+1,2+1,3+,2+1,3+2+,3+2+1,3+2+1,3+1。于是：15=14=1+3=+4=+1+=1 7+5=2+3+1=3+2+1=131.2模运算法则模运算与基本四则运算有些相似，但是除法例外。其规则如下 (a+b) % p = (a % p + b % p) % p （1-1） (a-b) % p = (a % p - b % p) % p （1-2） (ab) % p = (a % p)(b % p)% p （1-3） ab % p = (a % p)b) % p （1-4）结合率： (a+b) % p+c) % p = (a+(b+c) % p) % p （1-5）(ab) % pc)% p = (a(bc) % p) % p （1-6）交换率： (a+b) % p = (b+a) % p （1-7）(ab) % p = (ba) % p （1-8）分配率： (a +b)% pc) % p = (ac) % p + (bc) % p) % p （1-9）1.3 线性分组码和循环码一个长度为n，有2k个码字的分组码，当且仅当其2k个码字构成GF(2)域上所有n维向量组成的向量空间的一个k维子空间是被称为n,k线性码。 线性码的码字由k位消息部分和(n-k)位冗余校验部分组成。循环码事线性分组码的一个重要的子类，其有两个引入注目的原因：一是通过带反馈连接的移位寄存器（一般称为线性时序电路），其编码和校正计算能够很容易的实现；二是由于其具有固有的代数机构，都能找到很多种实用的方法进行译码。一个n,k 线性码C，如果每个码字的循环移位后的数仍是C的码字，则成为其为循环码。给定一个n,k循环码的生成多项式gx=gn-kxn-k+gn-k-1xn-k-1+g1x+1，假设待编码的消息为u=uk-1,uk-2,u1,u0，则相应的消息多项式为：u(x)=uk-1xk-1+uk-2xk-2+u1x+u0 （1-10）用xn-k乘以u(x)，得到次数不大于(n-1)的多项式为：xn-ku(x)=uk-1xn-1+uk-2xn-2+u1xn-k-1+u0xn-k （1-11）用生成多项式g(x)除xn-ku(x)得到：xn-ku(x)=mxgx+v(x) （1-12）其中，mx和v(x)分别为商式和余式。由于g(x)的最高次数为(n-k)，则v(x)的次数必不大于(n-k-1)。从而有vx=vn-k-1xn-k-1+v1x+v0 （1-13）整理得到次数不大于(n-1)的多项式：xn-kux+vx=mxgx =uk-1xn-1+uk-2xn-2+u1xn-k-1+u0xn-k + vn-k-1xn-k-1+v1x+v0 （1-14）该多项式能被多项式g(x)整除。相应的完整码字为：(uk-1,uk-2,u1,u0, vn-k-1,v1,v) （1-15）1.4缩短的循环码在系统设计中，如不能找到一个具有合适的自然长度的或者信息位数目的码字，缩短码是一种有效的解决方案。对一个n,k 循环码C，其中信息位的高l位均为零的码字共有2k-l个，构成了C的线性子码。若从这些码字中删除这l个零信息位，将得到2k-l个长度为n-l的向量，这些向量组成了 n-l,k-l 线性码。这种码被称为缩短循环码，但不是循环码。缩短循环码的纠错能力与差错检测能力至少与原码相同。1.5冗余码所用符号数或信号码元数比表示信息所必需的数目多的代码叫冗余码。1.6循环冗余检验循环冗余检验英文名称为Cyclical Redundancy Check，简称CRC。它是利用多项式除法及余数的原理来做错误检测的。它将要发送的数据比特序列当作一个信息多项式u(x)的系数，发送时去除以约定的生成多项式g(x)，得到一个余数多项式v(x)，将余数多项式加到信息多项式之后发送到接收端，接收端同样用g(x)去除接收到的接收多项式r(x)，进行计算，然后把计算结果与由生成多项式g(x)决定的固定序列比较，来检测传输错误。由此可以看出其同时具有循环码和冗余码的特征，所以这种错误检测方法叫循环冗余校验，编码叫循环冗余校验码，即如式1-15所示。理论上可以证明循环冗余校验码的检错能力有以下特点： (1)可检测出所有奇数位错。(2)可检测出所有双比特的错。(3)可检测出所有小于、等于校验位长度的突发错。2 CRC码编码在1.3节线性分组码和循环码中得到算式1-15的计算过程就是循环冗余校验码的编码步骤，归纳起来有以下三步骤：第1步 预先用xn-k乘以信息多项式u(x)，得到xn-ku(x)；第2步 用生成多项式g(x)去除xn-ku(x)，获得余式vx；第3步 整合余式v(x)和xn-ku(x)，获得码多项式xn-kux+vx。对于一个n,k循环码，生成多项式gx=xn-k+gn-k-1xn-k-1+g1x1+1，编码电路有两种方式：一，信息位由高位到低位的顺序从循环移位寄存器体左侧依次输入，信息位完全进入循环体后继续输入n-k-1个0，最后循环体中寄存器的值就是余式码字；图1 左侧串行输入循环移位寄存器体二，信息位由高位到低位的顺序从循环移位寄存器体右侧依次输入，信息位完全进入循环体后寄存器的值就是余式码字。图2 右侧串行输入循环移位寄存器体注：1，移位寄存器循环体中余式码字低位在左侧，高位在右侧。以CRC4为例，其生成多项式为：gx=x4+x+1，当信息多项式u=(101011)时用两种方法计算得到得余式码字是一样的：v=(0100)，编码后完整地码字为：(1010110100)。图三所示的两种计算余式码字的方法对应于数字电路中D触发器、加法器、乘法器的组成的循环体结构分别为图1、图2所示。图3 信息位为单比特两种方法比较3 CRC码校验3.1 CRC码校验的基本原理所有的CRC校验都是基于以下这个等式：Mxr+R mod G=0 (3-1)其中M=xrux, u(x)=un-l-1xn-l-1+u1x+u0, r=n-k, R=vr-1xr-1+v1x+v0, gx=gn-kxn-k+gn-k-1xn-k-1+g1x+1。M是信息字段（Message）多项式，R是校验字段（Remainder）多项式，r是校验字段多项式的最高次幂（也就是校验字段的长度，CRC-32 对应的n-k，依次类推），n-l是信息字段加上冗余校验码后多项式的最高次幂，k-l是信息字段多项式的最高次幂，n取决于k的值即n=2k，l是信息字段长度，G是生成(Generator)多项式。由此可见CRC32信息字段最大比特数为232-32，除此之外的信息字段编码就是缩短的CRC32编码。发送端M和G（对某一种确定的CRC校验，其G是固定的）是已知的，CRC计算就是 为了求出校验字段R；接收端M，R，G都是已知的，主要的操作都是为了验证等式是否成立，方法有很多种。下表展示了用于被用于一些常用的CRC标准的生成多项式，Hex列表示生成多项式对应的十六进制，MSB（most significant bit，可以理解为最左边的一位）省略，因为该位总是为1：表一 几种典型CRC生成多项式3.2发送端和接收端的具体处理方法参考文献2对CRC校验码的接收端有具体处理的描述，缺少中间推导过程。CRC校验码在工程应用过程中相比数学计算稍微有些变化：1， 在发送端对全0数据包的编码处理。数学计算中，当信息字段全部为0时的得到的余式码字也是全零的，但是在工程应用中，当非0信息字段在编码后发送给接收端，在线路传输中出现干扰或者是其他情况的错误，导致接收端收到的全零数据，即信息字段和余式字段都为0。如果在发送端不做特殊处理，在接收端就检验不出来这样的错误数据包。于是，在通信传输时，很多协议规定在发送端对CRC编码时定义一个Key寄存器，对CRC编码进行初始化，定义一个不为0的初值，Key寄存器通常被设置为全1。结合图1、图2来说，就是在信息输入给循环体之前，其D触发器的值为1。2， 对接收端收到的数据包中拖尾0数据的处理。接收端接收到信息字段和余式字段，计算出数据包的余式码字，并与余式字段做比较，就能检测出错误。更简单的做法是，接收端对接收 到的所有数据求余式（包括信息字段和余式字段），如果没有传输错误所得的余式一定为0。但是，余式为0并不一定能够说明数据包没有改变，如果数据包在余式字段后有0增加或者删除的情况出现，就无法被检测出来。为了更好的理解公式的推导过程，需要用到1.2节中的几个关于取模运算法则。接收端如何才能识别无差错的传输呢？我们知道在发送侧满足：Mxr+R mod G=0 (3-1) 如果用R表示R对1取反，我们得到： (Mxr+R) mod G = Mxr+xr-1+xr-2+ +1-R mod G =Mxr-R+xr-1+xr-2+ +1 mod G =Mxr+R+xr-1+xr-2+ +1 mod G = Mxr+ R mod G+ xr-1+xr-2+1 mod G mod G =(0+xr-1+xr-2+1 mod G mod G =(xr-1+xr-2+1) mod G) mod G =(xr-1+xr-2+1) mod G因此，在发送端发出来的无差错的传输的校验序列应该是：(xr-1+xr-2+1) mod G (3-2)在接收侧收到的完整码字多项式：M=Mxr+R (3-3)用多项式G 对Mxr取模为：(Mxr) mod G= Mxr+Rxr mod G =Mxr+xr-1+xr-2+1-Rxr mod G =Mxr+xr-1+xr-2+1+Rxr mod G =Mxr+R+(xr-1+xr-2+1)xr mod G =(Mxr+R+(xr-1+xr-2+1) mod G )xrmod G =(xr-1+xr-2+1 mod G )xrmod G =xr-1+xr-2+1xrmod G因此，在接收端计算出的无差错的传输的校验和应该是：xr-1+xr-2+1xr mod