对海明码的理解

1、对海明码的理解海明码是一种多重（复式奇偶检错系统。它将信息 用逻辑形式编码，以便能够检错和纠错。用在海明码中的全 部传输码字是由原来的信息和附加的奇偶校验位组成的。每 一个这种奇偶位被编在传输码字的特定位置上。实现得合适 时，这个系统对于错误的数位无论是原有信息位中的，还是 附加校验位中的都能把它分离出来。一个n位二进制数位串在传输过程中哪一位都有 出错的可能，也就是说有 n个发生错误的可能性。针对此情 况，如果发送方只抽出其中一位制置奇偶校验位值，以便对 其它位进行偶校验或奇校验，虽然也能检错，但无法确定错 码的位置，不能纠错。如果发送方抽出其中r位（放在1,2, 4, 8, 16位上），给

2、每个位制置奇偶校验位值，以便对从其它位中选择的有差异的r个位组进行偶校验或奇校验，这样，就能用含 r个校验位值的逻辑组合（其所在位置 可以不连续，但是，其在逻辑上是连续的）所衍生出的2r种状态对可能发生的错误进行相应范围的检测。进一步思考： 如果让2r种可能发生的状态中除去一种状态反映整个位串传 输正确外，剩下的 2r-1种状态一一对应地反映位串中可能发 生的n种错误，那么，对r会有多大的数量要求呢？显然， r 应满足下列关系式：2r-1>=n （1这样，r个校验位所衍生出的 2r种状态才能覆盖 可能产生的n种错误。每种错误发生时才不至于漏检。从n中扣出r个校验位n-r=k，这k个位是信

