CRC算法的求解

循环冗余码校验(Cyclical Redundancy Check, CRC)是一种利用除法及余数的原理进行错误侦测的校验方式。发送装置计算出CRC值并与数据一同发送给接收装置。接收装置对收到的数据重新计算CRC并与收到的CRC比较，若不同则说明数据通讯出现错误。CRC有不同的标准，如CRC-12、CRC-16、CRC-CCITT及CRC-32等。

CRC-12用于6位字符串，CRC-16及CRC-CCITT用于8位字符。CRC-16为美国采用，CRC-CCITT为欧洲国家所用。CRC-32大都被用于点对点同步传输。本文以下以最常用的CRC-16为例解释其生成过程。

CRC-16由两个字节组成。开始时CRC寄存器的每一位均预置为1。将数据的第一个8位字符与16位CRC寄存器的低8位异或，结果存入CRC寄存器。然后，CRC寄存器向右移一位，MSB补零，检查LSB。若LSB为0，则重复移位步骤；若为1，则CRC寄存器与预定义的多项式码异或。如此重复8次，完成第一个8位数据的处理。接下来，重复第2至第5步直到所有数据处理完成。最终CRC寄存器内的值即为CRC值。

CRC循环冗余校验标准多项式包括：CRC(16位) = X16 X15 X2 1，CRC(CCITT) = X16 X12 X5 1，CRC(32位) = X32 X26 X23 X16 X12 X11 X10 X8 X7 X5 X4 X2 X 1。以CRC(16位)多项式为例，其对应校验二进制列为1 1000 0000 0000 0101。注意，所列出的标准校验多项式都含有(X 1)的多项式因子，各多项式的系数为二进制数，四则运算遵循对二取模的运算规则，即参与运算的两个二进制数各位之间凡涉及加减运算时进行XOR异或运算。