[计算机组成原理] 海明校验码
海明校验码是一种可以纠正一位差错的编码，采用分组奇偶校验
编码
1.计算校验位的位数
假设信息位为k位，增加r位校验位，构成n=k+r位海明码。因为海明码要纠正一位错误，n位每一位错加上n位全对共n+1种状态，用二进制编码，r位校验位可以表示2r个状态，则r满足：2r≥k+r+1
以下为几种k和r的对应关系：
| k | r最小值 |
|---|---|
| 1~4 | 3 |
| 5~11 | 4 |
| 12~26 | 5 |
2.确定有效信息和校验位的位置
设数据位为Di,校验位为Pj,构成的海明码的位置为Hk,海明码要求第i组的校验位必须位于2i-1的位置，比如1、2、4、8......
举个例子，k=8,r=4
| H12 | H11 | H10 | H9 | H8 | H7 | H6 | H5 | H4 | H3 | H2 | H1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| D8 | D7 | D6 | D5 | P4 | D4 | D3 | D2 | P3 | D1 | P2 | P1 |
3.分组
若Di=Hj,则Di参加那些位号之和(拆成2的幂)等于j的校验位的分组校验
举几个例子：
D1 在海明码中的位置为H3,3=1+2,D1参加第一组和第二组的校验
D2在海明码中的位置为H5,5=1+4，D2参加第一组和第四组的校验
D3在海明码中的位置为H6,6=2+4，D3参加第二组和第四组的校验
写成二进制，规律更明显：
| 数据位 | 海明码位置 | 海明码位置下标二进制 |
|---|---|---|
| D8 | H12 | 1100 |
| D7 | H11 | 1011 |
| D6 | H10 | 1010 |
| D5 | H9 | 1001 |
| D4 | H7 | 0111 |
| D3 | H6 | 0110 |
| D2 | H5 | 0101 |
| D1 | H3 | 0011 |
P1校验第一组，包含的数据的海明码位置的二进制的第一位是1:D7D5D4D2D1
P2 校验第二组，包含的数据的海明码位置的二进制的第二位是1:D7D6D4D3D1
P3校验第三组，包含的数据的海明码位置的二进制的第三位是1:D8D4D3D2
P4:校验第四组，包含的数据的海明码位置的二进制的四位是1:D8D7D6D5
4.计算校验位，得出海明码
假设是偶校验，加上校验位使该组的1的个数为偶数，可以用异或计算
P1= D7⊕D5⊕D4⊕D2⊕D1
P2 =D7⊕D6⊕D4⊕D3⊕D1
P3=D8⊕D4⊕D3⊕D2
P4=D8⊕D7⊕D6⊕D5
算出校验位后，按2中的位置填入相应数字，得到海明码
译码
在接收端收到海明码后，按上述分组检验每组的正确性,每组异或为0则该组没出错，否则该组出错
S4=P1⊕ D7⊕D5⊕D4⊕D2⊕D1
S3=P2 ⊕D7⊕D6⊕D4⊕D3⊕D1
S2=P3⊕D8⊕D4⊕D3⊕D2
S1=P4⊕D8⊕D7⊕D6⊕D5
若S4S3S2S1=0000,则没有出错，将信息位提取出来使用
若S4S3S2S1不是全零,如S4S3S2S1=1010，则1010对应的十进制10，海明码H10(数据D6)出错，将H10取反即可
若十进制对应的位置是校验位出错，不需要纠正，因为我们只需要确保数据不出错就可以
思考：为什么这样分组
四位数据，r=3，海明码H7H6...H1中，H1H2H4是校验位，3=1+2，5=1+4，6=2+4，7=1+2+4
第一组:1 3 5 7
第二组：2 3 6 7
第三组：4 5 6 7
校验时每组异或，计算S3S2S1,全0则没出错，001则第一组出错，出错的位是第一组独有的那一位--第一位，刚好是001的十进制，101则1、3组错，出错的是1、3组共有，其他组没有的那一位--5，刚好是101的10进制