存储器的校验

编码的最小距离

指任意两组合法代码之间二进制位数的最小差异。

汉明码的生成

思路：分组 + 奇偶校验

• 分组：
  • $C_1$ 检测 $g_1$ 组，包含所有 x..xxxx1 的位：1，3，5，……
  • $C_2$ 检测 $g_2$ 组，包含所有 x..xxx1x 的位：2，3，6，7，10，11，……
  • $C_4$ 检测 $g_3$ 组，包含所有 x..xx1xx 的位：4，5，6，7，12，13，……
  • $C_8$ 检测 $g_4$ 组，包含所有 x..x1xxx 的位：8，9，10，11，12，13，14，15，24……

当原始数据有 $n$ 位时，汉明码的位数 $k$ 满足 $2^k\geqslant n+k+1$。

• 插入
  • 将 $C_i$ 插入在汉明码的 $i$ 位。
• 校验
  • 每个检测位 $C_i$ 去检测自己对应的组 $g_{\log_2i+1}$内的「1」的个数：
    • 配奇原则：若有偶数个 1 则校验为 1；
    • 配偶原则：若有奇数个 1 则校验为 1。
• 例如：0101，配偶校验。
  • 分组插入后： C1 C2 0 C4 1 0 1。
  • 校验：
    • $g_1$ 包含 C1 0 1 1，配成偶数个 1，$C_1$ 为 0。
    • $g_2$ 包含 C2 0 0 1，配成偶数个 1，$C_2$ 为 1。
    • $g_4$ 包含 C4 1 0 1，配成偶数个 1，$C_4$ 为 0。
  • 最终结果为 0100101。

汉明码的校验

汉明码可以纠正一位错。方法如下：

记 $P_i$ 为 $C_i$ 所在那一组的检测位。对于配偶原则，如果有奇数个 1，那么检测位为 1。写出所有的检测位，例如 0100111：

• $P_1$ 检测 0100111，共 2 个「1」，故为 0。
• $P_2$ 检测 0100111，共 3 个「1」，故为 1。
• $P_4$ 检测 0100111，共 3 个「1」，故为 1。

然后将各个检测位 逆序 排列，得到出错的位号—— $P_4P_2P_1=110_2=6_{10}$，即第 6 位出错。

Cache / 缓存

「Cache」的读音是 [kæʃ]，和 cash（钞票）一词的读音一致，大家不要读错了。