计算机组成原理学习日记3（海明码的计算）

1、根据有效信息位数判断校验位的个数

这里仅仅讨论单码错误的海明码。因为只讨论单码错误的情况，设有效信息的位数是7位，所以有效信息传输到对端的情况就有8种，包括每一位都出现一次错误加上所有都没有错的情况。

这里得出公式 2^m=k+m+1,m为校验码的位数，k为有效信息的位数。只要得到有效信息位数k，我们就可以得到m的最小个数，也就是最小的校验码的位数。如7位的有效信息，那么它的校验位的个数就是4位。

2、将校验位数加上有效信息位数进行排序，并将校验位安置到2^i序号上

我们用p1---p4代表4个校验码，用a1---a7代表七个有效信息。

比如7位的有效信息与4位的校验位，一共是11位，那么对其进行排序就是：

1    2   3   4    5   6    7   8   9  10   11

p1 p2  a1 p3  a2 a3 a4 p4 a5 a6  a7

我们用校验位对应的序号去组合成a1---a7对应的序号。

p1(1)   p2(2)   p3(4)   p4(8)

a1(3): p1, p2

a2(5): p1, p3

a3(6): p2, p3

a4(7): p1,p2 ,p3

a5(9): p1, p4

a6(10): p2, p4

a7(11): p1, p2, p4

我们将p1---p4每个校验位所处的所有有效信息位做一个总结：

p1: a1,a2,a4,a5,a7

p2: a1,a3,a4,a6,a7

p3: a5,a6,a7

p4: a9,a10,a11

每个校验位都对应着一个由有效信息组合而成的二进制数，我们对每个分组的每个有效信息位做异或的运算即可以得到对应的偶校验位的二进制取值。如果要做奇校验位的海明码，则需要对上面的操作结果做取反操作，就可以得到所有奇校验位。然后我们再将其填入之前的序列中，即可得到一个海明码序列。

3、接收方如何进行检错和纠错

同样的这里仅仅讨论单码错误的海明码。

接收方在接收到奇校验或者偶校验的海明码之后，根据它的总长度可以判断出它的有效位数，于是又做发送发同样的排序的操作：

1    2   3   4    5   6    7   8   9  10   11

p1 p2  a1 p3  a2 a3 a4 p4 a5 a6  a7

同样的我们用校验位对应的序号去组合成a1---a7对应的序号。

p1(1)   p2(2)   p3(4)   p4(8)

a1(3): p1, p2

a2(5): p1, p3

a3(6): p2, p3

a4(7): p1,p2 ,p3

a5(9): p1, p4

a6(10): p2, p4

a7(11): p1, p2, p4

同样的我们将p1---p4每个校验位所处的所有有效信息位做一个整合：

p1: a1,a2,a4,a5,a7

p2: a1,a3,a4,a6,a7

p3: a5,a6,a7

p4: a9,a10,a11

这时我们要将得到的奇校验位或者偶校验位加入到对应的上述的分组中，如下：

E1：p1 a1,a2,a4,a5,a7

E2：p2 a1,a3,a4,a6,a7

E3：p3 a5,a6,a7

E4：p4 a9,a10,a11

然后根据发送过来的奇校验或者偶校验海明码的对应的位信息带入上述的分组，如果是偶校验的海明码就直接做异或运算即可，得到的结果为E4 E3 E2 E1（结果是倒序的），如果E4 E3 E2 E1是0000则没有出现错误，如果出现了单码错误，则E4 E3 E2 E1所组成的二进制数就代表着对应的哪一位出现了错误，比如0010，就代表从左往右数第二位出现了错误。如果是奇校验的海明码在对分组进行了异或运算后，还需要对结果进行取反操作，然后同样的，若E4 E3 E2 E1位0000则没有出错，否则E4 E3 E2 E1组成的数就是对应出错的位数。