循环冗余校验码_循环冗余码计算_crc校验码计算

2.9.3 循环冗余校验码

所谓循环码是这样一组代码，其中任一有效码字经过循环移位后得到的码字仍然是有效码字，不论是右移或左移，也不论移多少位。例如，若（an-1 an-2 …a1 a0）是有效码字，则（an-2 an-3…a0 an-1），（an-3 an-4 …an-1 an-2）等都是有效码字。循环冗余校验码（Cyclic Redundancy Check，CRC）是一种循环码，它有很强的检错能力，而且容易用硬件实现，在局域网中有广泛应用。

首先我们介绍CRC怎样实现，然后再对它进行一些数学分析，最后说明CRC的检错能力。CRC可以用图2-31的移位寄存器实现。移位寄存器由k位组成，还有几个异或门和一条反馈回路。图2-31所示的移位寄存器可以按 CCITT-CRC标准生成16位的校验和。寄存器被初始化为零，数据字从右向左逐位输入。当一位从最左边移出寄存器时就通过反馈回路进入异或门和后续进来的位以及左移的位进行异或运算。循环冗余校验码当所有m位数据从右边输入完后再输入k个零（本例中k=16）。最后，当这一过程结束时，移位寄存器中就形成了校验和。k位的校验和随在数据位后边发送，接收端可以按同样的过程计算校验和并与接收到的校验和比较，以检测传输中的差错。

以上描述的计算校验和方法可以用一种特殊的多项式除法进行分析。m个数据位可以看作m-1阶多项式的系数。例如，数据码字00101011可以组成的多项式是x5+x3+x+1。图2-31中表示的反馈回路可表示成另外一个多项式x16+x12+x5+1，这就是所谓的生成多项式。所有的运算都按模2进行。即

显然，在这种代数系统中，加法和减法一样，都是异或运算。用x乘一个多项式等于把多项式的系数左移一位。可以看出按图2-31的反馈回路把一个向左移出寄存器的数据位反馈回去与寄存器中的数据进行异或运算，等同于在数据多项式上加上生成多项式，因而也等同于从数据多项式中减去生成多项式。我们以上给出的例子，对应于下面的长除法：

得到的校验和是9509H。我们看到，移位寄存器中的过程和以上长除法在原理上是相同的，因而可以用多项式理论来分析CRC代码。这就使得这种检错码有了严格的数学基础。

我们把数据码字形成的多项式叫数据多项式D(x)，按照一定的要求可给出生成多项式G(x)。用G(x)除Xk D(x)可得到商多项式Q(x)和余多项式R(x)，实际传送的码字多项式是

由于我们使用了模2算术，+R(x)=-R(x)，于是接收端对F(x)计算的校验和应为0。循环冗余校验码如果有差错，则接收到的码字多项式包含某些出错位E，可表示成

F(x)可以被G(x)整除，如果H(x)不能被G(x)整除，则说明E(x)≠0，即有错误出现；然而，若E(x)也能被G(x)整除，则有差错而检测不到。

数学分析表明，G(x)应该有某些简单的特性，才能检测出各种错误。例如，若G(x)包含的项数大于1，则可以检测单个错，若G(x)含有因子x＋1，则可检测出所有奇数个错。最后，也是最重要的结论是，具有r个校验位的多项式能检测出所有长度小于等于r的突发性差错。

为了能对不同场合下的各种错误模式进行校验，已经研究出了几种CRC生成多项式的国际标准；

其中CRC-32用在许多局域网中。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-37741-1.html