| x
x
x
x
x
x
x
x
x
图6 奇偶校验位置
因此可得到三个校验方程及确定校验位的三个公式：
A=B1⊕B3⊕B5⊕B7=0 得P1=D1⊕D2⊕D4
B=B2⊕B3⊕B6⊕B7=0 得P2=D1⊕D3⊕D4
C=B4⊕B5⊕B6⊕B7=0 得P3=D2⊕D3⊕D4
若四位信息码为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 未编码信息的海明码
上面是发送方的处理
在接收方，也可根据这三个校验方程对接收到的信息进行同样的奇偶测试：
A=B1⊕B3⊕B5⊕B7=0；
B=B2⊕B3⊕B6⊕B7=0；
C=B4⊕B5⊕B5⊕B7=0。
若三个校验方程都成立,即方程式右边都等于0，则说明没有错。若不成立即方程式右边不等于0，说明有错。从三个方程式右边的值，可以判断那一位出错。例如，如果第3位数字反了，则C=0(此方程没有B3），A=B=1（这两个方程有B3）。可构成二进数CBA，以A为最低有效位，则错误位置就可简单地用二进数CBA=011指出。
同样，若三个方程式右边的值为001，说明第1位出错。若三个方程式右边的值为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位错”。在试题中出现过类似的错误。
四、循环冗余校验码
在串行传送（磁盘、通讯）中，广泛采用循环冗余校验码（CRC）。CRC也是给信息码加上几位校验码，以增加整个编码系统的码距和查错纠错能力。
CRC的理论很复杂，一般书上只介绍已有生成多项式后计算校验码的方法。检错能力与生成多项式有关，只能根据书上的结论死记。
循环冗余校验码（CRC）的基本原理是：在K位信息码后再拼接R位的校验码，整个编码长度为N位，因此，这种编码又叫（N，K）码。对于一个给定的（N，K）码，可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码，而G(x)叫做这个CRC码的生成多项式。
校验码的具体生成过程为：假设发送信息用信息多项式C(X)表示，将C(x)左移R位，则可表示成C(x)*2R，这样C(x)的右边就会空出R位，这就是校验码的位置。通过C(x)*2R除以生成多项式G(x)得到的余数就是校验码。
上一页 [1] [2] [3] [4] [5] [6] 下一页 | 
