|
|
|
|
|
实现：为k个数据位设r个校验位，使k+r位的码字（即海明码）能发现k位中任何一位出错且可以纠正。
|
|
|
|
|
|
|
|
|
|
设r个校验位PrPr-1…P1,k个数据位Dk-1Dk-2…D0，产生的海明码为Hr+k,Hr+k-1…H1，则有如下规则。
|
|
|
|
规则1：Pi在海明码的2i-1位置，即Hj=Pi,j=2i-l；数据位则依序从低至高占据海明码中其他的位置。
|
|
|
|
规则2：海明码中的任意位都是由若干校验位来校验的。其对应关系是：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位则是由其自身来校验的。
|
|
|
|
|
|
下面以k=8对纠1位错的海明码的编码及校验原理给予说明。
|
|
|
|
|
|
当r=4时，有24≥8+4+1，可以满足2r≥k+r+1。
|
|
|
|
|
|
|
|
如：确定P4的位置，因j=2i-1=24-1=8，则有P4在H8的位置。同理得到以下位置的对应关系：
|
|
|
|
H12H11H10H9H8H7H6H5H4H3H2H1
|
|
|
|
|
|
|
|
|
|
形成Hi与P1相关的数据位有：S1=D0十D1十D3十D4十D6。
|
|
|
|
形成Hi与P2相关的数据位有：S2=D0十D2十D3十D5十D6。
|
|
|
|
形成Hi与P3相关的数据位有：S3=D1十D2十D3十D7。
|
|
|
|
形成Hi与P4相关的数据位有：D7十D6十D5十D4。
|
|
|
|
|
|
|
|
设G1=S1十P1；G2=S2十P2；G3=S3十P3；G4=S4十P4。若采用偶校验则G4~G1的值全为0时数据正确，反之有错。用对出错位取反的方法即可实现纠错。
|
|
|
|
例如，G4~G1=0111，其值为7，对应于H7（D3的位置）。将D3的值取反就实现了纠错。
|
|
|
