CRC校验原理及推导过程

1、CR俄验原理及推导过程1 代数引论参考文献1对伽罗华域、线性码、循环码、缩短循环码进行了很好的论述。1.1 伽罗华域(2 )在伽罗华域(2 )中的元素由(2)上的本原多项式构造，域中的元素两两运算之后的结果依然是该域中的元素，域中运算是基于模2 的。例如当 = 4,本原多项式为：( )=+ 4+ 1 ，(2 )中的元素集合 40,1, 2, 3,?, 14，转换为十六进制数依次对应为01,2,4,8,3,6, , ,5, ,7, , , ,9，转换为多项式依次对应为0,1,2,3, + 1,2+3 + 2,3 + + 1 2 + 1 3 + 2 + + 1 3+ 2 +15 = ? 14 =

2、?(1 + 3)= + 4 = + 1 + = 17+ 5= (2+ )+ (3+ + 1)= 3+ 2+ 1 =1.2 模运算法则模运算与基本四则运算有些相似，但是除法例外。其规则如下(a+b) % p = (a% p+ b % p) % p( 1-1 )(a-b) % p= (a % p - b % p) % p( 1-2)(a * b) % 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 )(a x b) % p x c)% p =

3、(a x (b x c) % p) % p(1-6)交换率：(a+b) % p = (b+a) % p( 1-7 )(a x b) % p = (b x a) % p(1-8 )分配率：(a +b)% p * c) % p = (a * c) % p + (b * c) % p) % p (1-9)1.3 线性分组码和循环码一个长度为，有 2 个码字的分组码，当且仅当其2 个码字构成(2)域上所有 维向量组成的向量空间的一个维子空间是被称为( ,)线性码。线性码的码字由位消息部分和( ? )位冗余校验部分组成。循环码事线性分组码的一个重要的子类，其有两个引入注目的原因：一是通过带反馈连接的移位

4、寄存器(一般称为线性时序电路)，其编码和校正计算能够很容易的实现；二是由于其具有固有的代数机构，都能找到很多种实用的方法进行译码。一个(，)线性码C,如果每个码字的循环移位后的数仍是C的码字，则成为其为循环码。给定一个 ( ,)循环码的生成多项式g(x) = ? + ? ?1 ? ?1 + ? 1 + 1，假设待编码的消息为u = ( ?1, ?2，? 1，U0),则相应的消息多项式为:u( ) = ? 1? 1 + ? 2 ? 2 + ? + 1 + u0( 1-10)用 ? 乘以u( )，得到次数不大于( ? 1)的多项式为：? u() = ?1 ?1 + ?2 ?2+ ? + 1 ? ?

5、1 + u0 ?11)用生成多项式g(x)除？ u(加到：? u() = () () + v()( 1-12)其中，()和v(价别为商式和余式。由于g(x)的最高次数为(？)，则()的次数必不大于( ? - 1)。从而有( ) = ? ?1 ? ?1 + ? + 1 + 0( 1-13)整理得到次数不大于( ? 1)的多项式：? u( ) + ()= ()() = ?1?1 + ?2 ?2+? + 1 ? ?1 +u0+? ?1? ?1 +? + 1 + 01-14)该多项式能被多项式g(x)整除。相应的完整码字为：( ?1, ?2,? 1,u0, ? ?1,? 1,)15)1-1-1.4 缩

6、短的循环码在系统设计中，如不能找到一个具有合适的自然长度的或者信息位数目的 码字，缩短码是一种有效的解决方案。?对一个( , ) 循环码，其中信息位的高位 均为零的码字共有2 个，构成?了 的线性子码。若从这些码字中删除这个 零信息位，将得到2 ? 个长度为n? 的 向量，这些向量组成了( ? , ? ) 线性码。这种码被称为缩短循环码，但不是循环码。缩短循环码的纠错能力与差错检测能力至少与原码相同。1.5 冗余码所用符号数或信号码元数比表示信息所必需的数目多的代码叫冗余码。1.6 循环冗余检验循环冗余检验英文名称为 Cyclical Redundancy Check,简称CRC它是利 用多项

7、式除法及余数的原理来做错误检测的。它将要发送的数据比特序列当作一个信息多项式u()的系数，发送时去除以约定的生成多项式 g(x),得到一个余数多项式v( )，将余数多项式加到信息多项式之后发送到接收端，接收端同样用g(x)去除接收到的接收多项式r(),进行计算，然后把计算结果与由生成 多项式g(x)决定的固定序列比较，来检测传输错误。由此可以看出其同时具有 循环码和冗余码的特征，所以这种错误检测方法叫循环冗余校验，编码叫循环冗余校验码，即如式1-15 所示。理论上可以证明循环冗余校验码的检错能力有以下特点：(1) 可检测出所有奇数位错。(2) 可检测出所有双比特的错。(3) 可检测出所有小于、

8、等于校验位长度的突发错。2 CRC马编码在 1.3 节线性分组码和循环码中得到算式1-15 的计算过程就是循环冗余校验码的编码步骤，归纳起来有以下三步骤：第 1 步 预先用 ? 乘以信息多项式u( )，得到 ? u( )；第2步 用生成多项式g(x)去除？ u(),获得余式v();第 3 步 整合余式v( )和? u( )，获得码多项式? u( ) + ( )。对于一个 ( ,)循环码，生成多项式g(x) =? + ? ?1 ? ?1 + ? + 1 1 + 1，编码电路有两种方式：一，信息位由高位到低位的顺序从循环移位寄存器体左侧依次输入，信息位完全进入循环体后继续输入n ? ? 1 个 0

