常用校验码(奇偶校验,海明校验,CRC)学习总结 (2)

常用校验码(奇偶校验,海明校验,CRC)学习总结

我们来看看这个表是怎么画出来的

首先数据位和校验位的位置我们通过公式可以得出

同列数据位所占的位置对应的行的值之和为列的值。举个例子,如D1,所在列为3,所在行分别为20和21,即1和2,满足式子1+2=3。

校验位的值为同行数据位相异或得到,至于P5,则是由所有数据位和校验位一起异或得到。

3.海明校验码判断修复错误

下面引入一个错误字S的概念
其实错误字S也就是传输前后分别求的校验位的异或值,奇偶校验码只要看一个错误字,而海明校验码则要考虑多个错误字。
S4 ~ S1为全0,说明没错. S4 ~ S1不为全0,说明有错. S5=1说明1位出错,而S5=0说明2位错,不再有效,且不能查出是哪2位出错。
S4~S1的编码值对应的则是出错的海明码位号(不太清楚图表可以返回上面的表格对照):
如1100,对应D8出错
如1011,对应D7出错
如1010,对应D6出错
如1001,对应D5出错......

Tip:我们通过观察8个数据位4个校验位的海明校验码,发现,若一位出错,则至少有两组校验码的生成收到影响,故我们得到其码距为3,根据码距与检错、纠错能力的关系可以得出该校验码能发现两位错,或修改一位错。

4.校验码位数的确定

前面看完后,一定有人会有疑问,为什么八位数据位我要四位或者五位校验位,三位不行么?六位不行么?那么,请继续看看下面

假定数据位数为n,校验码为k位,则故障字位数也为k位。k位故障字所能表示的状态最多是2K,每种状态可用来说明一种出错情况。

若只有一位错,则结果可能是:
数据中某一位错 (n种可能)
校验码中有一位错 (k种可能)
无错 ( 1 种可能)

假定最多有一位错,则n和k必须满足下列关系:

2^k≥1+n+k, 即:2^k-1≥n+k

所以当数据有8位时,校验码和故障字都应有至少4位。

5.分组方式的选择

看了前面,可能有人会对校验位的位置选择有疑问,为什么要符合公式2^(i-1) i=1,2...?上述的表格为什么要那样写?
首先,我们知道,数据位是和校验位一起被储存的,通过将他们按照某种方式排列成一个n+k的码字,将该码字上的每一位出错位置和故障字的数值建立联系,那么我们就能通过故障字的值来判断哪一位发生了错误

如果故障字全为0,则说明没有错误

如果故障字有且只有一位为1,则表示是校验位中发生错误,不需要矫正

如果故障字中有多位为1,则表示有一个数据位出错,其出错位置由故障字的值来确定

以一个八位的数据为例,该数据有四个校验位,在第二条规则中,我们可以知道,故障字的值为0001,0010,0100,1000这四种情况,对应四个校验位P1,P2,P3,P4发生错误,故我们将这四个校验位分别位于码字的第0001(1),0010(2),0100(4),1000(8)位,按照最后一个规则,将其他多位为1的情况作为八位数据M1-M8发生错误。故数据位M1-M8分别位于码字的第0011(3),0101(5),0110(6),0111(7),1001(9),1010(10),1011(11),1100(12)位,排列为M8M7M6M5P4M4M3M2P3M1P2P1

六.循环冗余码(CRC码) 1.为什么大批量数据不用奇偶校验?

在每个字符后增加一位校验位会增加大量的额外开销;尤其在网络通信中,对传输的二进制比特流没有必要再分解成一个个字符,因而无法采用奇偶校验码。

2.模2运算

在介绍CRC码之前,有必要介绍下计算CRC码必要的模2运算:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzxdpp.html