|
在数据中多加入几个校验位,把数据的每一个二进制位分配在几个奇偶校验组中,当某一位出错后,就会引起有关的几个校验位的值发生变化,这不但可以发现错误,还能指出哪一位出错。
|
|
|
首先要确定校验位的个数。假设校验位个数为r,则它能表示2r个信息,用其中一个信息表示没有错误,其余2r-1个信息指出哪一位错,而错误也可能发生在校验位,因此只有k=2r-1-r个信息能用于纠正被传送数据的位数。也就是说要满足关系
|
|
|
|
注意:如要能检测与自动校正一位错,并发现两位错,那么还要加一位总校验位,则码距为4,此时应满足
|
|
|
|
按上述不等式计算,可计算出数据位k与校验位r的对应关系,如下表所示。
|
|
|
k与r的对应关系
|
|
|
设海明编码为HmHm-1…H2H1,则此海明码的编码规则是:校验位与数据位之和为m,每个校验位Pi在海明码中被分配在位号为2i-1的位置,其余各位为数据位依次排列;海明码的每一位码Hi由多个校验位校验,其关系是被校验的每一位的位号等于校验它的各校验位之和。
|
|
|
可以看一个例子。现在要传送一个字节的数据,则k=8,那么r=4,所以海明码的总位数为12,可表示为
|
|
|
|
4个校验位P4~P1对应的编号是H8、H4、H2、H1。其余为数据位Di,则有以下排列:
|
|
|
|
那么可以知道,D8处在H12的位置,12=4+8,所以由处在H4的P3和处在H8的P4检测,这样依次类推,可以得到由P1检测的数值位有D1、D2、D4、D5和D7,若用偶校验,其结果为
|
|
|
|
|
|
|
|
|
|
|
|
则校验得到的结果值S4~S1能反映海明码出错情况。按S4S3S2S1的顺序排列形成一个二进制数,转换为十进制数为j,表示Hj出错。
|
|
|