-
2019-12-16 20:20:25
检错与纠错的原由
元件故障、噪声干扰等因素常常导致计算机在传输、存储或处理的过程中出现错误,故采用专门的逻辑电路对信号进行编码有便于检测错误甚至校验错误。本文介绍奇偶检验码和海明码。
奇偶校验码
这是一种最简单且应用最广泛的检错码,用的是以为校验位的奇偶校验。分成水平奇校验和水平偶校验。
1、水平奇校验
设数据X是一个n位字,在其高位前增加1位奇校验位,保证数据(包括奇校验位在内)的n+1位中,1的个数为奇数,这也就是奇校验称呼的由来。
例:
有X = 0100010,采用水平奇校验时,由于X本身的1的个数是2个,所以在高位前添加1使得X的1的个数是奇数个,即X变成10100010.2、水平偶校验
与奇校验类似,水平偶校验在数据的高位前添加一位校验位使得此数据各位上1的个数为偶数。当传输到对方的时候可以通过对传过来的数据X进行检测,如果没有出现问题则可认为在传输或者存储的过程中没有发生1位错误。
例:
有X = 0100010,采用水平奇校验时,由于X本身的1的个数是2个,所以在高位前添加0使得X的1的个数是偶数个,即X变成00100010.当传输到对方的时候可以通过对传过来的数据X进行检测,如果没有出现问题则可认为在传输或者存储的过程中没有发生1位错误。3、不足和改进
对于出现一位错误的情况,奇偶校验可以检测出错误但却不能检测出错误的准确位置,同时,当数据出现两位同时出现错误会导致检错码失去作用,但由于实现起来非常简单容易由此得到了广泛的应用。对于上述提到的两个问题,伟大的先人(是不是说老了,其实很多人还挺年轻的)在上面两个校验码的基础之上相继发明了垂直奇偶校验码和水平垂直检验码(在这我就不多说了)。
海明校验码
为了针对更复杂更庞大的数据能及时检错和纠错,通常将原数据配成海明编码。
1、编码纠错理论–编码最小距离(码距)
指在一种编码系统中任意两组合法代码之间的最少二进制位数的差异。
根据纠错理论:
L - 1 = D + C 且 D >= C
即编码最小距离L越大,则其检测错误的位数D越大,纠正错误的位数C也越大,且纠错能力恒小于或等于检错能力。如当编码最小距离L=3时,最多能检错两位,或能检错一位、纠错一位。海明码就是根据这一理论提出的具有一位纠错能力的编码。2、检错
为了使检测的二进制代码具有纠错能力,需添加位检测位,添加的检测位的位数k有下面的公式得到:、
2^k > = n + k + 1
插入的位置分别是2的0次方,2的1次方,2的2次方以此类推,各位添加的检测码的值由在二进制数位置数有含有检测码的所有位置上的数进行模二加得到。
例:
X = 10101
通过上面的公式可以得到k=4,故要插入4位检测码,将每位检测码称为Pi,每位数据码称为Di,则有:
P1 = D1 + D2 + D4 + D5 = 1
P2 = D1 + D3 + D4 = 1
P3 = D2 + D3 + D4 = 1
P4 = D5 = 1
故添加的检测码是1111,所以最后传输的数据是11101011。3、纠错
当接收方接收到数据以后,首先提取出检测码1111,然后求出指错字,设指错字为Gi,通过下列计算出指错字Gi:
G1 = P1 + D1 + D2 + D4 + D5 = 0
G2 = P2 + D1 + D3 + D4 = 0
D3 = P3 + D2 + D3 + D4 = 0
D4 = P4 + D5 = 0
上面求出的指错字是无数据出错的状态下的,当有数据出错时指错字的大小就是出错数据位的位置。4、不足
海明码优点多多(当初学习的时候感觉发明这种检错码的人简直是天才!!!),但当检测出错误并得到错误数据位位置后的实际纠错的方式并没有太过先进的地方(虽然已经很好了),同时也只能检测并纠错一位数据位错误。
这是我的人生中的第一篇博客,打算记录下自己在学习计算机组成原理中感觉比较有意思的知识,大家以后多多关照(≧▽≦)/啦!
更多相关内容 -
3 种常用校验码「奇偶校验码」「海明校验码」「循环冗余校验码」
2021-12-23 20:05:46校验码是指能够发现或能够自动纠正错误的数据编码,也称检错纠错码。 校验码的原理是通过增加一些冗余码,来检验或纠错编码。1. 奇偶校验码
> 校验码
校验码是指能够发现或能够自动纠正错误的数据编码,也称检错纠错码。
校验码的原理是通过增加一些冗余码,来检验或纠错编码。
如上图,添加一位冗余码,这时当出现位错误时(如 100 -> 101),就会发现变为非法状态进而检错。
> 几个概念
- 码字: 由若干位代码组成的一个字
- 码字间的距离:两个码字逐位对比,具有不同位的个数
- 码距:各合法码字间的最小距离
当码距 d = 1 时,无检错能力;d >= 2 时,有检错能力。码距越大,检错、纠错能力越强。
> 奇偶校验码
- 奇校验码:整个校验码(有效信息位和校验位)中 1 的个数为奇数
- 偶校验码:整个校验码(有效信息位和校验位)中 1 的个数为偶数
具体来说如何检验这就涉及到计网所学:
> 偶检验的硬件实现
各信息进行异或运算,得到的结果即为偶校验位:
2. 海明校验码
海明码实际上是一种多重奇偶校验码。其实现原理是将信息位分组进行奇偶校验,有多个校验位,并且多个校验位可以标注出出错位置。
> 确定校验位数目
设信息位为 D 4 D 3 D 2 D 1 D_4D_3D_2D_1 D4D3D2D1 共 4 位,则校验位 P 3 P 2 P 1 P_3P_2P_1 P3P2P1 共 3 位,对应海明码 H 7 H 6 H 5 H 4 H 3 H 2 H 1 H_7H_6H_5H_4H_3H_2H_1 H7H6H5H4H3H2H1 。
> 确定校验位的分布
海明码规定,校验位 P i P_i Pi 要放在海明位号为 2 i − 1 2^{i-1} 2i−1 的位置上。因此, H 1 H_1 H1 = P 1 P_1 P1、 H 2 H_2 H2 = P 2 P_2 P2、 H 4 H_4 H4 = P 3 P_3 P3
对于信息位 D 4 D 3 D 2 D 1 D_4D_3D_2D_1 D4D3D2D1 (1010),按顺序插入,则有:
> 校验位的值将每个信息位所处的海明位号以二进制形式表示出来,校验位 P i P_i Pi 的值为第 i 组(由该校验位校验的数据位)所有位求异或,如下图:
则有下表:
> 海明的校验原理每个校验组分布利用校验位和参与形成该校验位的信息位进行奇偶校验,构成 k 个校验方程:
- S 1 = P 1 ⊕ D 1 ⊕ D 2 ⊕ D 4 S_1 = P_1 ⊕ D_1 ⊕ D_2 ⊕ D_4 S1=P1⊕D1⊕D2⊕D4
- S 2 = P 2 ⊕ D 1 ⊕ D 3 ⊕ D 4 S_2 = P_2 ⊕ D_1 ⊕ D_3 ⊕ D_4 S2=P2⊕D1⊕D3⊕D4
- S 3 = P 3 ⊕ D 2 ⊕ D 3 ⊕ D 4 S_3 = P_3 ⊕ D_2 ⊕ D_3 ⊕ D_4 S3=P3⊕D2⊕D3⊕D4
若 S 3 S 2 S 1 S_3S_2S_1 S3S2S1 值为 000 000 000 ,则说明没有出错;否则说明出错, S 3 S 2 S 1 S_3S_2S_1 S3S2S1 即为错误位位号。具体来说:
注意:有的题目可能信息位和校验位顺序是颠倒的,如 D 1 D 2 D 3 D 4 D_1D_2D_3D_4 D1D2D3D4、 P 1 P 2 P 3 P_1P_2P_3 P1P2P3,但是其做法是不变的,只不过调整顺序即可。
> 补充
海明码具有 1 个比特位的纠错能力,和 2 个比特位的检错能力。但是它无法区分到底是 1 位错误还是 2 位错误。
为了解决此问题,海明码使用时通常在首部加上 全校验位 ,对整体进行偶校验。
S 3 S 2 S 1 = 000 S_3S_2S_1 = 000 S3S2S1=000 且全体偶校验成功,则没有出错。
S 3 S 2 S 1 ≠ 000 S_3S_2S_1 ≠ 000 S3S2S1=000 且全体偶校验失败,则有 1 位出错,纠错即可。
S 3 S 2 S 1 ≠ 000 S_3S_2S_1 ≠ 000 S3S2S1=000 且全体偶校验成功,则有 2 位出错,需要重传。ps:不得不说,海明太强了,怪不得获得了图灵奖
3. 循环冗余校验码
> 基本思想
收发双方约定好一个 生成多项式 G(x) ,发送方基于待发送的数据和生成多项式计算出 R 位校验码 ,将其添加到 K 位信息码 (待传输数据)的后面一起传输。
在接收端,利用生成多项式对接收到的 K+R 位 CRC 码 进行模 2 除法,若整除则说明没有出错,否则要进行重传或纠错。> 具体来说
首先,计算出 R 位校验码,即下图所示余数,并拼接成 K + R 位 CRC 码发送给接收端:
之后,对接收收到的信息与生成多项式系数所构成的比特串相除,看余数是否为 0 :
> 检错和纠错
对于上述例子,出错位置和对应余数如下图所示:
可以看出,即使计算出余数为 010 并不一定是第二位出错,也可能是第九位出错。上图是从王道考研视频中扒下来的,其实从第二行开始数据就错了。用在这里只是想说明一下 CRC 码是否可以纠错与 R 的位数是相关的,如果能够一一对应,CRC 码是可以纠错的,只需取反即可。
其实,若生成多项式选择得当,满足 2^R ≥ K+R+1,则 CRC 码是可以纠正 1 位错误的。但一般在差错检测是信息位远大于检错位,所以循环冗余校验实际中只用来检错。
-
三种常见校验码
2021-09-11 09:21:57本文主要介绍以下三种校验码:检验位求解、校验码求解、纠错能能力 奇偶校验码 海明码(汉明码) 循环冗余码(CRC码) 1.奇偶校验 校验原理 奇偶校验码 2. 海明校验码 海明码校验码思路简介 海明码求解... -
BCD码、奇偶校验码、海明校验码
2022-03-15 11:22:24BCD码 十进制数用二进制编码的形式,通过专门的十进制数运算指令进行处理。计算机中有专门的逻辑线路在BCD码运算时使每4位二进制数按十进制进行处理。 每位十进制数的取值可以是0-9这十个数之一,因此,每一个十进制...BCD码
十进制数用二进制编码的形式,通过专门的十进制数运算指令进行处理。计算机中有专门的逻辑线路在BCD码运算时使每4位二进制数按十进制进行处理。
每位十进制数的取值可以是0-9这十个数之一,因此,每一个十进制数位必须至少由4位二进制位来表示。而4位二进制位可以组合成16种状态,去掉10种状态后还有6种冗余状态,所以从16种状态中选取10种状态来表示十进制数位0-9的方法很多,可以产生多种BCD种。
8421码的映射关系:
4个二进制位 ------>16种不同的状态BCD码值使用其中10种 ------>不同的映射方案
注:0000-1001分别对应0-9,进行加法后若超出该范围,则需+0110进行修正(强制向高位进1)
余3码:8421码+ ( 0011 ) 2 (0011)_2 (0011)2
2421码:改变权值定义
2、4、 2、 1分别对应,每一位的权值表示0-4时最高位为0,表示5-9时最高位为1
奇偶校验码
几个简单的概念:
码字:由若干位代码组成的一个字
两个码字间的距离:将两个码字逐位进行对比,具有不同的位的个数
码距:一种编码方案可能有若干个合法码字,各合法码字间的最小距离
当码距d=1时,无检错能力;当d=2时,有检错能力;当d>=3,若设计合理,可能具有检错、纠错能力。
奇偶校验码
奇校验码:整个校验码(有效信息位和校验位)中“1”的个数为奇数
偶校验码:整个校验码(有效信息位和校验位)中“1”的个数为偶数
例:给出两个编码1001101和1010111的奇校验码和偶校验码。
设最高位为校验位,余7位是信息位,则对应的奇偶校验码为:
奇校验:11001101 01010111
偶校验:01001101 11010111偶校验的硬件实现:各信息进行异或(模2加)运算,得到的结果即为偶校验位
⊕:异或(模2加)
0⊕0=0
0⊕1=1
1⊕0=1
1⊕1=0求偶校验位:
1⊕0⊕0⊕1⊕1⊕0⊕1=0
1⊕0⊕1⊕0⊕1⊕1⊕1=1
进行偶校验(所有位进行异或,若结果为1说明出错):
0⊕1⊕0⊕0⊕1⊕1⊕0⊕1=0
海明校验码
偶校验:1010 ->01010,能发现奇数位错误,但无法确定是哪一位出错。
海明码设计思路:将信息位分组进行偶校验 ->多个校验位 ->多个校验位标注出错位置
信息位:n
校验位:k ------->2^k种状态
信息位+校验位:n+k
——————> 2^k>=n+k+1其中n+k位中任何一位都可能出错,1表示1中正确状态
海明码求解步骤:例:信息位:1010
1.确定海明码的位数:2^k>=n+k+1
n=4 ----> k=3
设信息位 D 4 D_4 D4 D 3 D_3 D3 D 2 D_2 D2 D 1 D_1 D1(1010),共4位,校验位 P 3 P_3 P3 P 2 P_2 P2 P 1 P_1 P1,共3位,对应的海明码为 H 7 H_7 H7 H 6 H_6 H6 H 5 H_5 H5 H 4 H_4 H4 H 3 H_3 H3 H 2 H_2 H2 H 1 H_1 H12.确定校验位的分布
校验位 P i P_i Pi放在海明位号位2i-1 的位置上,信息位按顺序放在其余位置
3.求校验位的值二进制:
H 3 H_3 H3:3 -->011
H 5 H_5 H5:5 -->101
H 6 H_6 H6:6 -->110
H 7 H_7 H7:7 -->111
将末尾为1的值进行偶校验:
P 1 P_1 P1= H 3 H_3 H3⊕ H 5 H_5 H5⊕ H 7 H_7 H7= D 1 D_1 D1⊕ D 2 D_2 D2⊕ D 4 D_4 D4=0⊕1⊕1=0
同理中间一位:
P 2 P_2 P2= H 3 H_3 H3⊕ H 6 H_6 H6⊕ H 7 H_7 H7= D 1 D_1 D1⊕ D 3 D_3 D3⊕ D 4 D_4 D4=0⊕0⊕1=1
第一位:
P 3 P_3 P3= H 5 H_5 H5⊕ H 6 H_6 H6⊕ H 7 H_7 H7= D 2 D_2 D2⊕ D 3 D_3 D3⊕ D 4 D_4 D4=1⊕0⊕1=0
4.纠错对各个分组进行偶校验运算
校验方程:S 1 S_1 S1= P 1 P_1 P1⊕ D 1 D_1 D1⊕ D 2 D_2 D2⊕ D 4 D_4 D4
S 2 S_2 S2= P 2 P_2 P2⊕ D 1 D_1 D1⊕ D 3 D_3 D3⊕ D 4 D_4 D4
S 3 S_3 S3= P 3 P_3 P3⊕ D 2 D_2 D2⊕ D 3 D_3 D3⊕ D 4 D_4 D4
接收到:1010010
S 1 S_1 S1= P 1 P_1 P1⊕ D 1 D_1 D1⊕ D 2 D_2 D2⊕ D 4 D_4 D4=0⊕0⊕1⊕1=0
S 2 S_2 S2= P 2 P_2 P2⊕ D 1 D_1 D1⊕ D 3 D_3 D3⊕ D 4 D_4 D4=1⊕0⊕0⊕1=0
S 3 S_3 S3= P 3 P_3 P3⊕ D 2 D_2 D2⊕ D 3 D_3 D3⊕ D 4 D_4 D4=0⊕1⊕0⊕1=0
海明码的检错、纠错能力:纠错——1位
检错——2位 -
三种校验码
2021-07-28 06:48:54奇偶校验、海明码、CRC循环冗余校验码三种校验码比较重要,需要牢记,在计算机网络中用处较大奇偶校验根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶... -
海明校验码理解+纠错原理
2018-04-08 14:15:43一、如何求海明校验码(主要想看看如何求每一个校验码对应的校验的信息位):校验码——揭开海明校验码求解之谜: https://blog.csdn.net/xingyu0806/article/details/48765855 二、海明校验码如何纠错:你看得懂... -
数据校验-奇偶校验码/海明码/循环冗余码
2021-04-02 20:33:16【前言】 数据在传输的过程中,会受到各种干扰的影响,如脉冲干扰,随机噪声干扰和人为干扰等,...所以,为了解决这个问题,数据单位中不能全部都是数据本身,还要包含其他帮助检错或纠错的东西,将这个数据单位称... -
海明码校验和纠错原理
2018-05-22 13:16:39海明码(Hamming Code)是一个可以有多个校验位,具有检测并纠正一位错误代码的纠错码,所以它也仅用于信道特性比较好的环境中,如以太局域网中,因为如果信道特性不好的情况下,出现的错误通常不是一位。 海明码的... -
纠错码
2021-06-23 03:34:02为使一种码具有检错或纠错能力,须对原码字增加多余的码元,以扩大码字之间的差别 ,即把原码字按某种规则变成有一定剩余度(见信源编码)的码字,并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收... -
计算机组成原理(校验码).ppt
2021-07-16 03:57:261、校验码,具有发现错误或者同时能给出错误所在位置的数据编码,就称为数据校验码。 纠错的关键是确定错误位置,然后取反即可。,将数据分组,每一组数据后附加一个校验位,使得该组数据(包括校验位)中1的个数为偶数... -
校验码中码距与纠错能力的关系
2012-10-13 22:01:38纠错编码的基本原理 1、 基本概念 为了方便对差错编码原理进行叙述下面先介绍一些基本术语。 1、 信息码元——指进行差错编码前送入的原始信息编码。 2、 监督码元——指经过差错编码后在信息码元基础上增加... -
计算机系统基础知识——校验码之奇偶校验码
2020-10-07 20:16:22前言:奇偶校验码是一种增加二进制代码传输距离最简单和最广泛的方法,通过增加冗余位使码字中“1”的个数恒为奇数或者偶数。 -
校验码 / 码距(奇偶校验 、海明校验、循环冗余校验码CRC)
2021-05-26 04:21:42一、码距一个编码系统中任意两个合法编码(码字)之间不同的二进数位(bit)数叫这两个码字的码距,而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。如图1所示的一个编码系统,用三个bit来表示八个不同... -
CRC循环校验码原理及计算举例
2019-11-21 09:51:02循环冗余校验码(CRC),简称循环码,是一种常用的、具有检错、纠错能力的校验码,在早期的通信中运用广泛。通过某种数学运算来建立数据位和校验位的约定关系。这种数学运算就是“模2除法”。这种编码基本思想是将要... -
海明校验码原理以及作用机制的介绍
2021-01-07 19:50:51对于海明校验码的原理和作用机制进行了介绍,并且给出了相关的例证作为辅助说明! -
计算机网络用多维奇偶校验码.pdf
2021-07-16 04:04:36公二二二二 二 二二二一二二艺二二二二二 计算机网络用多维奇偶校验码 靳蕃 西南交通 大 学 提要 本文介绍了几个用来计算水平一垂道奇偶校验码漏检错误图样数目的公式 为了提高计算机网络数据传输中的检错纠错能力 ... -
数据BCC校验码计算工具
2020-12-30 22:32:32这是数据BCC校验码计算工具下载,获得数据BCC校验码...而另一方面在数据编码上采取编码纠码的措施,使得机器能够自己发现错误甚至纠正错误,我们把这种具有检测错误或带有自动纠错能力的数据编码称为数据校验码。... -
一下子看懂校验码,CRC,海明码
2018-07-09 19:42:05校验码 能够发现错误或者自动纠错的数据...码距大于等于2的数据校验码,开始具有检错能力。 三种常见的校验码: 1、奇偶校验码 在首部增加一位二进制位(校验位),称为奇偶校验码,它可以检测出一位错误,... -
海明校验码的编码规则有哪些?
2021-05-26 04:20:07在海明码中, 位号数(1、2、3、……、n)为2的权值的那些位,即:1(2^0)、2(2...例如: N=11(海明码位数)K=7(数据位数)r=4(校验位) ,相应海明码可表示位号为: 1, 2, 3, 4 ,5 ,6, 7, 8, 9 ,10 ,11,校验位P占... -
进制、BCD码、ASKII码、校验码
2022-01-12 10:09:06R进制:基数=R,每个数码位可能出现R种字符,逢R进1 R进制转十进制:类比二进制转十进制 二进制转八进制:每3个二...BCD码:8421码 余3码 2421码 985(D) 1001 0100 0101(8421码) 1001 0100 1000(余3码) 1111 1110 1011 -
CRC循环冗余校验码
2022-04-03 16:51:33具有检错、纠错能力的校验码 模二除法(模二除法的结果不等于普通除法) 当部分余数首位是1时商取1,反之商取0。然后每一位的减法运算是按位减,不产生借位 例如: 如果要传输的数据为:1101011011 除数设为:10011 ... -
一道题带你搞懂CRC循环冗余校验是如何纠错的, 体会CRC的奇妙之处, 献给充满好奇心的你.
2021-05-09 08:41:41想必看到这片文章的同学,已经对CRC校验码的生成过程和理论依据如数家珍,但是CSDN上却很少有详细讲述CRC是如何纠错的。关于CRC校验码生成的理论,前人之述备矣,我也就不赘述了,不了解的同学可以在CSDN上搜索CRC... -
检错码与纠错码,一码归一码
2020-05-25 22:37:04检错码与纠错码,一码归一码 写在前面: 为什么需要差错处理 任何信道,即使是光纤,也会出错。 差错的类型 单个错误:分散在各块中 突发错误:集中在某个块中 注:突发错误比单个错误更加难于处理,通常利用处理单个... -
奇偶校验码(计算机组成原理10)
2020-10-05 13:00:46- 校验原理、奇偶校验的相关定义 - 计算机内部如何实现奇偶校验 -
一文搞定校验码(奇偶校验,海明,CRC 码)
2021-03-09 06:14:36效验码校验码:指能够发现或能够自动纠正错误的数据编码,也称检错纠错编码。实现原理:通过加一冗余码,来检验或纠错编码码字 : 由若干位代码组成的一个字码距:将两个码字逐位进行对比,具有不同的位的个数称为两... -
数据的表示和运算,进制转换,BCD码,奇偶校验码,海明校验码,循环冗余码
2022-04-02 17:05:04当d>=3时,若设计合理,可能具有检错,纠错能力。 奇偶校验码,缺点:只能发现奇数位的错误 奇偶校验位 有效信息位 1位 n位 eg:给出两个编码1001101和1010111的奇校验码和偶校验码 设最高位为校验位,余7位为有效... -
计算机网络:纠错
2021-06-23 03:34:13本文概述当数据从发送方发送到接收方时, 纠错码用于检测和纠正错误。纠错可以通过两种方式处理:向后纠错:发现错误后, 接收方会请求发送方重新传输整个数据单元。前向纠错:在这种情况下, 接收器使用纠错码自动纠正... -
海明校验码原理(详解)
2021-05-25 08:32:55海明校验1.海明校验的基本思想将有效信息按某种规律分成若干组,每组安排一个校验位,做...校验位的位数 校验位的位数与有效信息的长度有关设:N--为校验码的位数 K--是有效信息位 r--校验位(分成r组作奇偶校验,... -
海明码检错与纠错,经典例子讲解~
2020-12-01 09:19:31海明码检错与纠错,经典例子讲解~ -
海明校验码
2021-03-08 19:20:20由Richard Hamming于1950年提出、目前还被广泛采用的一种很有效的校验方法,是只要增加少数几个校验位,就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段,后者被称为自动纠错。...