计算机网络:数据链路层之差错控制、奇偶校验码、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/479961

相关文章

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

SpringBoot集成Milvus实现数据增删改查功能

《SpringBoot集成Milvus实现数据增删改查功能》milvus支持的语言比较多,支持python,Java,Go,node等开发语言,本文主要介绍如何使用Java语言,采用springboo... 目录1、Milvus基本概念2、添加maven依赖3、配置yml文件4、创建MilvusClient

SpringValidation数据校验之约束注解与分组校验方式

《SpringValidation数据校验之约束注解与分组校验方式》本文将深入探讨SpringValidation的核心功能,帮助开发者掌握约束注解的使用技巧和分组校验的高级应用,从而构建更加健壮和可... 目录引言一、Spring Validation基础架构1.1 jsR-380标准与Spring整合1

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

SpringBatch数据写入实现

《SpringBatch数据写入实现》SpringBatch通过ItemWriter接口及其丰富的实现,提供了强大的数据写入能力,本文主要介绍了SpringBatch数据写入实现,具有一定的参考价值,... 目录python引言一、ItemWriter核心概念二、数据库写入实现三、文件写入实现四、多目标写入

使用Python将JSON,XML和YAML数据写入Excel文件

《使用Python将JSON,XML和YAML数据写入Excel文件》JSON、XML和YAML作为主流结构化数据格式,因其层次化表达能力和跨平台兼容性,已成为系统间数据交换的通用载体,本文将介绍如何... 目录如何使用python写入数据到Excel工作表用Python导入jsON数据到Excel工作表用