上篇文章讲解了数据链路层_检错与纠错——海明码，海明码（Hamming Code）是一个可以有多个校验位，具有检测并纠正一位错误代码的纠错码，所以它也仅用于信道特性比较好的环境中，如以太局域网中，因为如果信道特性不好的情况下，出现的错误通常不是一位。

纠错码广泛用于无线通信中，因为无线线路比有线线路噪声更多、更容易出错，有线线路上的错误率非常低，所以对于偶然的错误，利用错误检测和重传机制更有效。数据链路层广泛使用循环冗余校验码（Cyclical Redundancy Check，CRC）进行错误检测。CRC编码又称为多项式编码（polynomial code）。CRC的基本思想是把位串看成系数为0或1的多项式，一个k位的帧看成是一个（k-1）次多项式的系数列表，该多项式有k项，从x^k-1到x⁰。这样的多项式就是（k-1）阶多项式，该多项式行为A₁x^k-1+ A₂x^k-2+…+ A_n-2x¹⁺ A_n-1x⁰。例如，1101有4位，可以代表一个三阶多项式，系数为1、1、0、1，即x³+ x²+1。

使用CRC编码，需要先商定一个生成多项式（Generator Polynomial）G(x)。生成多项式的最高位和最低位必须是1。假设原始信息有m位，则对应多项式M(x)。生成校验码思想就是在原始信息位后追加若干校验位，使得追加的信息能被G(x)整除。接收方接收到带校验位的信息，然后用G(x)整除。余数为0，则没有错误；反之则发生错误。

1、生成CRC校验码

下面讲解CRC校验码生成的过程。假设原始信息串为10110011，CRC的生成多项式为G(x)=X⁴+X³+1，求CRC校验码。

（1）原始信息后“添0”

假设生成多项式G(x)的阶为r，则再原始信息位后添加r个0，新生成的信息串共m+r位，对应多项式设定为x^rM(x)。

G(x)=X⁴+X³+1的阶为4，即11001，则在原始信息10110011后添加4个0，新信息串为10110011 0000。

（2）使用生成多项式除

利用模2除法，用对应的G(x)位去除串x^rM(x)对应的位串，得到长度为r位的余数。除法过程如下图。

得到余数0100。

注意：余数不足r位，则余数左边用若干个0补齐。如求得余数为二进制11，r=4，则补两个0得到0011。

（3）将余数添加到原始信息后

上面原始信息为10110011，添加余数0100后，结果为10110011 0100。

2、CRC校验

CRC校验过程与生成过程类似，接收方接收了带校验和的帧后，用多项式G(x)来除。余数为0，则表示信息无错；否则要求发送方进行重传。

注意：收发信息双方需要使用相同的生成多项式。

3、常见的CRC生成多项式

CRC算法不能保证每一个经过CRC验算的帧都绝对正确，其检错率与生成多项式有很大的关系，因此在实际的CRC算法中，通常选择一些国际机构推荐的CRC生成多项式。

不同的协议多项式可能不一样，事前约定，接收方当然就知道。

CRC-16=x¹⁶+x¹⁵+x¹²+1。该多项式用于FR、X.25、HDLC、PPP中，用于校验除帧标志位外的全帧。

CRC-32=x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1。该多项式用于校验以太网（IEEE 802.3）帧（不含前导和帧起始符）、令牌总线（IEEE 802.4）帧（不含前导和帧起始符）、令牌环（IEEE 802.5）帧（从帧控制字段到LLC层数据）、FDDI帧（从帧控制字段到INFO）、ATM全帧和PPP除帧标志位外的全帧。

最后，下面大家做一个练习，假设CRC生成多项式为G(x)=X⁵+X⁴+X+1，要发送的二进制序列为100101110，求CRC校验码是多少？