3、息 位。n=k+r，代入（1）式得：2r-1>= k+r (2移项得：2r- r>= k+1 (3按（3式进行试算（试算不包括 ">”最小值）表101245111226275758120121247r12345678k014112657120247根据经验表2r12345678此即r以其所衍生出的状态能覆盖的信息位数 量。反过来，从k的数量，可以倒推需要多少校验位对其进 行检测。知道了信息位数量与校验位数量的关系后，怎样编海明码 呢？用一道例题加以说明。例题现有8位二进制数信息位串10011101等待传输，问怎样 将海明校验位编入以资校验？根据前述，8个信息位要有

4、位串长就是8+4=12位。表34个校验位来检测，于是整个位置序1 2 3 4 5 6 79 10 11 12 检逻比特名辑关系(AAAAAAAAAA9A1A1101234567801校验位(A AAA2分布20 137信息位 (3A AAA A A9 A1 A1A1(6(7(8=1A1S1=1A1=0A1A1说明：表3表示海明码内部的逻辑关系。它反映了海明码是按什 么样的逻辑被制造出来的。(1按112的顺序给二进数制位串各位上的比特启名。(2把1, 2, 4, 8位(即2i,i=0,1,2位)安上奇偶校验比特 的名。(3把非2i位安上信息比特的名。(4按名位显示 10011101，如，A2的值

5、是10011101的第一 个“ 1”依此顺推。(5 A0的校验对象：每跳 1位拉入1个对象，直到尽头。校 验对象的值模2加之和为A0的值。(6 A1的校验对象：它旁边的 A2，而后每跳2位拉入2个对 象，直到尽头。校验对象的值的模2加之和为A1的值。(7 A3的校验对象：它旁边的 A4, A5 , A6 ,而后每跳4位 拉入4个对象，直到尽头。校验对象的值的模 2加之和为A3 的值。(8 A7的校验对象：它旁边的 A8 , A9 , A10 , A11，已到尽 头。校验对象的值的模2加之和为A7的值。(5(6(7(8为什么采取这样的逻辑方法(以 2i位校验 非2i位)选校验对象？为的是标准统一

6、、好记，便于发送方和接收方按同一个规则计算校正因子 S,从而便于接收方检错纠错。故此说明。(9将各校验位的值按相应位插入，形成海明码。(10 S0是 A0和 A0的校验对象模 2加之和，为 0； S1是A1和A1的校验对象模 2加之和，为 0; S2是A3和 A3的校验对象模2加之和，为0; S3是A7和A7的校验对象 模2加之和，为0。如果发生了不为 0则表明：不是校验者出 错就是被校验者出错。这个海明码一个12位的二进数制位串中，隐含着可资互相印证的逻辑关系：一是校验与被校验(反 过来是生成被生成)的关系一一被校验者对校验者也 有产生被产生作用。因为采取偶校验法，校验位值与 被校验的信息位

7、值群之奇偶性有同一性。当这个同一 性被破坏时就会想到让被校验的信息位值群与校验位 值互相印证；二是校正因子与偶校验双方的关系；三 是按取位数量不同跳拉校验对象法组成的校验组之间 的关系。正是这些关系为检错纠错提供了基础。接收方收到海明码后，按编码规则计算 S，若S3= S2= S1 = S0=0，则说明传输无误。反之，只要其中有一个为1便说明传输有误。错误分析：一、一个错儿影响一个 S假设第一位 A0在传输中由“ 1变成了 “0”导致 接收方在验算时 S0由“0变成了 “ 1”一他时接收方便知如表 3的第（5）行所示的逻辑关系中出了错 值。但到底是 A0错了还是第（5）行里的其他位值 出了错？

8、尚不能确定，要分析。这时如果S3=S2=S1=0就为找错提供了印证分析基础：因为S仁0，印证了 A2、A10传输无误；因为 S2=0，印证了 A4、 A6传输无误；因为 S3=0，印证了 A8、A10传输无 误；合计印证了A2、 A4、A6、A8、A10传输无误，而这正说明（5）行里的信息位值群正确，从而 挤認出A0错了。纠错：把A0由“ 1改成“ 0”为了以后省却印证分析的麻烦，不妨对这种12位海明码制定一个固定印证表指示：当S3 S2 S1S0=0001 时，A0 错误。A1、A3、A7传输错误均可用此印证分析方 法找出和纠正，可定一个固定印证表指示：当S3S2 S1 S0=0010 时，

9、A1 错误；当 S3 S2 S1 S0=0100 时，A3错误；当 S3 S2 S1 S0=1000时，A1错误。二、一个错儿影响两个 S假设第3位A2在传输中由“ 1变成了 “0”导致接收方在验 算时S0变成了 “ 1” S1变成了 “ 1”对照表3所示的横竖逻辑关系看，这个错误发生 过程就好似是这样：一枚火箭一一1变0 （在表3第3列底部），分出两个一模一样的弹头一一A2 （竖看），击中两个不同的目标一一S0和S1 （横看）”。找错过程正相反：从被 破坏的两个不同的目标 一一S0和S1，找两个一模一样的弹头一一A2,进而找出错比特值 一一0。当然，这是循着逻辑关 系找错，（表3只是说明了逻

10、辑关系）。不应理解成循表找 错。纠错：把A2由“0改成“ 1”并在印证表里填上当 S3 s2 si sO=ooii 时，a2 错误。按以上方法，我们同样可以发现和纠正第5位A4的错误，并在印证表里填上当s3 s2 si s0=0ioi时，指示a4错误；可以发现和纠正第6位a5的错误，并在印证表里填上当s3 s2 si s0=0iio时，指示a5错误；可以发现和纠 正第9位A8的错误，并在印证表里填上当S3 s2 sis0=i00i时，指示A8错误；可以发现和纠正第 io位A9的 错误，并在印证表里填上当s3 s2 si s0=i0io时，指示a9错误；可以发现和纠正第i2位Aii的错误，并在印

11、证表里填上当s3 s2 si s0=iio0时，指示Aii错误。以便对这些 可能发生的错误做到直接印证。三、一个错儿影响三个 s假设第7位A6在传输中由“i变成了 “0”导致接收 方在验算时so变成了 “i” si变成了 “i” 2变成了 a丄力i .对照表3看，这个错误发生过程就好似是这样：一枚火箭一一i变0,分出三个一模一样的弹头 一一A6,击 中三个不同的目标 一一s0、si和s2”。找错过程正相反：从被破坏的三个不同的目标 一一S0、S1和s2,找三个一模 一样的弹头一一a6,进而找出错比特值 一一0。纠错：把a6由“0改成“ 1”并在印证表里填上当s3 s2 si s0=oiii时，

12、指示a6错误。按以上方法，我们可以发现和纠正第11位A10的错误，并在印证表里填上当 S3 S2 S1 s0=1011时，指示 A10错误.用一、二、三所准备的印证表项制表如下：印证表表4S3 S2 S1S0000100100011010001010110出错A0A1A2A3A4A5S3 S2 S1S0011110001001101010111100出错A6A7A8A9A10A11如果在传输中同时发生两个错误，就很不好办。例如，A0错变为0，A1也错变为0，接收方在验算时发现 S仁s0=1， 如果按印证表查对则判为0011 A2错误，结果会造成错上加错的情形，如同法官错判了好人，放走了原凶一样。为 避免此种情况发生还是应该用印