计算机网络:数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码

本文主要是介绍计算机网络:数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

带你度过期末难关

文章目录
  • 一、差错控制
    • 1、冗余编码
    • 2、编码VS编码
  • 二、检错编码
    • 1、奇偶校验码
    • 2、CRC循环冗余码
  • 三、纠错编码————海明码
    • 海明距离
    • 1、确定校验码位数r
    • 2、确定校验码和数据的位置
    • 3、求出校验码的值
    • 4、检错并纠错
      • 纠错的方法一:
      • 纠错方法二:
  • 总结


一、差错控制

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

全局性
1.由于线路本身电气特性所产生的随机噪声(热噪声),是信道固有的,随机存在的。
解决办法:提高信噪比来减少或避免干扰。(对传感器下手)

局部性
⒉.外界特定的短暂原因所造成的冲击噪声,是产生差错的主要原因。
解决办法:通常利用编码技术来解决。

差错

  • 位错:【比特位出错,1变成0,0变成1。】
  • 帧错:
    • 丢失:收到[#1]-[#3]
    • 重复:收到[#1]-[#2]-[#2]-[#3]
    • 失序:收到[#1]-[#3]-[#2]

链路层为网络层提供服务:

  • 无确认无连接服务:通信质量好,有线传输链路
  • 有确认无连接服务:通信质量差的无线传输链路
  • 有确认面向连接服务:通信质量差的无线传输链路

1、冗余编码

在数据发送之前,先按某种关系附加上一定的冗余位,构成一个符合某一规则的码字后再发送。当要发送的有效数据变化时,相应的冗余位也随之变化,使码字遵从不变的规则。接收端根据收到码字是否仍符合原规则,从而判断是否出错。

2、编码VS编码


数据链路层编码和物理层的数据编码与调制不同。物理层编码针对的是单个比特,解决传输过程中比特的同步等问题,如曼彻斯特编码。而数据链路层的编码针对的是一组比特,它通过冗余码的技术实现一组二进制比特串在传输过程是否出现了差错。

二、检错编码

1、奇偶校验码

奇校验:原始码流+校验位 总共有奇数个1

偶校验:原始码流+校验位 总共有偶数个1

校验位只有1个


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

2、CRC循环冗余码


例题:
要发送的数据是1101011011,采用CRC校验,生成多项式是10011,那么最终发送的数据应该是?

最终发送的数据:要发送的数据+帧检验序列FCS

计算冗余码:
(1)加0:假设生成多项式G(x)的阶为r,则加r个0。
(2)模2除法:数据加O后除以多项式,余数为冗余码/FCS/CRC检验码的比特序列。


其中生成多项式是10011,而10011可以看成1×X^4 +0×X^3 +0×X^2 +1×X^1 +1×X^0。
可以看出最高阶是4阶,所以就需要在发送的数据(1101011011)后补4个0
计算过程如下图所示:
计算得出余数/FCS/冗余码:1110
那么最终发送的数据就是发送的数据+余数:11010110111110

注意:
冗余码的位数是生成多项式的最高阶数,如果你算的冗余码位数不够,需要在前面补0。(如果最高阶是4阶,冗余码计算出来的结果是11,那么冗余码应该是0011)

接收端检错过程

把收到的每一个帧都除以同样的除数,然后检查得到的余数R。

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

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

三、纠错编码————海明码

海明码:发现双比特错,纠正单比特错。
工作原理:动一发而牵全身

工作流程:

海明距离

两个合法编码(码字)的对应比特取值不同的比特数称为这两个码字的海明距离(码距),一个有效编码集中,任意两个合法编码(码字)的海明距离的最小值称为该编码集的海明距离(码距)

说白了就是两个编码之间的不同位有几个就是他们之间的海明距离。

下面不需要自己推导:

  • 如果想通过海明码去检验d位错的话,那么需要的码距是d+1位
  • 如果想通过海明码去纠正d位错的话,那么需要的码距是2d+1位

1、确定校验码位数r

数据/信息有m位,冗余码/校验码有r位

校验码一共有2^r种取值

海明不等式:2^r >=m+r+1

例题1:
要发送的数据: D=1100,求出校验码位数
解答:
可以得出数据位数m=4,满足不等式的最小r为3,即2^3>=4+3+1
也就是D=1100的海明码应该有4+3=7位,其中原数据4位,校验码3位。

例题2:
要发送的数据: D=101101,求出校验码位数
解答:
数据的位数m=6,满足不等式的最小r为4,即2^4>=6+4+1
也就是D=101101的海明码应该有6+4=10位,其中原数据6位,校验码4位。

2、确定校验码和数据的位置

例题1:
假设D=1100,校验码3位
校验码放在序号为2^n的位置,数据按序填上


然后再将1100依次填入空白处


例题2:
假设D=101101,校验码4位

3、求出校验码的值

例题1:
假设D=1100


然后用通配符管制


4号校验码负责4,5,6,7的校验
2号校验码负责2,3,6,7的校验
1号校验码负责1,3,5,7的校验

然后采用偶校验(具体采用偶校验还是奇校验题目中会给你说明)得出结果:


偶校验讲解:

  • 4号校验4567,其中567对应的值为011,进行偶校验时,必须有偶数个1,所以4为0。
  • 2号校验2367,其中367对应的值为011,进行偶校验时,必须有偶数个1,所以2为0。
  • 1号校验1357,其中357对应的值为001,进行偶校验时,必须有偶数个1,所以1为1。

故1100的海明码为:1000011

例题2:
假设D=101101
故101101的海明码为0010011101

4、检错并纠错

假设D=1100
若接收方收到的数据为1110001,(7到1位)检错类似奇偶校验

纠错的方法一:


1,3,5,7出错了,4,5,6,7出错了,得出5和7可能是错的,再由2,3,6,7是正确的排除7,所以错误的是5.

文字描述:找到不满足奇/偶校验的分组取交集,并与符合校验的分组取差集。

纠错方法二:


首先列出X1、X2、X4的校验结果,然后通过自身偶校验得出X1、X2、X4的结果为101,得出十进制是5,所以第五位错了。


总结

以上就是数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码的相关知识点,希望对你有所帮助。

这篇关于计算机网络:数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/479916

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

MySQL大表数据的分区与分库分表的实现

《MySQL大表数据的分区与分库分表的实现》数据库的分区和分库分表是两种常用的技术方案,本文主要介绍了MySQL大表数据的分区与分库分表的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有... 目录1. mysql大表数据的分区1.1 什么是分区?1.2 分区的类型1.3 分区的优点1.4 分

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

SpringBoot整合jasypt实现重要数据加密

《SpringBoot整合jasypt实现重要数据加密》Jasypt是一个专注于简化Java加密操作的开源工具,:本文主要介绍详细介绍了如何使用jasypt实现重要数据加密,感兴趣的小伙伴可... 目录jasypt简介 jasypt的优点SpringBoot使用jasypt创建mapper接口配置文件加密

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解