精华内容
下载资源
问答
  • 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、不足

    海明码优点多多(当初学习的时候感觉发明这种检错码的人简直是天才!!!),但当检测出错误并得到错误数据位位置后的实际纠错的方式并没有太过先进的地方(虽然已经很好了),同时也只能检测并纠错一位数据位错误。

    这是我的人生中的第一篇博客,打算记录下自己在学习计算机组成原理中感觉比较有意思的知识,大家以后多多关照(≧▽≦)/啦!

    更多相关内容
  • 摘要:星载计算机系统中电子器件容易受到空间环境电磁场的辐射和重粒子的冲击,从而导致器件运行出错,特别是存储器中数据容易出现错误,需要具有纠错功能的电路模块对其进行纠正,以免造成严重的后果。...
  • 摘要:星载计算机系统中电子器件容易受到空间环境电磁场的辐射和重粒子的冲击,从而导致器件运行出错,特别是存储器中数据容易出现错误,需要具有纠错功能的电路模块对其进行纠正,以免造成严重的后果。...
  • 1)图解纠错演练:从用户输入一个字符串,在屏幕上逐步进行错误归纳、检测和纠正。 2) 向字符串添加校验位:要求用户输入一个二进制字符串,并输出添加了正确校验位的字符串。 3) 从字符串中去除奇偶校验位:要求...
  • 下面我将介绍两个差错校验码:1、奇偶校验码和2、CRC循环冗余校验码。还有一个具有差错检验和纠错的海明码。 二、奇偶校验码 众所周知,数据在传输过程中是以0和1的比特流进行传输的。奇偶校验的规则就是添加一位...

    一、差错校验和纠错

    数据在传输过程中可能会因为其内部或者外部原因导致数据出现错误,因此需要对数据进行校验进而发现错误的数据帧等或者比特流。下面我将介绍两个差错校验码:1、奇偶校验码和2、CRC循环冗余校验码。还有一个具有差错检验和纠错的海明码。

    二、奇偶校验码

    众所周知,数据在传输过程中是以0和1的比特流进行传输的。奇偶校验的规则就是添加一位或者两位比特位,对数据进行填充使数据中0或1的个数变为奇数或者偶数,这种方式就是奇偶校验方式。但是这种校验方式只能找出奇数个比特位的错误,对于偶数个比特位的差错校验不出来。

    三、CRC冗余校验码

    实现CRC循环冗余校验码,假设传输的字符串为110010110,用1101进行计算得到多项式Y=x^5 +X^2。其具体的计算步骤如下:
    在这里插入图片描述

    四、海明码

    海明码具有检错和纠错的功能,进行海明码进行纠错检错的步骤如下:
    1、确定海明码的位数:计算公式是:n+k<2^k -1,其中n为元字符串个数,k为海明码个数。
    2、确定校验码的位置分布,放在2^n位置上。其中,n=0,1,2,3,4,5…
    3、分组进行校验,例如第三位数据是由1和2 进行校验,第五位数据是由第四位和第一位进行校验组成
    4、校验值的确定,利用异或关系进行海明码的值的确定。假如数据只有两位,他们分布在第三位和第五位数据位,则第一位数据校验码就是由第三位和第五位数据异或得到的。

    展开全文
  • 三种校验码

    千次阅读 2021-07-28 06:48:54
    奇偶校验、海明码、CRC循环冗余校验码三种校验码比较重要,需要牢记,在计算机网络中用处较大奇偶校验根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶...

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

    三种校验码比较重要,需要牢记,在计算机网络中用处较大

    奇偶校验

    根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位,用它使这组代码中“1”的个数为奇数或偶数。若用奇校验,则当接收端收到这组代码时,校验“1”的个数是否为奇数,从而确定传输代码的正确性。

    校验方法

    奇校验:就是让原有数据序列中(包括你要加上的一位)1的个数为奇数

    1000110(0)你必须添0这样原来有3个1已经是奇数了所以你添上0之后1的个数还是奇数个。

    偶校验:就是让原有数据序列中(包括你要加上的一位)1的个数为偶数

    1000110(1)你就必须加1了这样原来有3个1要想1的个数为偶数就只能添1了

    范例

    串行数据在传输过程中,由于干扰可能引起信息的出错,例如,传输字符‘E’,其各位为:

    0100,0101=45H

    D7 D0

    由于干扰,可能使位变为1,(为什么不变0?)这种情况,我们称为出现了“误码”。我们把如何发现传输中的错误,叫“检错”。发现错误后,如何消除错误,叫“纠错”。最简单的检错方法是“奇偶校验”,即在传送字符的各位之外,再传送1位奇/偶校验位。可采用奇校验或偶校验。

    奇校验:所有传送的数位(含字符的各数位和校验位)中,“1”的个数为奇数,如:

    1 0110,0101

    0 0110,0101

    偶校验:所有传送的数位(含字符的各数位和校验位)中,“1”的个数为偶数,如:

    1 0100,0101

    0 0100,0101

    奇偶校验能够检测出信息传输过程中的部分误码(奇数位误码能检出,偶数位误码不能检出),同时,它不能纠错。在发现错误后,只能要求重发。但由于其实现简单,仍得到了广泛使用。有些检错方法,具有自动纠错能力。如循环冗余码(CRC)检错等

    CRC校验

    CRC即循环冗余校验码(Cyclic Redundancy Check):是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)是一种数据传输检错功能,对数据进行多项式计算,并将得到的结果附在帧的后面,接收设备也执行类似的算法,以保证数据传输的正确性和完整性。

    工作原理

    循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。 校验码的具体生成过程为:假设要发送的信息用多项式C(X)表示,将C(x)左移R位(可表示成C(x)2R),这样C(x)的右边就会空出R位,这就是校验码的位置。用 C(x)2R 除以生成多项式G(x)得到的余数就是校验码。

    对应关系

    多项式和二进制数有直接对应关系:X的最高幂次对应二进制数的最高位,以下各位对应多项式的各幂次,有此幂次项对应1,无此幂次项对应0。可以看出:X的最高幂次为R,转换成对应的二进制数有R+1位。

    多项式包括生成多项式G(X)和信息多项式C(X)。

    如生成多项式为G(X)=X4+X3+X+1, 可转换为二进制数码11011。

    而发送信息位 101111,可转换为数据多项式为C(X)=X5+X3+X2+X+1。

    生成多项式

    是接受方和发送方的一个约定,也就是一个二进制数,在整个传输过程中,这个数始终保持不变。

    在发送方,利用生成多项式对信息多项式做模2除生成校验码。在接收方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。

    应满足以下条件:

    A、生成多项式的最高位和最低位必须为1。

    B、当被传送信息(CRC码)任何一位发生错误时,被生成多项式做除后应该使余数不为0。

    C、不同位发生错误时,应该使余数不同。

    D、对余数继续做除,应使余数循环。

    校验码位数

    CRC校验码位数 = 生成多项式位数 - 1。注意有些生成多项式的简记式中将生成多项式的最高位1省略了。

    生成步骤

    1、将X的最高次幂为R的生成多项式G(X)转换成对应的R+1位二进制数。

    2、将信息码左移R位,相当于对应的信息多项式C(X)*2R。

    3、用生成多项式(二进制数)对信息码做除,得到R位的余数(注意:这里的二进制做除法得到的余数其实是模2除法得到的余数,并不等于其对应十进制数做除法得到的余数。)。

    4、将余数拼到信息码左移后空出的位置,得到完整的CRC码。

    【例】假设使用的生成多项式是G(X)=X3+X+1。4位的原始报文为1010,求编码后的报文。

    解:

    1、将生成多项式G(X)=X3+X+1转换成对应的二进制除数1011。

    2、此题生成多项式有4位(R+1)(注意:4位的生成多项式计算所得的校验码为3位,R为校验码位数),要把原始报文C(X)左移3(R)位变成1010 000

    3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除(高位对齐),相当于按位异或:

    1010000

    1011

    ———–】

    0001000

    0001011

    ———-】

    0000011

    得到的余位011,所以最终编码为:1010 011

    原则

    若设码字长度为N,信息字段为K位,校验字段为R位(N=K+R),则对于CRC码集中的任一码字,存在且仅存在一个R次多项式g(x),使得

    V(x)=A(x)g(x)=xRm(x)+r(x);

    其中: m(x)为K次原始的信息多项式, r(x)为R-1次校验多项式(即CRC校验和),

    g(x)称为生成多项式:

    g(x)=g0+g1x1+ g2x2+…+g(R-1)x(R-1)+gRxR

    发送方通过指定的g(x)产生CRC码字,接收方则通过该g(x)来验证收到的CRC码字。

    生成方法

    借助于模2除法则,其余数为校验字段。

    例如:信息字段代码为: 1011001;对应m(x)=x6+x4+x3+1

    假设生成多项式为:g(x)=x4+x3+1;则对应g(x)的代码为: 11001

    x4m(x)=x10+x8+x7+x4 对应的代码记为:10110010000;

    采用模2除法则: 得余数为: 1010(即校验字段为:1010)

    发送方:发出的传输字段为: 1 0 1 1 0 0 1 1010

    信息字段 校验字段

    接收方:使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)

    如果能够除尽,则正确,

    给出余数(1010)的计算步骤:

    除法没有数学上的含义,而是采用计算机的模二除法,即除数和被除数做异或运算。进行异或运算时除数和被除数最高位对齐,按位异或。

    10110010000

    ^11001

    ————————–】

    01111010000

    1111010000

    ^11001

    ————————-】

    0011110000

    11110000

    ^11001

    ————————–】

    00111000

    111000

    ^11001

    ——————-】

    001010

    则四位CRC校验码就为:1010。

    利用CRC进行检错的过程可简单描述为:在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在原始信息后边,构成一个新的二进制码序列数共k+r位,然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式”。

    海明码校验

    将有效信息按某种规律分成若干组,每组安排一个校验位,做奇偶测试,就能提供多位检错信息,以指出最大可能是哪位出错,从而将其纠正。实质上,海明校验是一种多重校验。

    假设为k个数据位设置r个校验位,则校验位能表示2^r个状态,可用其中的一个状态指出 “没有发生错误”,用其余的2 ^r -1个状态指出有错误发生在某一位,包括k个数据位和r个校验位,因此校验位的位数应满足如下关系:

    2^r ≥ k + r + 1 (2.7)

    如要能检出与自动校正一位错,并能同时发现哪位错,此时校验位的位数r和数据位的位数k应满足下述关系:

    2^r-1 ≥ k + r (2.8)

    按上述不等式,可计算出数据位k与校验位r的对应关系,如表2.2所示。

    表2.2

    k值 最小r值

    2~4 3

    5~11 4

    12~26 5

    27~57 6

    58~120 7

    分组原则

    编辑

    在海明码中, 位号数(1、2、3、……、n)为2的权值的那些位,即:

    1(20)、2(21)、4(22)、8(23)、…2^(r-1)位,作为奇偶校验位,并记作: P1、P2、P3 、P4、…Pr,余下各位则为有效信息位。例如: N=11(海明码位数)K=7(数据位数)r=4(校验位) ,相应海明码可表示位号为: 1, 2, 3, 4 ,5 ,6, 7, 8, 9 ,10 ,11,校验位P占第1,2,4,8位,其他位为有效信息位,海明码中的校验位分别标示为P1,P2,P3,P4… Pr ,并被信息位中的一至若干位所校验,其规律是:第i位,由校验位位号之和等于i的那些校验位所校验,如:海明码的位号为3,它被P1P2(位号分别为1,2)所校验,海明码的位号为5,它被P1P3(位号分别为1,4)所校验。归并起来: 形成了4个小组,每个小组一个校验位,校验位的取值,仍采用奇偶校验方式确定。

    设计海明码编码的关键技术,是合理地把每个数据位分配到r个校验组中,以确保能发现码字中任何一位出错;若要实现纠错,还要求能指出是哪一位出错,对出错位求反则得到该位的正确值。例如,当数据位为3位(用D3 D2 D1表示)时,检验位应为4位(用P4 P3 P2 P1表示)。可通过表2.3表示的关系,完成把每个数据位划分在形成不同校验位的偶校验值的逻辑表达式中。

    表2.3 校验位与数据位的对应关系

    在P1、P2、P3、P4竖列相应行分别填1,

    在该4列的低3横行其它位置分别填0,

    在最顶横行的每个尚空位置都分别填1。

    若只看低3横行,右4竖列的3个bit的组合值分别为十进制的1、2、4、0,则分配 D1 D2 D3列的组合值为3 5 6,保证低3横行各竖列的编码值各不相同。

    表中D3 D2 D1为三位数据位,P4 P3 P2 P1为四位校验位。其中低三位中的每一个校验位P3 P2 P1的值,都是用三个数据位中不同的几位通过偶校验运算规则计算出来的。其对应关系是:对Pi(i的取值为1~3),总是用处在Pi取值为1的行中的、用1标记出来的数据位计算该Pi的值。最高一个校验位P4,被称为总校验位,它的值,是通过对全部三个数据位和其它全部校验位(不含P4本身)执行偶校验计算求得的。

    形成各校验位的值的过程叫做编码,按刚说明的规则,4个校验位所用的编码方程为:

    P4 = D3 D2 D1 P3 P2 P1

    P3 = D3 D2

    P2 = D3 D1

    P1 = D2 D1

    由多个数据位和多个校验位组成的一个码字,将作为一个数据单位处理,例如被写入内存或被传送走。之后,在执行内存读操作或在数据接收端,则可以对得到的码字,通过偶校验来检查其合法性,通常称该操作过程为译码,所用的译码方程为:

    S4 = P4 D3 D2 D1 P3 P2 P1

    S3 = P3 D3 D2

    S2 = P2 D3 D1

    S1 = P1 D2 D1

    对应关系

    编辑

    译码方程和编码方程的对应关系很简单。译码方程,是用一个校验码和形成这个校验码的编码方程执行异或,实际上是又一次执行偶校验运算。通过检查四个S的结果,可以实现检错纠错的的目的。实际情况是,当译码求出来的S4、S3、S2、S1的得值与表2.3中的那一列的值相同,就说明是哪一位出错;故人们又称表2.3为出错模式表。若出错的是数据位,对其求反则实现纠错;若出错的是校验位则不必理睬。举例如下:

    任何一位(含数据位、校验位)均不错,则四个S都应为0值;

    任何单独一位数据位出错,四个S中会有三个为1;如D3错,则S4 S3 S2 S1为1110。

    若单独一位校验位出错,四个S中会有一个或两个为1;如P1错,S4 S3 S2 S1为1001,如P4错,S4 S3 S2 S1为1000。

    任何两位(含数据位、校验位)同时出错,S4一定为0,而另外三个S位一定不全为0,此时只知道是两位同时出错,但不能确定是哪两位出错,故已无法纠错。如D1、 P2出错,会使S4 S3 S2 S1为0001。请注意,S4的作用在于区分是奇数位出错还是偶数位出错,S4为1是奇数位错,为0是无错或偶数位错。这不仅为发现两位错所必需,也是为确保能发现并改正一位错所必需的。若不设置S4,某种两位出错对几个S的影响与单独另一位出错可能是一样的(不必花费精力推敲),此时若不加以区分,简单地按一位出错自动完成纠错处理反而会帮倒忙。

    展开全文
  • 校验码 奇偶校验 海明码校验

    千次阅读 2020-06-28 17:07:10
    1.奇偶校验 奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中"1"的个数是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶校验。采用何种校验是事先规定好的...

    1.奇偶校验

            奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中"1"的个数是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位,用它使这组代码中"1"的个数为奇数或偶数。若用奇校验,则当接收端收到这组代码时,校验"1"的个数是否为奇数,从而确定传输代码的正确性。

    工作方式

    为了能检测和纠正内存软错误,首先出现的是内存"奇偶校验"。内存中最小的单位是比特,也称为"位",位只有两种状态分别以1和0来标示,每8个连续的比特叫做一个字节(byte)。不带奇偶校验的内存每个字节只有8位,如果其某一位存储了错误的值,就会导致其存储的相应数据发生变化,进而导致应用程序发生错误。而奇偶校验就是在每一字节(8位)之外又增加了一位作为错误检测位。在某字节中存储数据之后,在其8个位上存储的数据是固定的,因为位只能有两种状态1或0,假设存储的数据用位标示为1、1、1、0、0、1、0、1,那么把每个位相加(1+1+1+0+0+1+0+1=5),结果是奇数。对于偶校验,校验位就定义为1;对于奇校验,则相反。当CPU读取存储的数据时,它会再次把前8位中存储的数据相加,计算结果是否与校验位相一致。从而一定程度上能检测出内存错误,奇偶校验只能检测出错误而无法对其进行修正,同时虽然双位同时发生错误的概率相当低,但奇偶校验却无法检测出双位错误。

    优缺点

    奇偶校验有两种类型:奇校验和偶校验。奇偶校验位是一个表示给定位数的二进制数中1的个数是奇数或者偶数的二进制数,奇偶校验位是最简单的错误检测码。如果传输过程中包括校验位在内的奇数个数据位发生改变,那么奇偶校验位将出错表示传输过程有错误发生。因此,奇偶校验位是一种错误检测码,但是由于没有办法确定哪一位出错,所以它不能进行错误校正。发生错误时必须扔掉全部的数据,然后从头开始传输数据。在噪声很多的媒介上成功传输数据可能要花费很长的时间,甚至根本无法实现。但是奇偶校验位也有它的优点,它是使用一位数据能够达到的最好的校验码,并且它仅仅需要一些异或门就能够生成。奇偶校验被广泛应用。

    2.海明码

    海明码简介

      海明码,小名汉明码(Hamming Code),以发明者理查德·卫斯里·汉明的名字命名。海明码具有检错和纠错双功能,它基于奇偶校验原理,只能检查出某一位错码的位置。当有多位错码时,它就不适用了。

    异或运算
      在了解汉明码之前,先熟悉下异或运算和奇偶校验。
    异或运算,相异为1,相同为0。它也叫模2和、模2加法,本质上是不带进位的加法。
    数学符号是 ⊕;
    计算机符号是“xor”;
    C语言中异或符号是^;
    常用的公式是:(a^b)^a=b,即两个数异或结果在与其中一个数异或得到的是另一个数。
    常用的应用:多用在一些加密算法中,将要加密的数据和一些已知数进行异或运算,得到加密后的数据。
    奇偶校验 :

    海明码的校验位数
      下面本例以1010110为例进行海明码编码。
      第一步先确定需要多少位校验码。
      设数据有n位,校验码有x位。则校验码一共有2x2x种取值方式。其中需要一种取值方式表示数据正确,剩下2x−12x−1种取值方式表示有一位数据出错。因为编码后的二进制串有n+x位,因此x应该满足:2x−1≥n+x2x−1≥n+x   
    使不等式成立的x的最小值就是校验码的位数。在本例中,n=7,解得x=4。
    信息码和校验码的对应关系如下表:

    校验码的位置

      校验码在二进制串中的位置为2的整数幂,即1、2、4、8、16……..剩下的位置是信息码,如图(来源百度),绿色为校验位:

    本例的校验码位置如下图:
    这里写图片描述

    计算校验位的值

    由于奇偶校验原理一样,偶校验的计算更为简单,实际中多用偶校验,本例中也以偶校验进行计算。
    这里写图片描述

    如图中:
    第一行中每个X跳过1位;第一行所有的X值进行异或是0;第一行的X对应的数据位位置转化为二进制最后一位都是1,即是xxx1这种形式;
    第二行中每2个X跳过2位;第二行所有的X值进行异或是0;第二行的X对应的数据位位置转化为二进制倒数第二位一位都是,即是xx1x这种形式;
    第三行中每4个X跳过4位;第三行所有的X值进行异或是0;第三行的X对应的数据位位置转化为二进制倒数第三位一位都是1,即是x1xx这种形式;
    第四行中每8个X跳过8位;第四行所有的X值进行异或是0;第四行的X对应的数据位位置转化为二进制倒数第四位一位都是1,即是1xxx这种形式;
    ……..
    每一行都是从对应的校验位开始校验,即从第2n/22n/2位开始校验,校验2n/22n/2个,然后跳过2n/22n/2个。
    下面计算本例子,将表格中的位置用二进制表示:

     x1的计算:
    x1是第一个校验码,位置对应栏所有最后一位为1(xxx1格式)的相异或为0,即
    这里写图片描述

     

    x1⊕1⊕0⊕0⊕1⊕0=0

    则x1=0;
    x2计算:
    x2是第二个校验码,位置对应栏所有倒数第二位为1(xx1x格式)的相异或为0,即
    这里写图片描述

     

    x2⊕1⊕1⊕0⊕1⊕0=0

     

    则x2=1;
    x3计算:
    x3是第三个校验码,位置对应栏所有倒数第三位为1(x1xx格式)的相异或为0,即
    这里写图片描述

    x3⊕0⊕1⊕0=0

     

    则x3=1;
    x4计算:
    x4是第四个校验码,位置对应栏所有倒数第四位为1(1xxx格式)的相异或为0,即
    这里写图片描述

    x4⊕1⊕1⊕0=0

    则x4=0;
    所以最终的海明码是01110100110。
    这里写图片描述

    海明码的校验
    假设位置为1011的数据传输错误,由0变成了1,则校验纠错的过程为:
      将所有位置形如xxx1, xx1x, x1xx, 1xxx的数据分别异或。
      xxx1: 0^1^0^0^1^1 = 1
      xx1x: 1^1^1^0^1^1 = 1
      x1x: 1^0^1^0 = 0
      1xxx: 0^1^1^1 = 1
     那么出错数据的位置为1011,这样便可得到出错的位置。

    假设同时有两个位置出错,本例中假设位置为1010对应数据由1变成0,,位置为1011对应数据由0变成1,则推出校验纠错过程:
      xxx1: 0^1^0^0^1^1 = 1
      xx1x: 1^1^1^0^0^1 = 0
      x1x: 1^0^1^0 = 0
      1xxx: 0^1^0^1 = 0
    那么校算出的错误位是0001,即第一位;但实际上是倒数第二位和最后一位都有错误,说明海明码不能校验两位以上出错的数据,即海明码只能检测并纠正一位错误。
     

    展开全文
  • 这两天在看网络,第一次发博客,时间仓促以后会进一步完善。 传输差错控制 计算机内部 / 网络 传递信息时对产生的差错进行控制 (1)自动重发请求...(2)前向纠错(Forward Error Correction,FEC),不但能检...
  • 通用差错检验模型 一般的检测算法都是使用特定的运算规则E,看输入的自变量和得到的因变量是否相对应 但是如果自变量和因变量在传输过程中都发生了改变,...一维奇偶校验码的编码规则是把信息码元先分组,在每组最后加
  • 海明校验码/汉明校验码海明码是什么?需要多少个校验位?校验位放哪里?怎么对信息位进行分组?如何纠错?总结 海明码是什么? 首先需要知道什么是奇偶校验码:在 n 位有效信息位前 或 后添加一个校验码改变整个校验...
  • CRC校验码的MATLAB和FPGA实现源程序CRC校验码的MATLAB和FPGA实现+源程序摘要:本设计首先介绍了CRC校验码工作的基本原理和生成原理,并利用Matlab软件对其进行了程序编程和编译仿真。重点分析了CRC校验码的FPGA具体...
  • 在这个小节中我们会继续探讨数据校验的问题,我们会学习海明教研嘛,那海明教研嘛又可以称为汉民教研嘛,啊,这只是一个英译的问题,因为发明这个校验码的人叫理查德汉明,也正是因为它发明了海林嘛,对于信息纠错这...
  • 校验码】数据校验码

    千次阅读 2016-11-05 22:05:59
    而另一方面在数据编码上采取编码纠码的措施,使得机器能够自己发现错误甚至纠正错误,我们把这种具有检测错误或带有自动纠错能力的数据编码称为数据校验码。其原理是在数据中加入一些校验位,组成数据校验码,通过...
  • 校验码的介绍

    2022-01-06 21:21:51
    效验如何组成?是什么影响效验的检错和纠错
  • 根据对64位数据进行检纠错处理的需要,设计一个利用8位校验码,以实现该功能的算法逻辑,并通过FPGA实现。经过仿真验证,该模块具备检测2位错误,纠正1位错误的功能,而且也能较好地满足实时性的要求,具有一定的...
  • 3.3差错控制(检错编码、纠错编码)
  • 奇偶校验码

    2017-12-30 23:07:00
    数据校验码,是数据传输时,一种常用的发现某些错误,甚至带有一些纠错功能的数据编码方法 (一)奇校验码 实现原理: 将原来合法的编码距由1增加到2 具体实现过程: 将原有的合法二进制数据增加一位 标志位 ...
  • 基于CAN总线的CRC校验码的原理与实现王鹏【摘要】CAN总线又称为控制...循环冗余校验码实现简单,误判率比较低,还具有纠错功能,在通信系统中应用较为广泛.【期刊名称】赤峰学院学报(自然科学版)【年(卷),期】2014(...
  • 海明码校验纠错原理(一)

    千次阅读 2014-09-29 05:23:11
     要采用海明码纠错,需要按以下步骤来进行:计算校验位数→确定校验码位置→确定校验码→实现校验和纠错。下面来具体介绍这几个步骤。本文先介绍除最后一个步骤的其它几个步骤。  1. 计算校验位数  ...
  • 下面进一步介绍二维码纠错相关的编码矩阵 1 范德蒙德(Vandermonde)矩阵 在线性代数中有一种矩阵称为范德蒙德矩阵,它的任意的子方阵均为可逆方阵。一个mmm行nnn列的范德蒙德矩阵定义如下,其中aia_iai​ 均不相同...
  • 这篇文章讲解了分布式存储保证可靠性常用的方法,MinIO纠错码,分布式MinIO的优点,以及虚拟机上分布式MinIO集群的搭建,并使用Nginx负载均衡来代理MinIO集群访问。
  • 写这篇文章呢,主要是想聊一下CRC的纠错功能,虽然我们谈到CRC很少说到它的纠错功能,但不代表没有,因此写一文以记录下它的纠错功能以及如何用java代码实现。 给出java代码如下 import org.junit.Test; import ...
  • 七、量子纠错码的数学描述
  • 差错控制之检错编码与纠错编码

    千次阅读 2020-04-25 14:21:01
    检错编码—奇偶校验码 检错编码–CRC循环冗余码 纠错编码—海明码 海明码:发现双比特错误,纠正单比特错 1.确定校验码的位数r 2.确定校验码和数据的位置 3.求出校验码的值 4.检错并纠错 总结 ...
  • 海明码具有检错和纠错功能,它基于奇偶校验原理,只能检查出某一位错的位置。当有多位错时,它就不适用了。 异或运算 在了解汉明码之前,先熟悉下异或运算和奇偶校验。 异或运算 异或运算,相异为1,相同为0...
  • (实例来源于百度百科) 存储单元:可存放一个机器字并具有特定存储地址的存储单位。 它不是存储器的最小单元,但一定是CPU访问存储器的最小单位。比如通常一个存储单元由八个二进制位组成(一个字节),每次CPU进行...
  • 数据校验码

    千次阅读 2016-11-14 22:55:25
    一、奇偶校验 根据被传输的一组二进制代码的数位中“1”的个数是奇数或偶数来进行校验。采用奇数的称为奇校验,反之,称为偶校验。采用何种校验是事先规定好的。通常专门设置一个奇偶校验位,用它使这组代码中“1...
  • Reed-Solomon利用范特蒙矩阵或者柯西矩阵的特性来实现纠错码功能。 Reed-Solomon编码: 把输入数据视为向量D=(D1,D2,…,Dn),编码后数据视为向量(D1,D2,…Dn,C1,C2,…,Cm),RS编码可以看做为如下图的矩阵运算...
  • 纠错码专题——线性分组(1)

    千次阅读 多人点赞 2020-04-12 02:23:53
    线性分组包括一大类的纠错编码在内,有汉明码、循环、LDPC等等,之前了解这些编码也是在网上搜搜资料,看看博客这样去学习,在网上搜索资料的时候发现一个问题,例如在看很多人写的汉明码博客时,很多人都一味...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,214
精华内容 2,085
关键字:

具有纠错功能的校验码