海明码速算

按 $2^k-1$ 切块#

从左往右，第 $k$ 块长 $2^k-1$ 位，也就是 1、3、7、15……，最后一块不够长，有多少算多少。

比如拿到手的原始数字是 1110011011011：

$$\underbrace{1}_{\text{第1块}} \;\Big|\; \underbrace{110}_{\text{第2块}} \;\Big|\; \underbrace{0110110}_{\text{第3块}} \;\Big|\; \underbrace{11}_{\text{第4块}}$$

校验位就比块数多一个。这里 4 块，要 5 个校验位。

第二步：每个校验位取数#

例 1：101101#

$$\underbrace{1}_{\text{第1块}} \;\Big|\; \underbrace{011}_{\text{第2块}} \;\Big|\; \underbrace{01}_{\text{第3块}}$$

3 块，4 个校验位。

• $P_8$：第 3 块全取。1 个 1，$P_8 = 1$。
• $P_4$：第 2 块全取；第 3 块不够跳 3。2 个 1，$P_4 = 0$。
• $P_2$：第 1 块全取；第 2、3 块跳1取2。4 个 1，$P_2 = 0$。
• $P_1$：每块跳0取1，跳1取1。2 个 1，$P_1 = 0$。

注意： 跳和取的规则和 $2^k$ 有关，比如 $P_8$ 在分好的块里本来是跳 8 取 8。但每块开头的那个校验位（$P_4, P_8, P_{16}, \dots$）帮你把本来该跳过的那一组位置“吃掉”了 1 个，所以 $P_8$ 先跳 7 取 8，再继续跳 8 取 8。

还有一点：海明码的分块长度在数学上是天然对齐的，任何一块的末尾都正好落在某次“取 $2^k$”的最后一位，所以不用担心取到一半被块尾打断（最后一块不满的除外，有多少取多少）。

例 2：1011010011#

$$\underbrace{1}_{\text{第1块}} \;\Big|\; \underbrace{011}_{\text{第2块}} \;\Big|\; \underbrace{010011}_{\text{第3块}}$$

3 块，4 个校验位。

• $P_8$：第 3 块全取。3 个 1，$P_8 = 1$。
• $P_4$：第 2 块全取；第 3 块跳3取4。4 个 1，$P_4 = 0$。
• $P_2$：第 1 块全取；第 2、3 块跳1取2，跳2取2。5 个 1，$P_2 = 1$。
• $P_1$：每块跳0取1，跳1取1。3 个 1，$P_1 = 1$。

例 3：1110011011011#

$$\underbrace{1}_{\text{第1块}} \;\Big|\; \underbrace{110}_{\text{第2块}} \;\Big|\; \underbrace{0110110}_{\text{第3块}} \;\Big|\; \underbrace{11}_{\text{第4块}}$$

4 块，5 个校验位。

• $P_{16}$：第 4 块全取。2 个 1，$P_{16} = 0$。
• $P_8$：第 3 块全取；第 4 块不够跳 7。4 个 1，$P_8 = 0$。
• $P_4$：第 2 块全取；第 3 块跳3取4；第 4 块不够跳 3。4 个 1，$P_4 = 0$。
• $P_2$：第 1 块全取；第 2、3、4 块跳1取2，跳2取2。6 个 1，$P_2 = 0$。
• $P_1$：每块跳0取1，跳1取1。5 个 1，$P_1 = 1$。