首页 > 其他分享 >【计算机网络】数据链路层——差错控制

【计算机网络】数据链路层——差错控制

时间:2024-03-01 22:11:27浏览次数:32  
标签:编码 比特 差错控制 校验 校验码 计算机网络 差错 码距 链路层

差错控制(检错)

差错从何而来?

概括来说,传输中的差错都是由于噪声引起的。

全局性

由于线路本身电气特性所产生的随机噪声(热噪声),是信道固有的,随机存在的。

解决办法:提高信噪比来减少或避免干扰。(对传感器下手)

局部性

外界特定的短暂原因所造成的冲击噪声,是产生差错的主要原因。

解决办法:通常利用编码技术来解决。

差错种类

image-20240228224422423

image-20240228224450080

差错控制使用的方法

image-20240228224729882

数据链路层编码和物理层的数据编码与调制不同。

物理层编码针对的是单个比特,解决传输过程中比特的同步等问题,如曼彻斯特编码。

而数据链路层的编码针对的是一组比特,它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。

冗余编码

在数据发送之前,先按某种关系附加上一定的冗余位,构成一个符合某一规则的码字后再发送。

当要发送的有效数据变化时,相应的冗余位也随之变化,使码字遵从不变的规则。

接收端根据收到码字是否仍符合原规则,从而判断是否出错

奇偶校验码

image-20240228224917950

采用奇校验,就是在原先的编码后面(或者前面)加一个1或者0,使得1的个数是奇数

采用偶校验,就是在原先的编码后面(或者前面)加一个1或者0,使得1的个数是偶数

不能保证完全检测,因为有可能

如果一个字符s的ASC11编码从低到高依次为1100101,采用奇校验,在下述收到的传输后字符中,哪种错误不能检测?

A. 11000011 B . 11001010 C. 11001100 D.11010011

在原码1100101 后面 加1 得 11001011,这下是奇数了

然后发现ABC,都是4个1,是偶数,肯定不对。

但是D,也是奇数!其实是错了,但是!!!!!检测不到!!!

奇偶校验码特点:只能检查出奇数个比特错误,检错能力为50%。

CRC循环冗余编码

一图流:

image-20240228225657807

1、准备待传有效数据,然后将数据分为等长的组。

2、每个组都加上冗余码(r位FCS)构成帧再发送

  • 如何得到r位FCS

​ 先在一组数据后面加上r位的0,假设生成多项式G(x)的阶为r,则加r个0。

​ 以生成多项式(模二AKA异或)

​ 得到一个商和余数,这个余数就是r位FCS

image-20240229140916423

3、接收方检验:d+r位数据,除以生成多项式

4、余数为0则为正确接受,余数不为0则舍弃

要发送的数据是1101 0110 11,采用CRC校验,生成多项式是10011,那么最终发送的数据应该是?

首先

计算冗余码

  • 加0 。生成多项式是四阶的,加四个零,得到11010110110000
  • 模二除法。

就是先写个1,然后异或下来,同0异1。结果首位0不写,向后补位。直到所有的都除出来

image-20240229141224683

除到这个时候,只剩4位了,就不用除了

1110就叫做4位FCS

然后把FCS冗余码加到后面

于是最终要发送的序列就是1101 0110 11 1110

接收端检错过程

把收到的每一个帧都除以同样的除数(生成多项式,这里是10011),然后检查得到的余数R。

1.余数为0,判定这个帧没有差错,接受。

2.余数为不为0,判定这个帧有差错(无法确定到位),丢弃。

FCS的生成以及接收端CRC检验都是由硬件实现,处理很迅速,因此不会延误数据的传输。

无差错&可靠传输的区别

在数据链路层仅仅使用循环冗余检验CRC差错检测技术,只能做到对帧的无差错接收,即“凡是接收端数据链路层接受的帧,我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。

接收端丢弃的帧虽然曾收到了,但是最终还是因为有差错被丢弃。“凡是接收端数据链路层接收的帧均无差错”。

