生活资讯
计算机数据链路层三个基本问题(计算机网络-数据链路层二)
2023-04-24 04:00  浏览:43

2.3 差错检测

数据传输过程中会由于噪声或者其他因素而出现差错。差错分为位错帧错两大类。

位错:二进制数字出错,如00000000变成00000001

帧错:包括丢失重复失序三种。如发送编号顺序为1、2、3的三个帧,如果接收方收到的是13,就是发生了丢失,2号帧丢失;如果接收方收到的是1223,就是发生了重复,2号帧重复;如果接收方收到的是132,就是发生了失序,2 、3号帧失序。

为了保证数据传输的可靠性,必须采取一些措施来检测差错。差错控制既可以检测差错然后重传,也可以检测差错后直接纠错。前者使用检测编码,后者使用纠错编码。

注:这里的编码是数据链层的编码,针对的是一组比特。而物理层的编码是针对单个比特,如归零编码、曼彻斯特编码。

2.3.1 检测编码

检测编码有奇偶校验码CRC循环冗余码两种。

2.3.1.1 奇偶校验码

奇偶校验码分为奇校验偶校验。n位的奇偶校验码中有n-1位信息元和1位校验元。在编码时,先看信息元中的“1”的个数是奇数还是偶数,对于奇校验,如果信息元中“1”的个数为奇数,则校验位设置为0,如果为偶数,则校验元设置为1,总之奇校验就是通过设置校验元时校验码中“1”的个数为奇数。而偶校验就是通过设置校验元时校验码中“1”的个数为偶数

接收方收到数据后会检查“1”的个数,对于奇校验,如果“1”的个数为奇数,则认为没有出错,如果为偶数,则判定出错,要求发送方重传。偶校验同理。从工作过程中我们可以发现,如果判定出错,则肯定发生了错误;但是如果判定未出错,却不一定传输正确。

比如传送奇校验码为000000001 ,如果接收方收到的是000000111,此时会判定正确,但实际出现了错误。奇偶校验码只能检测出奇数个比特的错误

2.3.1.2 CRC循环冗余码

CRC循环冗余码比较复杂,用一个例子来说明。比如要发送数据1101 0110 11,首先发送方与接收方会商定一个生成多项式,如10011,生成多项式可以换一种形式G(x)=x4 x 1。事实上G(x)=1*x4 0*x3 0*x2 1*x1 1*x0,,取各项系数就得到了10011,然后确定生成多项式的阶,生成多项式的阶为x的最高次数,此生成多项式x的最高次数为4,故阶为4。接下来在要发送的数据后面加上4(阶数)个0,得到1101 0100 11 0000,然后进行模2除法(相同取0,不同取1,见下图)。

计算机数据链路层三个基本问题(计算机网络-数据链路层二)(1)

最后得到的余数1110即为冗余码,故最终发送的数据为1101 0110 111110。

接收方收到数据后除以生成多项式10011,如果得到的余数为0,则判定没有错误并接收;否则判定未出错并丢弃

值得注意的是,使用CRC循环冗余校验也不一定保证接收就没有出错,只是出错概率低,一般生成多项式越高阶,出错概率越低。

2.3.2 检错编码

检错编码这里介绍海明码。海明码工作流程:

确定校验码位数r→确定校验码和数据的位置→求出校验码的值→检错并纠错

①确定校验码位数:如果数据有m位,设校验码为r位,则校验码一共有2r种取值,减去1种全对的情况,则2r-1种取值方式表示有1位出错,而编码后一共有m r位,故r应满足:

2r-1≥m r(海明不等式)

例如发送数据1100,m=4,代入不等式可得最小的r=3,海明码有m r=7位。

②确定校验码和数据的位置:校验码放在序号为2n(1,2,4,8…)的位置上,按序填上。

计算机数据链路层三个基本问题(计算机网络-数据链路层二)(2)

③求出校验码的值:

计算机数据链路层三个基本问题(计算机网络-数据链路层二)(3)

4号校验码,4对应的二进制为100,则其负责1**的校验,即100、101、110、111,再转换为十进制,也就是4,5,6,7。1、2号校验码同理。

偶校验说明:4对于x4,5对应0,6、7均对应1,则x4取0,这样有偶数(也就是2)个“1”。

④检错并纠错:

假设接收方收到的数据:

计算机数据链路层三个基本问题(计算机网络-数据链路层二)(4)

我们很容易发现5号位出错了,但是接收方并不能直接识别,需要采用一定的方法进行判断。

x4负责的4、5、6、7:0、1、1、1,由于是偶校验,而这里是奇数个1,故判定出错。

x2负责的2、3、6、7:0、0、1、1,偶数个1,判定正确

x1负责的1、3、5、7:1、0、1、1,奇数个1,判定错误

据此可得出数据传输出错。接下来判定出错的位数:

法一:

计算机数据链路层三个基本问题(计算机网络-数据链路层二)(5)

合起来就得到了101,转换为十进制就是5,也就是5号位出错。

法二:

计算机数据链路层三个基本问题(计算机网络-数据链路层二)(6)

先作图,如图所示。最外面三个部分是1、2、4,然后交叉的部分写其和,3=1 2,5=1 4,6=2 4,7=1 2 4。根据前面的判断4、5、6、7和1、3、5、7中有错,取4、5、6、7的圆与1、3、5、7相交的部分,可得到错误在5、7中,又根据2、3、6、7正确,可以排除7,这样就可以确定5号位出错。

,
发表评论
0评