计算机网络——数据链路层-差错检测（奇偶校验、循环冗余校验CRC）

奇偶校验

循环冗余校验CRC

发送方操作

接收方操作

生成多项式

举例-1

举例-2

我们知道，

实际的通信链路都不是理想的，比特在传输过程中可能会产生差错；1可能变成0，而0也可能变成1，这称为比特差错。

如下图所示：

比特流在传输过程中由于受到各种干扰就可能会出现比特差错，或称为误码。

在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率BER（Bit Error Rate）。
使用差错检测码来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一。

例如以太网版本2的MAC帧格式和点对点协议PPP的帧格式，他们帧尾中都包含了帧检验序列FCS字段，其作用就是让接收方的数据链路层检查帧在传输过程中是否产生了误码。

奇偶校验

接下来我们介绍基偶校验这种比较简单的检测方法。

在待发送的数据后面添加1位奇偶校验位，使整个数据（包括所添加的校验位在内）中“1”的个数为奇数（奇校验）或偶数（偶校验）。

举例说明：

采用奇偶校验，如果有奇数个位发生误码，则奇偶性会发生变化，也就是奇变偶或者是偶变奇，这样就可以检查出误码；
而如果有偶数个位发生误码，则奇偶性不会发生变化，不能检查出误码（漏检）；

这是因为：每个误码对奇偶性的影响相互抵消了，这样就无法检查出误码，也称为漏检。

由于奇偶校验的漏检率比较高，因此计算机网络的数据链路层一般不会采用这种检测方法。

循环冗余校验CRC

CRC（Cyclic Redundancy Check）

接下来我们介绍循环冗余校验CRC，这是一种具有很强检错能力的检测方法，漏检率极低。

收发双方约定好一个生成多项式G（x）；
发送方基于待发送的数据和生成多项式计算出差错检测码，称为冗余码，并将其添加到待传输数据的后面一起传输；
接收方通过生成多项式来计算收到的数据是否产生了误码。

发送方操作

使用除法（模二除法）来计算冗余码，

待发送的数据作为被除数的一部分，后面添加生成多项式最高次数个0以构成被除数
生成多项式各项系数构成的比特串作为除数
进行模二除法得到商和余数
余数就是所计算出的冗余码，将其添加到待发送数据的后面一起发送。

需要注意的是，冗余码的长度与生成多项式最高次数相同，而商仅作为标记防止计算过程中对错位。

对模二除法不太了解的同学可以前往：模2除法——用非常直观的例子解释_模二除法-CSDN博客

——作者：

猫咪钓鱼

接收方操作

被除数就是接收到的数据，除数仍是生成多项式各项系数构成的比特串，进行模二除法得到商和余数，如果余数为0，可判定传输过程没有产生误码，否则可判定传输过程产生了误码。

生成多项式

下面我们对生成多项式举例说明，这是一个生成多项式：

这是该生成多项式的完整形式：

生成多项式各项系数构成的比特串就是我们做除法时所用到的除数

这是常用的生成多项式：

使用这些生成多项式进行CRC校验可以达到较好的检测效果，也就是漏检率比较低。

需要注意的是，CRC算法要求生成多项式必须包含最低次项。

举例-1

待发送的信息为101001，生成多项式为 $G(x)=x^3+x^2+1$ ，计算余数。

该题给定了待发送的信息和一个生成多项式，要求计算余数：

第一步构造被除数。在待发送信息后面添加生成多项式最高次数个0，就可以构造出被除数。

这是待发送信息：

这是添加生成多项式最高次数个0：

第二步构造除数。生成多项式各项系数构成的比特串就是除数：

第三步做模二除法，得到余数为1：

第四步检查余数。余数的位数应与生成多项式最高次数相同，如果位数不够，则在余数前补0来凑足位数，将余数添加到待发送信息的后面就可以发送了：

举例-2

再来做一个练习

接收到的信息为101101001，生成多项式为 $G(x)=x^3+x^2+1$ ，判断传输是否误码？

该题给定了接收方收到的信息和一个生成多项式，要求判断传输过程是否产生了误码：

需要说明的是，

检错码只能检测出帧在传输过程中出现了差错，但并不能定位错误，因此无法纠正错误。
要想纠正传输中的差错，可以使用冗余信息更多的纠错码进行前向纠错，但纠错码的开销比较大，在计算机网络中较少使用。
循环冗余校验CRC有很好的检错能力（漏检率非常低），虽然计算比较复杂，但非常易于用硬件来实现，因此被广泛应用于计算机网络的数据链路层。
在计算机网络中通常采用我们后续课程中将要讨论的检错重传方式来纠正传输中的差错，或者仅仅是丢弃检测到差错的帧，这取决于数据链路层向其上层提供的是可靠传输服务还是不可靠传输服务。