2017.0707.《计算机组成原理》-汉明码

1.校验起源于传输过程中造成的数据错误,为了检测和纠正这些错误,人们发明了校验。当然校验的方法很多。汉明码只是其中一种。

如果一条信息中包含更多用于纠错的位,且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果,那么我们就可以找出出错位了。在一个7位的信息中,单个位出错有7种可能,因此3个错误控制位就足以确定是否出错哪一位出错了。→这里阐述的是一种手段,通过这种手段我们对数据进行纠错。纠错是指不光能够判定是否出错,还能指出哪一位出错了。纠错的位和纠错位不一样吧?纠错的位和纠错位应该是一个意思。为什么说3个控制位足以确定7种单个位发生的错误,2的3次方等于8,是大于7的,完全可以概括7种错误。

汉明码SECDED(single error correction, double error detection 单错纠正,双错检测)版本另外加入一检测比特,可以侦测两个或以下同时发生的比特错误,并能够更正单一比特的错误(这是更为完整的汉明码的定义)。因此,当发送端与接收端的比特样式的汉明距离(Hamming distance)小于或等于1时(仅有1 bit发生错误),(1bit可以自动修改,比特样式的汉明距离?说明还有其他类型的汉明距离)可实现可靠的通信。相对的,简单的奇偶检验码除了不能纠正错误之外,也只能侦测出奇数个的错误。→汉明码可以侦测两个或以下同时发生的比特错误,并能够更正单一比特的错误。这是指两位(?)或者一位的比特错误都能查出来,并且对于一位的比特错误还能纠正。这样理解对么?同时,汉明码比简单奇偶校验更进一步。

这里还产生一个问题,纠错的位和检测比特之间是否存在关系,只是说法不一样么?

2.还是看不懂汉明码,这里有很多基础概念完全不认识。

汉明码是一种线性分组码。线性分组码是指将信息序列划分为长度为k的序列段,在每一段后面附加r位的监督码,且监督码和信息码之间构成线性关系,即它们之间可由线性方程组来联系。这样构成的抗干扰码称为线性分组码。→看来信息序列是被划分为好多序列段,长度不知道,所以称为K?每一序列段和后面的监督码之间都有固定的线性关系?

下面来仔细剖析一下汉明码和汉明距离

对于汉明码的众多基本概念,不同的人对他们有不同的叫法。

设码长为n,信息位长度为k,监督位长度为r=n-k。如果需要纠正一位出错,因为长度为n的序列上每一位都可能出错,一共有n种情况,另外还有不出错的情况,所以我们必须用长度为r的监督码表示出n+1种情况。而长度为r的监督码一共可以表示2^r种情况。因此
2^r >= n + 1, 即r >= log(n+1)→这里有一个问题,K应该是指所有信息位的总长,而不是某一小段信息位的长度吧?同样监督位也是如此。

我们以一个例子来说明汉明码。假设k=4,需要纠正一位错误,则
  2^r >= n + 1 = k + r + 1 = 4 + r + 1
解得 r >= 3。我们取r=3,则码长为3+4=7。用a6,a5,…a0表示这7个码元。用S1,S2,S3表示三个监关系式中的校正子。我们作如下规定(这个规定是任意的):

   S1  S2  S3    错码的位置
   0   0   1        a0
   0   1   0        a1
   1   0   0        a2
   0   1   1        a3
   1   0   1        a4
   1   1   0        a5
   1   1   1        a6
   0   0   0        无错
  
按照表中的规定可知,仅当一个错码位置在a2,a4,a5或a6时校正子S1为1,否则S1为0。这就意味着a2,a4,a5,a6四个码元构成偶校验关系:
   S1 = a6⊕a5⊕a4⊕a2   (1)式
同理,可以得到:
   S2 = a6⊕a5⊕a3⊕a1   (2)式
   S1 = a6⊕a4⊕a3⊕a0   (3)式
在发送信号时,信息位a6,a5,a4,a3的值取决于输入信号,是随机的。监督为a2,a1,a0应该根据信息位的取值按照监督关系决定,即监督位的取值应该使上述(1)(2)(3)式中的S1,S2,S3为0,这表示初始情况下没有错码。即

a6⊕a5⊕a4⊕a2 = 0
   a6⊕a5⊕a3⊕a1 = 0
   a6⊕a4⊕a3⊕a0 = 0
  
由上式进行移项运算,得到:

  
   a2 = a6⊕a5⊕a4
   a1 = a6⊕a5⊕a3
   a0 = a6⊕a4⊕a3
  
已知信息位后,根据上式即可计算出a2,a1,a0三个监督位的值。

接收端受到每个码组后,先按照(1)~(3)式计算出S1,S2,S3,然后查表可知错码情况。

例如,若接收到的码字为0000011,按照(1)~(3)计算得到:
S1 = 0, S2 = 1, S3 = 1
查表可得在a3位有一个错码。

这种编码方法的最小汉明距离为d=3,所以这种编码可以纠正一个错码或者检测两个错码。

→这上面具体讲述了汉明码的运作流程。

3. 汉明距离

在一个码组集合中(这是一个什么样的码组集合在一起?所有出错的和没出错的?),任意两个码字之间对应位上码元取值不同的位的数目定义为这两个码字之间的汉明距离。即
       d(x,y)=∑x[i]⊕y[i],这里i=0,1,..n-1,x,y都是n位的编码,⊕表示异或
例如,(00)与(01)的距离是1,(110)和(101)的距离是2。
在一个码组集合中,任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。
最小汉明距离越大,码组越具有抗干扰能力。

下面我们用d表示码组的最小汉明距离。
(1)当码组用于检测错误时,设可检测e个位的错误,则
  d >= e + 1
设有两个距离为d的码字A和B,如果A出现了e个错误,则A变成了以A为圆心,e位半径的球体表面的码字。为了能够准确地分辨出这些码字既不是A也不是B,那么A误码后变成的球面上的点与B至少应该有一位距离(如果B在球面上或在球面内部则无法分辨出到底B是不是A的错误码),即A与B之间的最小距离d >= e+1。→这汉明距离是由两个编码构成的,它是用来对两个编码进行检测的?

(2)若码组用于纠错,设可纠错t个位的错误,则
  d >= 2t+1
设有码字A和B,如果A出现了t个错误,B也出现了t各错误,则A码变成以A为圆心,t为半径的球面上的码字;B码变成以B为圆心,t为半径的球面上的码字。为了在出现t个错之后仍能分辨一个码字到底是属于A的错码还是属于B的错码,A,B为球心的两个球面应该不相交,即球心A,B之间距离应该大于2t,所以d >= 2t+1。

(3)如果码组用于纠正t个错,检测e个错,则
  d >= e+t+1, 这里e>t
这种检错纠错方式结合的情况同上述两个情况类似。当码字出现t个或者小于t个错时,系统按照纠错方式工作。当码字出现超过t个错而小于等于e个错时,系统按照检错方式工作;当A出现e个错,B出现t个错时,既要纠正B的错,又要发现A的错,则以A为球心,e为半径的球和以B为球心,t为半径的球应该不相交,所以A,B之间的距离应该大于等于e+t+1,即d>=e+t+1。

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注