海明码是一种多重(复式)奇偶校验错误系统。 对信息进行逻辑编码,以便进行检错和纠错。 汉明码中使用的所有传送码字由原始信息和附加的奇偶校验比特构成。 每个这样的奇偶校验位都嵌入在发送码字的特定位置。 如果适当地实现,则即使在原始信息比特中添加奇偶校验比特,该系统也可以将具有错误的比特分离。
要导出和使用长度为m位的码字的汉明码,需要执行以下步骤:
1、确定最小校验位数k,记录D1,D2,…,Dk,每个奇偶校验位符合不同的奇偶校验规定。
2、原始信息和k个奇偶校验位一起编辑成长为m k比特的新码字。 选择k奇偶校验(0或1 )以满足所需的奇偶校验条件。
3、对接收到的信息进行必要的k个奇偶校验。
4、所有奇偶校验结果正确时,认为信息无误。
如果发现一个或多个错误,则错误位由这些检查的结果唯一确定。
校验位数的位数
确定汉明码时的基本考虑之一是确定所需的最小限度的校验位数k。 如果考虑长度为m比特的信息,附加k个奇偶校验位,则发送的全长为m k。 接收器执行k个奇偶校验,每个校验结果是真还是假。 该奇偶校验的结果可表示为k比特的二进制字,最多可确定2k种不同的状态。 这些状态必须有所有奇偶校验测试为真,是判断信息正确的条件。 然后,剩下的(2k-1 )状态可以用于判定错误代码的位置。 因此,我们得出以下关系:
2k-1m k
码字格式
虽然理论上奇偶校验位可以位于任何位置,但是按照惯例,奇偶校验位可以位于1、2、4、8、的位置。
图5表示在m=4,k=3的情况下的信息比特和奇偶校验位的分布。
码字位置
B1
B2
B3
B4
B5
B6
B7
奇偶校验位
x
x
x
信息位
x
x
x
x
复合码字
P1
P2
D1
P3
D2
D3
D4
图5汉明码中奇偶校验位和信息比特的定位
奇偶校验位的确定
这里的目的是提出编码方法以帮助理解。 (但是,我不知道编码是否是主要标准。 )
每行值等于1的各位代码不同,或者。
例如,m=4,k=3.数据位的前三行,奇偶校验位的最后三行。 也就是说
a=P1
b=p2
c=P3D1D2D3D4=0得P3=D1D2D3D4按以下计算访问同下
通过对m-k比特复合码字进行奇偶校验,确定k个奇偶校验比特。
P1位负责检查汉明码的一、三、五、七、…() P1、D1、D2、D4、…)位(包括P1本身)。
P2汉明码的第2、3、6、7、…()负责检查P2、D1、D3、D4、…)位,) (包括P2本身) )。
P3负责检查汉明码的4、5、6、7、…() P3、D2、D3、D4、…)位置,) (包括P3本身) )。
m=4,k=3,对于偶数检查的例子,进行式的偶数测试即可。 这些测试(由a、b、c表示)在图6所示各比特位置处被执行。
奇偶校验条件
码字位置
1
2
3
4
5
6
7
a
B
C
x
x
x
x
x
x
x
x
x
x
x
x
图6奇偶校验位置
因此,得到三个校验方程式和确定奇偶校验位的三个公式。
a=B1
b=B2
c=B4
如果4比特信息符号为1001,则能够使用这3个式子求出3个奇偶校验位P1、P2、P3的值。 海音码;
以上是发送方的处理
接收方还可以根据这三个检查方程对收到的信息进行相同的奇偶校验测试。
a=B1
b=B2
c=B4b5b5B7=0。
如果三个验证方程全部成立,即方程右边都为0,则没有错。 如果方程右边马上不等于0,就会有错误。 根据三个方程式右边的值,可以判断出那个是错误的。 例如,如果第三位的数字相反,则C=0(该方程式中没有B3 ),A=B=1(这两个方程式中有B3 )。 如果将a作为最低有效位,则可以构成二进制数CBA,错误位置可以简单地用二进制数CBA=011指出。
同样,如果3个方程式右边的值为001,则第1位是错误的。 如果3个方程式右边的值为100,则第4位是错误的。
哼唱的距离必须是3。
所以能纠正1位出错。而奇偶校验码的码距才是2,只能发现1位出错,但不能纠正(不知道那一位错)。无校验的码距是1,它出任何一位出错后还是合法代码,所以也就无法发现出错。这是关于海明码的经典说法,即码距为3,可以发现2位,或者纠正1位错。应满足2k-1≥m+k。
但在清华的威武的外套主编的《计算机组成与结构》(该书已成为国内的权威)中还提出了一种码距为4的海明码,可以发现2位,并且纠正1位错。应满足2(k-1)≥m+k。
由于威武的外套书上对这两种概念没有很仔细解释(特别对码距为3的海明码),过渡很突然。有些书简单抄袭时没有仔细消化,所以出现一些概念错。对于一般码距为3的海明码,应该是“可以发现2位,或者纠正1位错”,而不是“可以发现2位,并且纠正1位错”。在试题中出现过类似的错误。
若四位信息码为1001,利用这三个公式可求得三个校验位P1、P2、P3值。和海明码,如图7则表示了信息码为1001时的海明码编码的全部情况。而图8中则列出了全部16种信息(D1D2D3D4=0000~1111)的海明码。
码字位置
B1
B2
B3
B4
B5
B6
B7
码位类型
P1
P2
D1
P3
D2
D3
D4
信息码
-
-
1
-
0
0
1
校验位
0
0
-
1
-
-
-
编码后的海明码
0
0
1
1
0
0
1
图7 四位信息码的海明编码
P1
P2
D1
P3
D2
D3
D4
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
0
1
1
1
0
0
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
0
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
1
1
1
1
0
0
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
1
1
1
1
1
图8 未编码信息的海明码