存储器之校验码（下）

前言

额，主要是校验码上篇好像布局有点问题。就拆了一个下篇。

根据上篇，我们可以得知海明码主要解决的是“规则”这个问题，主要从以下几个角度进行分析：

设欲检测的二进制代码有n位，为使其具有纠错能力，需增加k位，组成n + k的代码。为了能准确对错误定位以及指出代码没错，k需要满足以下关系： 2^k >= n + k + 1

这个不等式的意思就是：检测位的所能表示的状态需要大于等于 n + k + 1 个（这里额外加1是全正确的情况下，即000…）

放在 2^{i - 1} 的位置上，比如：

数据位按序依次填到检测位和检测位之间的间隔中去。

比如二进制代码：“0010”

用公式总结一下
第i个检测位，每检测完 2^{i - 1} ，就跳过 2^{i - 1}，再检测下一个范围 2^{i - 1}…

这样分组能有以下这些特点：

每个小组有且仅有一位被该组所独占，该位是其他组没有的。
每两个小组（g_i和 g_j）共同占有一位，该位是其他组没有的。即 g_i和 g_j 共同占有第 2^i-1 + 2^j-1 位
每三个小组（g_i、g_j和g_t）共同占有一位，该位同样是其他组没有的。即 g_i、 g_j 、g_t共同占有第 2^i-1 + 2^j-1 + 2^t-1位

比如二进制代码：“1101 1010”

通过2^k >= n + k + 1，解出k为4。需要4个检测位
我们用“?”代替检测位：??1? 101? 1010
检测位需要对要监督的位置进行异或（⊕）
- 第一位检测位：需要检查1、3、5、7、9… 根据题目判断（这里的3、5、7、9表示位置） 3 ⊕ 5 ⊕ 7 ⊕ 9 ⊕ 11 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0。所以第一位检测位是0。
- 第二位检测位：需要检查2、3、6、7… 根据题目判断 3 ⊕ 6 ⊕ 7 ⊕ 10 ⊕ 11 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 = 1
- …后面的如上所示
- 最后得出0110 1010 1010

为什么使用异或？
答：因为异或运算符正好满足相同为0，不同为1的情况

P_i表示从左到右的位数。

比如第一组，只要验证P1 ⊕ P3 ⊕ P5 ⊕ P7 ⊕ P9 ⊕ P11 = 0 即可。
如果所有的小组异或后为0，那么就代表数据没有问题

比如：
|情况| P8 | P4 | P2 | P1 |
| :-: | :-: | :-: | :-: | :-: |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 |
| 3 | 1 | 1 | 0 | 0 |

按配奇原则（偶数个数的“1”，用1表示；奇数个数的“1”，用0表示）配置1100 101的海明码

通过2^k >= n + k + 1，解出k为4。需要4个检测位
??1?100?101
计算校验位
- P1 = P3 ⊕ P5 ⊕ P7 ⊕ P9 ⊕ P11… = 1
- P2 = P3 ⊕ P6 ⊕ P7 ⊕ P10 ⊕ P11…= 1
- P4 = P5 ⊕ P6 ⊕ P7 ⊕ P12 ⊕ P13 ⊕ P14 ⊕ P15…= 0；
- P8 = P9 ⊕ P10 ⊕ P11 ⊕ P12 ⊕ P13… = 1；
新配置的汉明码为1110 1001 101

按配偶原则（偶数个数的“1”，用0表示；奇数个数的“1”，用1表示）配置0110 101的海明码

海明码通常用于一位纠错、两位检错，实际使用时需要再加一位检测码。