循环冗余校验码

1、循环循环冗余检查（冗余检查（CRCCRC）是一种数据传输检错功能，）是一种数据传输检错功能，对数据进行对数据进行多项式多项式g g（X X）计算）计算，并将得到的结果，并将得到的结果附附在在要传输的信息要传输的信息的的后面，接收设备也执行类似后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。若的算法，以保证数据传输的正确性和完整性。若CRCCRC校验不通过，系统重复向硬盘复制数据，陷校验不通过，系统重复向硬盘复制数据，陷入死循环，导致复制过程无法完成。出现循环冗入死循环，导致复制过程无法完成。出现循环冗余检查错误的可能原因非常多，硬件软件的故障余检查错误的可能原因非常多，硬件软件

2、的故障都有可能都有可能。接收方如何检查收到的信息有无错误？接收方如何检查收到的信息有无错误？ 首先接收方和发送方约定一个首先接收方和发送方约定一个“生成多项生成多项式式”g(xg(x）。相当于两方传递信息需要对的口令。）。相当于两方传递信息需要对的口令。CRC（Cyclic Redundancy Check）循环冗余校验码，是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来确认信息的困惑。对通信的可靠性检查就需要校验，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结

3、果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。（倒推法）：（倒推法）：发送方发送的是T(x)，接收方接收到的是R(x)，若T(x)和R(X)相等，则传输的过程中没有出现错误。如何判断T(x)和R(X)是否相等？若R(X)能够被g(x)整除，则接收方认为T(x)和R(X)相等，即传输的过程中没有出现错误。发送方要传输的信息info包含在T(x)里，info是T(x)的一部分，但不能说info就是T(x)。实际应用中，g(x)的取值是有限制的，它受限于以下国际标准：CRC-CCITT=x16+x12+x5+1CRC-16=x16+x15+x2+1CRC-12=x1

4、2+x11+x3+x2+x+1关于g(x)的国际标准还有一些，这里不一一介绍。人工计算循环冗余校验码需要先弄清的知识：多项式除法、异或运算。CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为（n,k）码。它的编码规则是：移位 将原信息码（kbit）左移r位（k+r=n)，而后尾巴上添r个0。相除 运用一个生成多项式g(x)（必须转换成二进制数）用模2除上面的式子，得到的余数就是校验码。 移位后的信息码mod多项式g(x)=校验码非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，

5、就是加法不考虑进位，公式是：0+0=1+1=0,1+0=0+1=1即异则真，非异则假。由此得到定理：a+b+b=a 也就是模2减和模2加直值表完全相同。有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x）生成CRC校验码。CRC码生成和校验基本分为三步：第一步：在数据单元(k位）的末尾加上r个0。r是一个比预定除数g(x)的比特位数(r+1)少1的数。第二步：采用二进制除法将新的加长的数据单元（k+r位)除以除数g(x) 。由此除法产生的余数就是循环冗余码校验码。第三步：求CRC循环冗余校验码(K+r)被除数+r(余数)如果余数位数小于r，最左的缺省位数为0。如果余数为0,则r=0

6、。生成多项式应满足以下原则a、生成多项式的最高位和最低位必须为1。b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。c、不同位发生错误时，应该使余数不同。d、对余数继续做模2除，应使余数循环。 任何一个二进制数序列可以和一个只含有0和1两个系数的代数多项式建立起一一对应的关系。因此，用来求CRC码的那个除数通常用多项式来表示。原因如下：代数多项式很短可以通过多项式来进行概念的数学证明。 任何一个n位的二进制数都可以用一个n-1 次的多项式来表示,这种多项式叫码多项式（又叫信息多项式） 。码多项式与二进制序列之间的一一对应关系：（an-1 an-2a1a0）

7、N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0码多项式以n=3位二进制数为例 二进制数 对应多项式 000 001 010 011 100 101 111 01xx+1x2x2+1x2+ x+1n1011011 x6+x4+x3+x+1nx5+x4+x2+x 110110码多项式运算法则:二进制码多项式的加减运算为模2加运算，即两个码多项式相加时，对应项系数进行模2加减。乘除运算与普通多项式类似；模2加减：即各位做不带进位、借位的按位加减。这种加减运算实际上就是逻辑上的异或运算。即加法和减法等价。码多项式码多项式生成多项式G(x):求CRC码时所用的“除数”所对应的多

8、项式叫生成多项式。在串行通信中通常使用下列三种生成多项式G（X）来产生CRC码。CRC-16：G(x)=X16+X15+X2+1，美国二进制同步系统中采用。CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推荐。CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7+ X5+X4+X2+X+ 1码多项式码多项式循环冗余码生成器采用模2除法。下图显示了这一过程。CRC校验器的功能完全像发生器一样，当收到附加了CRC码的数据后，做同样的模2 除法。如果余数是全0，则将CRC码丢弃，接受数据。否则，丢弃收到的数据。r个比特0数据g(x

9、)CRC校验码r+1r余数先发数据位先发数据位后发校验位后发校验位g(x)余数r+1r数据0接收，非接收，非0拒绝拒绝数据发送方发送方接收方接收方 0G(X) 111010100011010 CRC校验码 信息码 CRC冗余校验码CRC码是很有效的差错校验方法。除了正好数据块的比特值是按除数值变化的错误外，循环冗余校验(CRC)将检测出其他所有错误。而且，常用的CRC除数通常有17，或是33个比特，使得不可检测的错误可能降低到几乎近于零。CRC接收电路再配上适当的硬件电路不仅可以检错，而且可以纠错，纠错能力很强特别适合检测突发性错误，在数据通信中得到较广泛的应用。能检测出全部单个错误能检测出全

10、部随机二位错误能检测出全部奇数个错误能检测出全部长度小于k位的突发错误能以1-（1/2）k-1概率检测出长度为（k+1）位的突发性错误例如：g(x)=x4+x3+x2+1，（7,3）码，信息码110产生的CRC码就是：对于g(x)=x4+x3+x2+1的解释：（都是从右往左数）x4就是第五位是1，因为没有x1所以第2位就是0。11101 | 110,0000（设a=11101 ，b=1100000）用b除以a做模2运算得到余数：1001余数是1001，所以CRC码是1001，传输码为：110,1001若信息码字为11100011，生成多项式 G（X）=X5+X4+X+1，则计算出的 CRC 校验码为？1110001100000/110011=10110110*1100