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] 下一页 没有相关教程
|