计算机组成原理：循环冗余校验码及应用

循环冗余校验码（简称CRC码）广泛应用在计算机网络及通信中。这里只作定性介绍。

要传送的信息是一串k位二进制序列，被一个预先选择的r+1位二进制串（称为“生成多项式”）相除，相除后得到的r位余数就是校验位，把它拼接到原k位有效信息后面即形成k+r位的循环冗余校验码——CRC码。CRC码具备这样的特征：CRC码能被“生成多项式”整除，所以当CRC码到达接收方时，接收方用同样的生成多项式相除，如果正好除尽，表示无信息差错，接收方去掉CRC码后面的r位校验，收下k位有效信息；当不能除尽时，说明有信息在传送过程中出错了，一般要求重新传送一次或立即纠错。

传送信息时生成CRC码以及接收时对CRC码校验都要与“生成多项式”相除，这里的除法是“模2运算”，即进行加、减运算时不考虑进位和借位。做模2除法时，上商的原则是当部分余数首位为1时商取1，反之商取0，然后按模2减；求部分余数时，这个余数去掉一位最高位。当被除数逐位除完时，最后余数的位数比除数少一位，该余数就是校验位，它拼接在有效信息后面组成CRC码。

例2-12：设传送信息是二进制串100110，选择的生成多项式为1011，计算校验位并写出CRC码。

生成多项式是4位=r+1，所以校验位r=3。先做模2除法，注意被除数先加r个0。(www.xing528.com)

校验位是011，传送的CRC码是100110 011。

接收方收到的是带有校验位的CRC码，把CRC码除以同一个生成多项式，如果余数为0，则信息无错误。可以用例2-12验证，CRC码是100110 011，生成多项式仍是1011。

如果某一位出错，则余数不为0。此时继续模2除法，余数值将出现反复循环，请读者自行试做。这就是“循环码”名称的由来。

应该注意，并不是任何一个r+1位的二进制串都可以作生成多项式用，它应满足，当任何一位发生传送错误时都能使余数不为0，并且不同位发生错误时应当使余数也不同，这样不但能检错，而且能推断是哪一位出错，从而有利于准确地纠错。常用的生成多项式长13位、17位或33位。下面是几种检错率很高、被广泛使用的生成多项式：11000000000000101，10001000001000001。