“可靠传输” :数据链路层发送端发送什么,接收端就收到什么。

链路层使用CRC检验,能够实现无比特差错的传输,但这还不是可靠传输。

纠错编码——海明码

之前只是知道有错,但是不知道在哪

需要找到位置并且纠正错误。(可以发现双比特错,但是只能纠正单比特错。)

image-20240229155046994

海明距离 (海明距、码距)

两个合法编码(码字)的对应比特取值不同的比特数称为这两个码字的海明距离(码距),

一个有效编码集中,任意两个合法编码(码字)的海明距离的最小值称为该编码集的海明距离(码距)。

image-20240229155221952

在上图中,编码集的码距为1,因为所有的编码的海明距离都是1(001和010,100和101)

码距为1的情况下,无法检查差错?

求得码距的方法:可以肉眼观察,也可以做异或,。例如0000和1001做异或结果1001,有几个1,码距就是多少

image-20240229155553995

在这套编码集中,如果出现了差错,那么是可以检测到的,因为码距出现了减小

码距设置依据:

码距为n,可以检测出n-1位的比特错。

  • 想要检查n位比特错,就要设置码距为n+1

  • 想要纠正n为比特错,就要设置码距为2n+1

纠错过程

1、确定校验码位数r(海明不等式)

使用穷举法来求得r。m+r便得到海明码。

要发送的数据是1100

数据的位数m=4,满足不等式的最小r穷举为3。因为不可能是2!

然后推得D=1100的海明码应该有m+r = 4+3 = 7位

其中原数据4位,校验码3位。

2、确定校验码的位置

校验码放在序号为2^n的位置,数据按序填上。

image-20240229160306359

其中2^0位置是校验码x1, 2^1位置是校验码x2, 2^2位置是校验码x3,

3、求出校验码的值(分组偶校验求值)

  • 在刚才的表格上面把序号的二进制写出来:

image-20240229160438722

​ 此时校验码4,2,1所在的位置是100,010,001

​ 发现特点:image-20240229160605963

​ 满足1xx的数有:111,110,101,100;

​ 于是就说x4负责4,5,6,7的校验。如此类推,

​ 2号校验码负责2, 3, 6, 7的校验

​ 1号校验码负责1, 3,5, 7的校验

  • 刚才就相当于完成了一次分组。

  • 对这些分组依次采用偶校验。

​ x4分组:4567,所在的值是110x。偶校验要求1出现偶数次,那么x就是0。于是x4 = 0

​ x2分组:2367,所在的值是x011。偶校验要求1出现偶数次,那么x就是0。于是x3 = 0

​ x1分组:1357,所在的值是x001。偶校验要求1出现偶数次,那么x就是1,。于是x1 = 1

至此得到完整的海明码

image-20240229161050967

4、检错和纠错

若接收方收到的数据是:1 1 1 0 0 0 1,检错类似奇偶校验。

4号校验码负责4567的校验,0111,奇,不行

2号校验码负责2367的校验,0011,偶

1号校验码负责1357的校验。1011,奇,不行

检查出错的位置

  • 法一:用维恩图

image-20240229161426117

​ 4567错,1357错。错的一定是5或者7

​ 但是2367又没错,所以7不是错的。错的是5!!!!

  • 法二:矩阵

首先将

image-20240229161642964

提取成增广矩阵的形式:

image-20240229161701670

然后用偶校验方法,让每一行满足1出现偶数次。

解得

image-20240229161800528

然后将其转置

image-20240229161821761

读取第二行的二进制,101,是5。所以是第五位出错。

总结

image-20240229161922779

标签:编码,比特,差错控制,校验,校验码,计算机网络,差错,码距,链路层
From: https://www.cnblogs.com/nekodream/p/18048070

