奇偶校验,CRC循环冗余校验,海明码校验

简介: 奇偶校验,CRC循环冗余校验,海明码校验

码距

任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。

例如:00,01,10,11

00,01---变化的二进制位数有1位

00,11---变化的二进制位数有2位

所以最小的变化位数是1,码距为1

1.奇偶校验

奇偶校验码的编码方法是:由若干位有效信息 (如一个字节),再加上一个二进制位(校验位) 组成校验码。


奇校验:整个校验码(有效信息位和校验位) 中“1”的个数为奇数

偶校验:整个校验码(有效信息位和校验位) 中“1”的个数为偶数。


对于奇偶校验,只能检测出奇数个错误或者一位错误,例如11变为00,还是偶数个“1”,偶数的错误“0”和“1”会相互抵消,无法检错,并且不可以纠错。

2.CRC循环冗余校验

把接收到的CRC码用约定的生成多项式G(X)除 (模二除法) ,如果正确则余数为0; 如果某一位出错,则余数不为0。不同的位数出错其余数不同,余数和出错位序号之间有惟一的对应关系。

可检错,不可纠错可检错,不可纠错

模二除法的具体过程,通过例题来看:


要发送的数据为1101011011。采用CRC的生成多项式是 P(X)=X^4+X+1。试求应添加在数据后面的余数。

(1)若要发送的数据在传输过程中最后一个1变成了0,即变成了1101011010,问接收端能否发现?

(2)若要发送的数据在传输过程中最后两个1变成了0,即变成了1101011000,问接收端能否发现?

采用 检验后,数据链路层的传输是否就变成了可靠的传输?

由上面运算结果可知需要添加的余数为1110

3.海明校验码

在有效信息位中加入几个校验位形成海明码,使码距比较均匀地拉大,并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后,就会引起有关的几个校验位的值发生变化,这不但可以发现错误,还能指出错误的位置,对应公式:

,其中n为数据位数,k为校验位数

注:校验码是通过扩大码距进行校验的,所以码距>1

对于海明码的求解过程:

例1:

若题目给出的数据是1010,默认D1~D4=1010,带入公式,得到k=3,表示有3个校验码

3个校验码分别为

列如下表格

对于P1,我们寻找最低位有1的数,其他同理:

P1(001):③011⑤101⑦111

P2(010):③011⑥110⑦111

P3(100):⑤101⑥110⑦111

接下来,我们将1010带入,默认为偶校验(异或计算):

P1:③⑤⑦--->1 0 0=1

P2:③⑥⑦--->1 1 0=0

P3:⑤⑥⑦--->0 1 0=1

最后将P1,P2,P3:101带入,就得到海明校验码:1 0 1 1 0 1 0

例2:

若题目给出D8~D1:10101011,也就是降序排列,那么我们写数列时就反过来写:

数据位是8,那么k=4,即校验位为4,4+8=12,数列至少需要画12格

P1:③⑤⑦⑨⑪---->11100=1

P2:③⑥⑦⑩⑪---->10110=1

P3:⑤⑥⑦⑫---->1011=1

P4:⑨⑩⑪⑫---->0101=0

所以海明码:1 0 1 0 0 1 0 1 1 1 1 1

拓展:

P13进行全校验,即看海明码是否满足偶校验,满足则前面添0,否则添1,这里满足,所以:

(0)1 0 1 0 0 1 0 1 1  1 1 1

4.校验方式的对比

目录
相关文章
|
移动开发
【软考】校验码之详细总结
【软考】校验码之详细总结
1690 0
|
4月前
|
人工智能 运维 开发工具
一篇搞懂 AI Agent 架构选型,避开 80% 落地坑!
AI Agent正加速落地,但架构选型常成绊脚石。本文精析LangChain、LangGraph、AutoGen、CrewAI、OpenAI Agents SDK五大主流框架,从任务复杂度、可控性、开发效率、成本四大维度对比,助企业按需选型、避坑提速,实现智能化升级。
一篇搞懂 AI Agent 架构选型,避开 80% 落地坑!
|
人工智能 程序员 Go
一文掌握 MCP 上下文协议:从理论到实践
本文介绍了 模型上下文协议(Model Context Protocol,MCP),一种用于规范大型语言模型(LLM)与外部数据源及工具之间交互的开放标准。内容涵盖了 MCP 协议的整体架构(客户端与服务器的一对一连接模式)、消息传输机制(采用 JSON-RPC 2.0 格式)、以及客户端与服务器支持的核心原语。
6769 70
|
算法
海明码详解
本文详细介绍了海明码(Hamming Code)的概念、原理和应用,包括信息位与校验位的关系、校验位的计算方法、错误检测与纠正过程,并通过实例展示了如何使用海明码进行编码,突出了海明码在提高数据传输可靠性方面的重要性。
2770 0
海明码详解
|
数据安全/隐私保护
思科模拟器Cisco Packet Tracer 8.2.1注册、下载和安装教程(正确+详细)
本文详细总结了思科模拟器Cisco Packet Tracer 8.2.1注册、下载和安装教程(正确+详细),看这一篇就够啦~
60213 7
思科模拟器Cisco Packet Tracer 8.2.1注册、下载和安装教程(正确+详细)
|
存储 前端开发 中间件
『软件工程10』结构化系统分析:数据流图和字典案例分析
该文章通过具体案例分析了在软件工程中如何运用数据流图和数据字典来进行结构化系统分析,帮助明确系统的信息流程和数据定义。
『软件工程10』结构化系统分析:数据流图和字典案例分析
|
传感器 C++
计算机网络:数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码
计算机网络:数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码
1789 0
|
运维 负载均衡 监控