330.3-3 差错检测

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

如图所示，比特流在传输过程中，‍‍由于受到各种干扰，就可能会出现比特差错或称为误码。‍‍在一段时间内‍‍传输错误的比特占所传输比特总数的比率成为误码率 BER。大家可以通过动画演示，‍‍清楚的看到比特在传输过程中出现了错误，但是接收方的数据链路层‍‍又是通过怎样的方法才能知道？

​​

使用差错检测码‍‍来检测数据在传输过程中是否产生了比特差错，是数据链路层所要解决的重要问题之一

例如。‍这是以太网版本 2 的 MAC 帧格式，其帧尾中包含了一个长度为 4 字节的帧检验序列 FCS 字段，‍‍其作用就是让接收方的数据链路层检查帧在传输过程中是否产生了误码，‍‍这是点对点协议 PPP 的帧格式，其帧尾中也包含了一个长度为两字节的帧检验序列，‍‍FCS 字段，其作用也是让接收方的数据链路层检查正在传输过程中是否产生了误码。

​​ ‍

奇偶校验

接下来‍‍我们介绍奇偶校验这种比较简单的检测方法，在待发送的数据后面添加一位奇偶校验位，‍‍使整个数据包括所添加的校验位在内中的 1 的个数为基数这称为基教验，或为偶数这称为偶校验。‍‍

我们来举例说明，这是待发送的数据，假设收发双方约定采用基校验，‍‍那么在数据后面添加的校验位应该为比特 1，使得比特一的总数为基数，‍‍假设传输过程中产生了一位误码，我们用红色表示，接收方对收到的比特流进行基校验，‍‍发现比特 1 的总数为偶数而不是基数，就知道传输过程中发生了误码。‍‍

​​ ‍

• 换句话说，‍‍采用基校验，若比特 1 的数量的基性改变，可以检查出错误，但是‍‍如果传输过程中产生了两位误码，接收方对收到的比特流进行机校验，‍‍发现比特 1 的总数为基数，就误认为传输过程中没有发生误码。换句话说，采用基校验，‍‍若比特 1 的数量的奇性不改变，是无法检查出错误的。‍‍
• 假设收发双方约定采用偶校验，‍‍那么在数据后面添加的校验位应该为比特 0，使得比特 1 的总数为偶数，‍‍假设传输过程中产生了 1 位误码，接收方对收到的比特流进行偶校验，‍‍发现比特 1 的总数为基数而不是偶数，就知道传输过程中发生了误码。换句话说，采用偶校验‍‍若比特 1 的数量的偶性改变，可以检查出错误，但是如果传输过程中产生了两位误码，接收方对收到的比特流进行偶校验，发现比特 1 的总数为偶数，‍‍就误认为传输过程中没有发生误码。换句话说，采用偶校验，若比特 1 的数量的偶性不改变，‍‍是无法检查出错误的。‍‍

通过本例可以看出采用奇偶校验，如果有奇数个位发生误码，则奇偶性会发生变化，也就是奇变偶者是偶变奇，这样就可以检查出误码。而如果有偶数各位发生误码，则奇偶性不会发生变化，‍‍这是因为每个误码对奇偶性的影响相互抵消了，这样就要无法检查出误码，也称为漏检。‍‍由于奇偶校验的漏检率比较高，因此计算机网络的数据链路层一般不会采用这种检测方法。‍‍ ‍

循环冗余校验 CRC

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

• 收发双方约定好一个生成多项式
• 发送方基于代发送的数据和生成多项式计算出差错检测码，称为冗余码，‍‍并将其添加到带传输数据的后面一起传输
• 接收方通过生成多项式来计算‍‍收到的数据是否产生了误码 ‍ 我们来看发送方的操作，是用除法来计算冗余吗，待发送的数据作为被除数的一部分，后面添加生成多项式最高次数个 0，已构成被除数，‍‍生成多项式各项系数构成的比特串作为除数进行除法，得到商‍‍和余数，余数就是所计算出的冗余码，将其添加到待发送数据的后面一起发送。‍‍需要注意的是‍‍冗余码的长度与生成多项式最高次数相同，而商仅作为标记，防止计算过程中对错位。‍‍

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

​​ ‍

下面‍‍我们对生成多项式举例说明，这是一个生成多项式，这是该生成多项式的完整形式，‍‍生成多项式各项系数构成的比特串，就是我们做除法时所用到的除数，‍‍这是常用的生成多项式，使用这些生成多项式进行 CRC 校验，可以达到较好的检测效果，‍‍也就是漏检率比较低。需要注意的是 CRC，算法要求生成多项式，必须包含最低次项。‍‍

​​ ‍

接下来‍‍我们来做一个练习，该题给定了待发送的信息和一个生成多项式，要求计算余数。‍‍我们使用之前介绍的除法来计算。

• 第一步，构造被除数。‍‍在待发送信息后面添加生成多项式最高次数个 0，就可以构造出被除数。这是待发送信息，‍‍这是添加生成多项式最高次数个 0。
• 第二步，构造除数，‍‍生成多项式各项系数构成的比特串就是除数。
• 第三步做除法，‍‍在该位做标记，将除数移过来，然后进行异或运算，将该位落下来，‍‍在该位做标记，一表示够除，将除数移过来，然后进行异或运算，‍‍将单位落下来，在单位做标记，零表示不够除，再将单位落下来，在单位做标记，‍‍一表示够除，将除数移过来，然后进行一会运算，‍‍将单位落下来，在该位做标记，零表示不够除，再将单位落下来在单位做标记，‍‍一表示够除，将除数移过来，然后进行异或运算，得到余数为一。‍‍
• 第四步，‍‍检查余数余数的位数应与生成多项式最高次数相同，如果位数不够，‍‍则在余数前补零来凑足位数，将余数添加到待发送信息的后面

​​

就可以发送了。‍‍我们再来做一个练习。该题给定了接收方收到的信息和一个生成多项式，‍‍要求判断传输过程是否产生了误码。我们给出以下步骤，‍‍请同学们参照之前的除法过程计算余数，然后根据余数是否为 0，‍‍来判断传输过程是否产生了误码

​​

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