软件设计师学习-海明码

wiki

海明码（Hamming Code）是由贝尔实验室的 Richard Hamming 设计的，是一种利用奇偶校验来检错和纠错的校验方法。方法是在数据位插入 k 个校验位，通过扩大码距来实现检错和纠错。

1. 理论构成

设数据位有 n 位置，校验位有 k 位，则 n 与 k 需要满足关系：2k - 1 ≥ n + k。

按照如下规则进行编码：

设 k 个校验位为 P_k,P_k-1,…,P₁，n 个数据位为 D_n-1,D_n-2,…,D₁,D₀，对应的海明码为 H_n+k,H_n+k-1,…,H₁，那么：

• P_i 在海明码的第 2^i-1 位置，即 H_j=P_i，且 j=2^i-1，数据位则依序从低到高占据海明码中剩下的位置
• 海明码中任何一位都是由若干个校验位来校验的。其对应关系如下：被校验的海明码的下标等于所有参与校验该位的校验位的下标之和，而校验位由自身校验。

2. 理论设计

对于 8 位的数据位，可计算，其校验位需要 4 个（2⁴ - 1 = 15 ≥ 8 + 4 = 12）。由此可知：

• 数据位可表示为 D₇,D₆,…,D₀
• 校验位可表示为 P₄,P₃,P₂,P₁
• 海明码可表示为 H₁₂,H₁₁,…,H₁

编码过程如下：

1. 确定数据位、校验位在海明码中的位置：
   

2. 确定校验关系，默认为偶校验（奇校验需要取反即可）：
   

3. 检验错误，对海明码的数据进行差错检查很容易，如下：

若采用默认偶检验，则 G₄G₃G₂G₁ 全为 0 时表示接收到的数据无错误（奇校验全为 1）。当不全为 0 时，可判断发生了错误，而且它的十进制指出了发生错误的位置，如 G₄G₃G₂G₁ = 1010，说明 H₁₀(D₅) 出错，可将其取反来纠正错误。

3. 实战

假设一个数据为 11001001，可知需要 4 个校验位。数据位如上，现在计算校验位。根据上述说明，使用异或计算可求出相应校验位：

P1 = D0 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0
P2 = D0 ⊕ D2 ⊕ D3 ⊕ D5 ⊕ D6 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 = 1
P3 = D1 ⊕ D2 ⊕ D3 ⊕ D7      = 0 ⊕ 0 ⊕ 1 ⊕ 1     = 0
P4 = D4 ⊕ D5 ⊕ D6 ⊕ D7      = 0 ⊕ 0 ⊕ 1 ⊕ 1     = 0

异或求值也可以换一种计算方式，把校验位的 0 替换为 *，写成通配符形式：

将对应位数的的海明码，写成二进制形式：

将与通配符匹配的数据写在其下方，可见与异或求值一致：

纠错计算就是用纠错码与相应位数异或，由于该纠错码就是使用相应位数计算而来，因此值是一样的，所以异或结果必然是 0：

G1 = P1 ⊕ D0 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0
G2 = P2 ⊕ D0 ⊕ D2 ⊕ D3 ⊕ D5 ⊕ D6 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
G3 = P3 ⊕ D1 ⊕ D2 ⊕ D3 ⊕ D7      = 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1     = 0
G4 = P4 ⊕ D4 ⊕ D5 ⊕ D6 ⊕ D7      = 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1     = 0