相关文章

  • 【计算机网络】物理层-编码与调制
    基带信号&宽带信号信道:信号的传输媒介。一般用来表示向某一个方向传送信息的介质,因此一条通信线路往往包含一条发送信道和一条接收信道。基带信号:将数字信号1和0直接用两种不同的电压表示,再送到数字信道上去传输(基带传输)。来自信源的信号,像计算机输出的代表各种......
  • 【计算机网络】物理层传输介质&设备.
    物理层传输介质传输介质也称传输媒体/传输媒介,它就是数据传输系统中在发送设备和接收设备之间的物理通路。传输媒体并不是物理层。传输媒体在物理层的下面,因为物理层是体系结构的第一层,因此有时称传输媒体为0层。在传输媒体中传输的是信号,但传输媒体并不知道所传输的信号代表什......
  • 【计算机网络】物理层-数据交换方式
    为什么要数据交换:减少链路电路交换原理:在数据传输期间,源结点与目的结点之间有一条由中间结点构成的专用物理连接线路,在数据传输结束之前,这条线路一直保持。交换的阶段:建立连接(呼叫/设备间逐个地电路建立)通信(数据传输)释放连接(拆除电路)特点:独占资源,用户始终占用端到......
  • 2024-02-29-Linux高级网络编程(1-计算机网络概述)
    1.计算机网络概述1.1计算机发展简史最早的广域网:在通信双方或多方之间,通过电路交换建立电路连接的网络。1.1.1电路交换特点建立链接->使用链接->释放链接物理通路被通信双方独占1.1.2电路交换适用于电话网​计算机数据是突发式出现在数据链路上的,而电路交......
  • 北斗同步时钟服务器(NTP网络时间服务器)应用于计算机网络系统
    北斗同步时钟服务器(NTP网络时间服务器)应用于计算机网络系统北斗同步时钟服务器(NTP网络时间服务器)应用于计算机网络系统京准电子科技官微——ahjzsz前言近几年来,随着计算机自动化系统水平的提高,在各大计算机监控系统、微机保护装置、微机故障录波装置以及各类数据管理机得......
  • 数据链路(相邻节点传输数据帧)(计算机网络)
    信道:以传输媒介为基础的信号通道。数据链路层信道点对点信道:使用一对一的点对点通信方式广播信道:使用一对多的广播通信方式。广播信道上连接的主机很多,因此必须使用专用的共享信道协议来协调这些主机的数据发送。从数据链路层看,H1到H2的通信可以由四段不同的链路层通信组......
  • 【计算机网络】物理层重要公式:奈氏准则&香农定理
    奈氏准则&香农定理失真影响失真程度的因素:1.码元传输速率2.信号传输距离3.噪声干扰4.传输媒体质量码间串扰码间串扰指接收端收到的信号波形失去了码元之间清晰界限的现象。信道带宽:最高频-最低频。超过的部分发生码间串扰,小于的部分发生失真?奈氏准则奈氏准则在理想......
  • 【计算机网络】物理层基本概念
    物理层基本概念物理层的接口特性物理层解决如何在连接各种计算机的传输媒体上传输数据比特流,而不是指具体的传输媒体。物理层主要任务:确定与传输媒体接口有关的一些特性定义接口的标准等机械特性定义物理连接的特性,规定物理连接时所采用的规格、接口形状、引线数目、引脚数......
  • 计算机网络概述
    计算机网络概念计算机网络主要是由一些可编程的、通用的硬件互联而成,而这些硬件并非用来实现某一特定目的(例如传输数据或者视频信号)。这些可编程的硬件能够用来传送多种不同类型的数据,并能支持广泛的和日益增长的应用。计算机网络由若干节点和连接这些节点的链路组成。网络......
  • 计算机网络体系结构1.3标准化及相关组织
    计算机网络标准化及相关组织标准化工作:标准分类:法定标准\事实标准法定标准:有权威机构指定的正式的\合法的标准.(可以是国内的法定标准,亦可以是国际的法定标准)-->>OSI参考模型事实标准:某些公司的产品在竞争中占据了主流,时间长了,这些产品中的协议和技术就成了标......