循环冗余校验in计算机网络技术

2023-10-19 理论教育版权反馈

【摘要】：循环冗余校验有严密的数学结构，本节仅介绍相关概念与冗余码的产生、使用过程。循环冗余码的校验能力与生成多项式有关，若能针对传输信息的差错模式设计生成多项式，就会得到较强的检测差错的能力。CRC-32 的检错能力大有提高，它能检测出所有长度不大于32 位的突发差错，对33 位和大于33 位突发差错的检错能力可分别达到99.999 999 95%和99.999 999 98%。③将余数作为校验码放入信息位左移后的空间。

循环冗余码（Cyclical Redundancy Check，CRC）是较为复杂的一种差错检测方法，可生成一种高性能的检错、纠错码，但实际应用中常用这种方法来检错。由于它检错能力强、实现简单，因而在数据通信中得到了广泛的应用。循环冗余校验有严密的数学结构，本节仅介绍相关概念与冗余码的产生、使用过程。

在CRC 中，都需要用到多项式这个概念。一个二进制数可以用一个多项式来表示。例如，“1001”表示成多项式为x3 +1。这里，x 不表示未知数这个概念，仅作为一种二进制数的表达方式。

在CRC 编码中，码字由K 位信息码和R 位的校验码两部分组成。K 位信息码可以看成一个多项式C（x）。发送方和接收方共同约定一个生成多项式G（x）。发送方将信息码的多项式除以生成多项式G（x），将得到的余数作为校验码；接收方将收到的信息除以生成多项式G（x），如果余数为“0”，则认为数据在传输过程中没有错误，如果余数不为“0”，则存在错误。同时，余数也可作为确定错误位置的依据。

生成多项式G（x）并非任意制定，必须具备一定的条件。例如，G（x）的首位和最后一位的系数必须为“1”。循环冗余码的校验能力与生成多项式有关，若能针对传输信息的差错模式设计生成多项式，就会得到较强的检测差错的能力。目前，人们已经设计了许多生成多项式。最常见的有：

其中，CRC-16 和CRC-CCITT 用于8 位字符同步系统，它们能够检测出全部的1 位、2 位和奇数位的差错，所有长度不大于16 位的突发差错。CRC-32 的检错能力大有提高，它能检测出所有长度不大于32 位的突发差错，对33 位和大于33 位突发差错的检错能力可分别达到99.999 999 95%和99.999 999 98%。

校验码的生成步骤可描述如下：

①将K 位数据C（x）左移R 位，得到移位后的多项式C（x）×xR。(www.chuimin.cn)

②将移位后的信息多项式除以生成多项式，得到R 位冗余多项式。

③将余数作为校验码放入信息位左移后的空间。

若将上述过程用多项式等价的二进制数来表示，则校验码的产生过程即为被除数与除数做二进制除法的运算求余的过程。

例如，信息位为10100001，生成多项式G（x）=x3 +x2 +1，则校验码的生成过程如下：

产生的余数为010，发送端发送出去的码字即为10100001010。

【练一练】设待编码的信息C（x）=10100110，利用生成多项式G（x）=x5 +x3 +1 进行差错检测，则生成的冗余码是什么？发送端发送出去的码字是什么？