循环冗余校验码

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+

4、1 CRC-16=x16+x15+x2+1 CRC-12=x12+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)=校验码

5、非常简单，要说明的：模2除就是在除的过程 中用模2加，模2加实际上就是我们熟悉的异或 运算，就是加法不考虑进位，公式是： 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) 。 由此除法产生的余数就是循环冗余码 校验码。

6、 第三步：求CRC循环冗余校验码 (K+r)被除数+r(余数) 如果余数位数小于r，最左的缺省位数为0。 如果余数为0,则r=0。 生成多项式应满足以下原则 a、生成多项式的最高位和最低位必须为1。 b、当被传送信息（CRC码）任何一位发生错误 时，被生成多项式做模2除后应该使余数不为0。 c、不同位发生错误时，应该使余数不同。 d、对余数继续做模2除，应使余数循环。 任何一个二进制数序列可以和一个只含 有0和1两个系数的代数多项式建立起一一 对应的关系。因此，用来求CRC码的那个 除数通常用多项式来表示。原因如下： 代数多项式很短 可以通过多项式来进行概念的数学证明。 任何一个n位的二进制数

7、都可以用一个n-1 次的多 项式来表示,这种多项式叫码多项式（又叫信息多项 式） 。 码多项式与二进制序列之间的一一对应关系： （an-1 an-2a1a0）N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0 码多项式 以n=3位二进制数为例 二进制数 对应多项式 000 001 010 011 100 101 111 0 1 x x+1 x2 x2+1 x2+ x+1 n1011011 x6+x4+x3+x+1 nx5+x4+x2+x 110110 码多项式运算法则: 二进制码多项式的加减运算为模2加运算， 即两个码多项式相加时，对应项系数进行模 2加减。 乘除运算与普

8、通多项式类似； 模2加减：即各位做不带进位、借位的按 位加减。这种加减运算实际上就是逻辑 上的异或运算。即加法和减法等价。 码多项式码多项式 生成多项式G(x): 求CRC码时所用的“除数”所对应的多项式 叫生成多项式。 在串行通信中通常使用下列三种生成多 项式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 码多项式码多项式 循环

9、冗余码生成器采用模2除法。下图显 示了这一过程。 CRC校验器的功能完全像发生器一样，当 收到附加了CRC码的数据后，做同样的模 2 除法。如果余数是全0，则将CRC码丢 弃，接受数据。否则，丢弃收到的数据。 r个比特0数据 g(x) CRC校验码 r+1 r 余数 先发数据位先发数据位 后发校验位后发校验位 g(x) 余数 r+1 r 数据 0接收，非接收，非0拒绝拒绝 数据 发送方发送方 接收方接收方 0 G(X) 111010100011010 CRC校验码 信息码 CRC冗余校验码 CRC码是很有效的差错校验方法。除了正好 数据块的比特值是按除数值变化的错误外， 循环冗余校验(CRC)

10、将检测出其他所有错误。 而且，常用的CRC除数通常有17，或是33个 比特，使得不可检测的错误可能降低到几乎 近于零。 CRC接收电路再配上适当的硬件电路不仅可 以检错，而且可以纠错，纠错能力很强特别 适合检测突发性错误，在数据通信中得到较 广泛的应用。 能检测出全部单个错误 能检测出全部随机二位错误 能检测出全部奇数个错误 能检测出全部长度小于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*1