crc校验原理及推导过程

《crc校验原理及推导过程》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、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、α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）(a×b)%p=((a%p)×(b%p))%p（1-3）ab%p=((a%p)b)%p（1-4）结

3、合率：((a+b)%p+c)%p=(a+(b+c)%p)%p（1-5）((a×b)%p×c)%p=(a×(b×c)%p)%p（1-6）交换率：(a+b)%p=(b+a)%p（1-7）(a×b)%p=(b×a)%p（1-8）分配率：((a+b)%p×c)%p=((a×c)%p+(b×c)%p)%p（1-9）1.3线性分组码和循环码一个长度为n，有2k个码字的分组码，当且仅当其2k个码字构成GF(2)域上所有n维向量组成的向量空间的一个k维子空间是被称为n,k线性码。线性码的码字由k位消息部分和(n-k)位冗余校验部

4、分组成。循环码事线性分组码的一个重要的子类，其有两个引入注目的原因：一是通过带反馈连接的移位寄存器（一般称为线性时序电路），其编码和校正计算能够很容易的实现；二是由于其具有固有的代数机构，都能找到很多种实用的方法进行译码。一个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-

5、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+v

6、x=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个

7、长度为n-l的向量，这些向量组成了n-l,k-l线性码。这种码被称为缩短循环码，但不是循环码。缩短循环码的纠错能力与差错检测能力至少与原码相同。1.5冗余码所用符号数或信号码元数比表示信息所必需的数目多的代码叫冗余码。1.6循环冗余检验循环冗余检验英文名称为CyclicalRedundancyCheck，简称CRC。它是利用多项式除法及余数的原理来做错误检测的。它将要发送的数据比特序列当作一个信息多项式u(x)的系数，发送时去除以约定的生成多项式g(x)，得到一个余数多项式v(x)，将余数多项式加到信息多项式之后

8、发送到接收端，接收端同样用g(x)去除接收到的接收多项式r(x)，进行计算，然后把计算结果与由生成多项式g(x)决定的固定序列比较，来检测传输错误。由此可以看出其同时具有循环码和冗余码的特征，所以这种错误检测方法叫循环冗余校验，编码叫循环冗余校验码，即如式1-15所示。理论上可以证明循环冗余校验码的检错能力有以下特点：   (1)可检测出所有奇数位错。  (2)可检测出所