9、，最后循环体中寄存器的值就是余式码字；图1左侧串行输入循环移位寄存器体二，信息位由高位到低位的顺序从循环移位寄存器体右侧依次输入，信息 位完全进入循环体后寄存器的值就是余式码字。Din图2右侧串行输入循环移位寄存器体注：1,移位寄存器循环体中余式码字低位在左侧，高位在右侧。以CRC物例，其生成多项式为：g(x) = + + 1,当信息多项式u 二 (101011)时用两种方法计算得到得余式码字是一样的：=(0100),编码后完整地码字为：(1010110100)。图三所示的两种计算余式码字的方法对应于 数字电路中D触发器、加法器、乘法器的组成的循环体结构分别为图1、图2所示。方法方法10011

10、 000；0101011010 H 。5 : 1: :101 I：0 ：1010110101 ;10011 ;0110 ：101101 i01101 1001100001' 10011-001!0000000110-100001110010011011110000011110100111001T0100100 00100011000100010 0 0100图3信息位为单比特两种方法比较3 CRC马校验3.1 CRC码校验的基本原理箕布的人吊饭验都是基于以下这个等式:(+ )=0(3-1)u( ) 二 ? ? 1? ?1 + ? + 1 + U0 ,0110110000 1010101

11、000 10100,g（x） =?+?1 '1+?1 + 1OM是信息字段（Message多项式，R是校验字段（Remainder）多项式，r 是校验字段多项式的最高次幕（也就是校验字段的长度，CRC-32对应的？k,依次类推），？是信息字段加上冗余校验码后多项式的最高次幕，k ?是信 息字段多项式的最高次幕， 取决于k的值即=2,k是信息字段长度，G是生 成（Generator）多项式。由此可见CRC32言息字段最大比特数为232- 32,除此之 外的信息字段编码就是缩短的 CRC3编码。发送端M和G （对某一种确定的CR仪验，其G是固定的）是已知的，CRC 计算就是 为了求出校验字

12、段R;接U端M R, G都是已知的，主要的操作都是 为了验证等式是否成立，方法有很多种。下表展示了用于被用于一些常用的 CRCB准的生成多项式，Hex列表示 生成多项式对应的十六进制，MSB（most significant bit ,可以理解为最左边 的一位）省略，因为该位总是为1:Cuniniun心Puhnumbil ferlieiCRC-1212X=+E 匚 +13-丫2- 180FCR 匚16工演+JC1$+12 一8005CRC-CC1TT16'b+X- +15 + 1I02jCRC-3232工式 + x26 _4/2 + ,16一上】.也一X*与 A4 + T? 一，4 t

13、04CI IDB7表一几种典型CRC£成多项式3.2发送端和接收端的具体处理方法参考文献2对CRC验码的接收端有具体处理的描述，缺少中间推导过程。CRCJ验码在工程应用过程中相比数学计算稍微有些变化：1,在发送端对全0数据包的编码处理。数学计算中，当信息字段全部为0时的得到的余式码字也是全零的，但是 在工程应用中，当非0信息字段在编码后发送给接收端，在线路传输中出现干 扰或者是其他情况的错误，导致接收端收到的全零数据，即信息字段和余式字段都为00如果在发送端不做特殊处理，在接收端就检验不出来这样的错误数 据包。于是，在通信传输时，很多协议规定在发送端对 CRCS码时定义一个 Key寄

14、存器，对CR诉码进行初始化，定义一个不为0的初值，Key寄存器通常 被设置为全1。结合图1、图2来说，就是在信息输入给循环体之前，其 D触发 器的值为1。2,对接收端收到的数据包中拖尾0数据的处理。接收端接收到信息字段和余式字段，计算出数据包的余式码字，并与余式 字段做比较，就能检测出错误。更简单的做法是，接收端对接收到的所有数据求余式（包括信息字段和余式字段），如果没有传输错误所得的余式一定为00但是，余式为0并不一定能够说明数据包没有改变，如果数据包在余式字段 后有0增加或者删除的情况出现，就无法被检测出来。为了更好的理解公式的推导过程，需要用到 1.2节中的几个关于取模运算 法则。接收端

15、如何才能识别无差错的传输呢？我们知道在发送侧满足：(+ )=0(3-1)如果用卡表示R对1取反，我们得到:(Mx+ ) mod G = (Mx+ (x ?1 + x ?2+ ? + 1 ?)+x?1 + x?2+ ? + 1)+)+x?1+x?2 + 1)=(M + ) mod G) + ( ? 1 + ?2 + ? + 1)=(0 + (?1 + ?2+ ? + 1)=(?1 + ?2+ ? + 1)=(?1 +?2 + ? + 1)因此，在发送端发出来的无差错的传输的校验序列应该是:(?1 + ?2 + ? + 1)(3-2)在接收侧收到的完整码字多项式:(3-3)用多项式G对取模为:()=(+)=+ (?1+ ?2+ ?+ 1?)=+ (?1+ ?2+ ? + 1+ )=+ + (?1+ ?2 + ? + 1)=(+ + (?1+ ?2+ ? + 1)=(?1 + ?2 + ? + 1)=(?1+ ?2+?+ 1)因此，在接收端计算出的无差错的传输的校验和应该是:(?1+ ?2+? +1)(