《计算机网络课程设计（第2版）》——3.5节相关扩展

3.5 相关扩展

除了上面介绍的方法之外，还有其他一些算法可以完成crc校验。例如，多项式除法可用除法电路来实现。除法电路的主体由一组移位寄存器和模2加法器（异或单元）组成。以crc-itu为例，它由16级移位寄存器和3个加法器组成，图3-5给出了除法电路实现crc的示意图（编码/解码共用）。编码、解码前将各寄存器初始化为“1”，信息位按照时钟周期依次移入。当信息位全部输入后，从寄存器组输出crc结果。

比特型算法

上面的crc-itu除法电路可以用软件来模拟。定义一个寄存器组，初始化为全1。依照电路图，每输入一个信息位，相当于一个时钟脉冲到来，从高到低依次移位。移位前信息位与bit0相加产生临时位，其中bit15移入临时位，bit10、bit3还要加上临时位。当全部信息位输入完成后，从寄存器组取出它们的值，这就是crc码。

该算法的代码如下：

字节型算法

比特型算法逐位进行运算，效率比较低，不适用于高速通信的场合。数字通信系统（遵循各种通信标准）一般是对一帧数据进行crc校验，而字节是帧的基本单位。最常用的是一种按字节查表的快速算法。该算法基于这样一个事实：计算本字节后的crc码，等于上一字节crc右移8位和本字节之和再与上一字节余式crc码的低8位左移8位相加后所求得的crc码。如果我们把8位二进制序列数的crc(共256个)全部计算出来，放在一个表里，那么编码时只要从表中查找对应的值进行处理即可。

crc-itu的算法如下：

1) 寄存器组初始化为全1（0xffff）。

2) 寄存器组向右移动一个字节。

3) 刚移出的那个字节与数据字节进行异或运算，得出一个指向值表的索引。

4) 将索引所指的表值与寄存器组做异或运算。

5) 数据指针加1，如果数据没有全部处理完，则重复步骤2。

6) 寄存器组取反，得到crc，附加在数据之后。

crc-itu的验证算法如下：

5) 数据指针加1，如果数据没有全部处理完，则重复步骤2（数据包括crc的两个字节）。

6) 判断寄存器组的值是否等于“magic value”(0xf0b8)，若相等则通过，否则失败。

下面是通用的crc-itu查找表以及计算和验证crc的c语言程序：