我们知道，实际通信链路都不是理想的，比特在传输过程中可能会产生差错，1可能会变成0，0可能会变成1，这称为比特差错。
那么接收方如何判断数据在传输过程中是否出现了差错呢？我们可以在发送数据后面增加差错检测码来检测。本篇文章来看看数据链路层中差错检测问题。
我们以以太网MAC帧格式为例说明：
我们可以看到帧尾是一个4字节的帧检验序列FCS字段，其作用是让接收方数据链路层检查帧在传输过程中是否出现了误码。
常用的差错检测方法有奇偶校验、CRC循环冗余算法等方法。
PS：FCS是指帧检验序列，就是添加在数据后面的冗余码；CRC或奇偶校验是一种检测算法。注意区分FCS和CRC概念上的区别。
一、奇偶校验
用奇偶校验法算出来的冗余码叫做奇偶校验码，可以用来检测数据传输过程中是否发生错误，是众多校验码中最为简单的一种。
顾名思义，它有两种校验方法：奇校验和偶校验。
奇校验：原始码流+校验位 总共有奇数个1
偶校验：原始码流+校验位 总共有偶数个1
这个算法特别简单，比如双方约定以奇校验为校验方式，那么发送发检测比特流中1的个数，如果数据部分的1个数为偶数个，则校验位要放1，这样1的个数才是奇数个；接收方接收后，判断该帧中比特1的数量，如果为奇数个，那么表示没有误码，如果是偶数个，则产生了误码。
可以看到，这个方法十分简单，但是不可靠，为什么这么说呢？假设约定的是奇校验，即发送发构建的一帧的比特流中1的个数为奇数个。但是不幸的是中间还是出现了比特差错，如果正好是错了两个比特呢？很有可能还是奇数个1，那么接收方就会误判为无误码。这种只有一半概率的校验算法着实让人睡不着觉，因此计算机网络的数据链路层不会采用此检测方法。
二、循环冗余校验CRC
这是一种具有很强检错能力的检错方法，漏检率极低：
-
收发双方约定好一个生成多项式G(x)
-
发送方基于待发送的数据和生成多项式计算出差错检测码（冗余码），将其添加到待传输数据的后面一起传输
-
接收方通过生成多项式来计算收到的数据是否产生了误码
除数是由生成多项式的系数构成，比如生成多项式为：
生成多项式就为：10111，至于后面补充的0，就看多项式最高次幂是多少，比如示例的多项生成式最高次数为4，那么就在数据二进制形式后面补4个0。
此外，算法要求生成多项式必须包含最低次项，常用的生成多项式有：
此外，最重要的就是计算余数的过程，这里采取的是模2除法，下面来好好说说上图是如何计算的。
三、模2除法的计算规则
耐心看，不难！！！！！！！
要说模2除法，先说模2加法和模2减法。
模2加法运算为：1+1=0，0+1=1，0+0=0，无进位，也无借位。可以看到加法过程符合异或运算结果。
模2减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，也无进位，无借位。可以看到减法过程也符合异或运算结果。
模2乘法跟普通的二进制乘法一样：0 * 0 = 0，0 * 1 = 0，1 * 0 = 0，1 * 1 = 1。只是在中间结果的计算上采用的是模2加法来计算。
模2除法则采用的是模2减法运算。可以看到，实际上减法就是异或运算！那么下面对于除法的运算就全部转为异或运算。
回到正题，上图中的计算过程实际上可以对应到如下规则：
-
除数与被除数最高几位（与除数位数相同）做异或，商1。（除数首位必须为1）
-
余数先去掉首位，若此时余数最高位为1，商1，并对以它为除数继续模2除。若最高位为0，则商0，重复步骤2。
-
直到余数位数小于除数位数时，运算结束。
这个规则实际上可以跟上图示例的计算规则对应上，但是可以做下简化：
-
当余数位数与除数位数相同时，才进行异或运算，余数首位是1，商就是1，余数首位是0，商就是0。
-
当已经除了几位后，余数位数小于除数，商0，余数往右补一位，位数仍比除数少，则继续商0，当余数位数和除数位数一样时，商1，进行异或运算，得新的余数，以此至被除数最后一位。
图再贴一遍，方便进行步骤的比对：
重要的点就是：要找到相同位数去异或计算；位数不够则商为0；最后余数位数小于除数位数计算停止；余数就是CRC校验要带上的FCS。
最后，接收方根据生成多项式和数据串去验证是否能除尽，能则说明数据串正确。
四、小小的总结
检错码只能检测出帧在传输过程中出现了差错，但是不能定位错误，因此无法纠正错误。
要想纠正传输中的差错，可以使用冗余信息更多的纠错码进行前向纠错，但纠错码的开销比较大，计算机网络中较少使用。
循环冗余校验CRC有很好的检错能力（漏检率非常低），虽然计算比较复杂，但非常易于用硬件实现，因此被广泛应用于数据链路层。
在计算机网络中通常采用我们后续将要讨论的检错重传方式来纠正传输中的差错，或者仅仅是丢弃检测到差错的帧，这取决于数据链路层向其上层提供的是可靠传输服务（TCP）还是不可靠传输服务（UDP）。
原文始发于微信公众号（幕后哈土奇）：九、数据链路篇-差错检测问题
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/114219.html
