汉明码的原理及其应用

汉明码的原理及其应用

1 异或运算的应用与案例

例题： 在给定一个的整型数组中，已知其中只有一种数出现了奇数次，其余数出现了偶数次。现在需要设计一个算法，来找到该出现了奇数次的数具体是多少。（限制时间复杂度为：O(N)，空间复杂度为：O(1)） 题解： 异或运算原理：

0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;

假设给定2个二进制数 101100 110011 构建数组 [101100, 110011, 101100] 通过疑惑运算表计算数组遍历异或流程

  101100 [0]
^ 110011 [1]
————————————————————
= 011111     → 结果
^ 101100 [2]
————————————————————
= 110011 [2] → 奇数次

类比推理，若我们有一堆的二进制数据，则他们的异或结果如下：

[ 0 1 0 ... 0 ] ^= 0 [0为奇数个]
[ 0 1 1 ... 1 ] ^= 1 [1为奇数个]
[ 1 1 0 ... 0 ] ^= 0 [0为奇数个]
[ ⁞ ⁞ ⁞  ⁞  ⁞ ] 对每位进制不断异或
[ 1 0 1 ... 1 ] ^= 1 [1为奇数个]

不难看出，最终每一个二进制位上的异或运算结果都取决于 0 或 1 是否出现了奇数次。假若抛开出现奇数次数字不看，由于其他所有数都只出现了偶数次所以在单独的二进制位上所有的 0 和 1 都是出现了偶数次则其异或的结果必然是 0。再代回出现奇数次的数，则可以得到对应二进制位置上的二进制数。依此类推，这样就可以得到了出现奇数次数的具体数值。 具体见以下Java代码。

public class Test {  
    public static void main(String[] args) {  
        int[] arr = {9,1,2,1,5,3,1,7,5,3,2,1,3,7,9,7,3,7,2,7,3,1,7,2,9,3,7,9,1};  
        int eor = 0;  
        for (int i : arr)
            eor ^= i;
        System.out.println(eor);  //output 7
    }
}

2 汉明码

汉明码（Hamming Code），是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，当计算机存储或移动数据时，可能会产生数据位错误，以侦测并更正单一的比特翻转错误。由于汉明编码简单，它们被广泛应用于内存（RAM）。 Hamming Code 的基本原理为 奇偶校验（Parity Check）与 交集和排除思想（Intersection And Exclusive） 也就是一开始引入的异或运算案例。

2.1 奇偶校验 Parity Check

给定以下二进制数：

在汉明码中，将需要传输的二进制数划分为 纠错码（Error Correcting Code → ! ） 与 原始数据（Raw Code）。汉明码对纠错码的处理模式如下：

1. 如果 1 出现的次数为偶数次，则纠错码保持为 0；
2. 如果 1 出现的次数为奇数次，则纠错码改变为 1，将数据中 1 的个数改变为偶数个； 数据接收方接收到处理后的汉明码后进行如下处理：
3. 若接收到的数据中 1 的个数为偶数（2n）个，则说明数据没有错误；
4. 若接收到的数据中 1 的个数为奇数（2n+1）个，则说明数据发生错误，出现了比特翻转（仅对于单一比特翻转错误）；

Q：若传输过程中纠错码发生了比特翻转呢？ A：同样也会被列入错误数据。

结论： 纠错码的存在不是 “用一个数据去保护所有数据” 而是 “通过一个数据改变整组数据的奇偶性”，纠错码本身就存在于整组数据中。换而言之，纠错码在保护其他数据的同时，也保护了纠错码自身。

缺点：

1. 奇偶校验只能得到某组数据是否发生错误，而不能精确地知道错误发生在哪里。
2. 发现错误后的解决措施为重新发送一份新的数据，这就导致了数据延迟的发生。
3. 单纯依靠奇偶校验无法发现两位比特翻转（01事件）的错误数据，在数据准确率上未做提升。

2.2 交集与排除 Intersection And Exclusive

在离散数学中，我们处理复杂的集合关系时会常用到韦恩图（Venn diagram）。例如：给定集合A、B、C如下图所示，求 (B∩C-A) 部分。这就是汉明码中的交集与排除思想。

1. 首先，利用奇偶校验已经确定了某组数据是否发生错误； 2. 接着，再通过交集与排除思想就可以确定发生比特翻转的二进制位； 现在，假定存在一组 16bit 的二进制数：

将其转换为 4x4 的数据矩阵：

想要得到发生比特翻转的二进制位置，只需要采用交集与排除的思想：将这整组数据按一定规律划分为不同的几组，并让他们之间有一定的交集。

2.2.1 数据组的交集如何取定

二分法：在数据结构与算法设计中我们知道，二分法是计算机中定位数据的好方法。对一半的数据做检查，若错误不在这一半内则必定在另一半内，依此类推得到错误数据的位置。

2.2.2 错误数据的行列确定

1. 取交集 结合上述的两种方法就可以得到发生比特翻转的二进制数的具体的行列位置

1. 解决矛盾

开头是假设有一个错误作为前提条件，来判断错误数据的位置。

若如果我们不知道盘面的数据里是否有错误，且行列校验全部都奇偶校验通过了。那么 0 号的数据位就不会被纳入保护范围，其错误与否不会影响奇偶校验的结果。

解决方案： 让 0 号的数据也不存储原始的数据，让其对整个盘面的数据做奇偶校验，这样就可以知道整个盘面内是否有错误，同时也能规避掉 0 号位无法保护的问题。

2.2.3 场景案例

场景模拟：服务商A传输了一段16bit位的数据给客户B，数据在传输过程中某一比特位上发生了比特翻转，以下为客户B接收到的数据矩阵示意图：

逐步分析： 1. 盘面分析 数据盘面中一共出现了 9 个 1 ，说明发生了比特翻转的错误； 2. 二四列校验

其中 1 出现的次数为 6 次**偶数**次，说明错误发生在一三列； 3. 三四列校验

其中 1 出现的次数为 5 次**奇数**次，说明错误发生在三四列； 综合2、3得到比特翻转位发生在第3列； 4. 二四行校验

其中 1 出现的次数为 5 次**奇数**次，说明错误发生在二四行； 5. 三四行校验

其中 1 出现的次数为 4 次**偶数**次，说明错误发生在一二行； 综合4、5得到比特翻转位发生在第2行； 6. 综合3、5方法确定比特翻转错误发生在第3列第2行（6号位）上；

2.2.4 问题与矛盾

Q：若错误恰巧发生在 0 号位的纠错码上，该判断方法是否会存在问题？ A：纠错码的存在不是 “用一个数据去保护所有数据” 而是 “通过一个数据改变整组数据的奇偶性”，纠错码本身就存在于整组数据中。

假设验证： 以下数据深色区域为占位纠错码：

经过校验发现修改任何一个位置上的纠错码都能通过奇偶校验发现纠错码出现了错误（红色位置）。但是，纠错码不影响原始数据，翻不翻转都无所谓。

2.3 多处错误情况

2.3.1 两处错误

假设下列数据矩阵盘中 第 5 号 和 第 15 号 位置数据发生翻转

但是，通过奇偶校验得到错误发生在第 3 列第 3 行（10号位）； 同时，盘面内一共有6个1偶数个说明盘面数据没有发生错误； 此时，两个结论发生矛盾，说明盘面存在两处错误； 但是无法定位错误的位置，需要重新传输数据。

2.3.2 三处及多处错误

汉明码无法解决 3 处错误，但是同时出现 3 个错误的可能性非常低。若真发生了，则更应该考虑降低错误发生的频率而非校验错误。 纠错码存在的意义： 使用尽可能少的数据，去解决不可避免的错误。而非所有错误。

3 汉明码的实际应用

第二节主要阐述了汉明码是如何解决 “单次比特翻转的纠正” 与 “二次比特翻转的校验” 的问题。第三节开始阐述汉明码与第一节中异或运算的巧妙结合来快速处理数据错误问题的思路。 将数据矩阵还原成横向排列：

可以发现，除了0号位置，其余汉明码的位置正好在1 2 4 8位置上，正好是2的第n次方。这是因为汉明码本质上和二分法的原理非常接近，所以校验位正好在数据组的一半的一半…的（标记为 - 的位置）位置上。

如果想传输更长的数据，则只需要在每个2的第n次方位置上放上一位纠错码，从而实现更大数据盘的支持。

关系： 数据盘越大，纠错码的占比越少，数据发生多个错误的几率越高。 数据盘越小，纠错码的占比越高，数据发生多个错误的几率越低。

在常见的 ECC 内存在传输数据时，每个块的大小通常是 72bit：

1. 其中 64bit 为原始数据；
2. 另外 8bit 为这 64bit 数据的纠错码； 正是因为汉明码的实现需要额外占用部分空间来存放纠错码，所以普通 8G 内存只需要 8颗 1G 的颗粒，就可以实现 8G 的容量。 而 ECC 内存为了实现 8G 的可用容量，则需要 9颗 1G 的颗粒。 就比如：3090Ti 打开 ECC 显存的功能以后，现存的可用容量下降也是因为这个原因。

3.1 少量纠错码的优势

使用少量的纠错码对大量的数据就错并不是汉明码最厉害的地方。因为现在有了更高级的 LDPC 纠错码，并被广泛应用于各种 SATA 和 NVME 硬盘的纠错上，他能查找并解决多位比特翻转。

LDPC（Low Density Parity Check Code）低密度奇偶校验码。最早在20世纪60年代由Gallager在他的博士论文中提出。

归功于汉明码的硬件实现更加简单，汉明码依旧作为最重要的纠错码被广泛应用于硬盘传输数据中。

3.2 汉明码矩阵

现给定一个 4x4 的汉明码矩阵，并规定 11 号位置为比特翻转的错误数据，并将所有位置的角标以二进制表示：

规定奇偶校验的结果：若某个区域出现了错误记录为1，反之记录为0；

将得到结果进行拼接得到 1101 刚好对应的十进制是 11 位 奇偶校验结果的排列组合都必然代表了一组位置（标识：- 区域 -）

提出假设： 位置信息和奇偶校验的结果可能存在某种必然的联系。

验证假设：

0000 0001 0010 0011
0100 0101 0110 0111
1000 1001 1010 1011
1100 1101 1110 1111

1. — 1 — 区域
   • 二四列位置的角标的第一位均为 1
   • 一三列位置的角标的第一位均为 0
2. — 2 — 区域
   • 三四列位置的角标的第二位均为 1
   • 一二列位置的角标的第二位均为 0
3. — 3 — 区域
   • 二四行位置的角标的第三位均为 1
   • 一三行位置的角标的第三位均为 0
4. — 4 — 区域
   • 三四行位置的角标的第四位均为 1
   • 一二行位置的角标的第四位均为 0

借助这个二进制角标的性质可以很容易地某一列、某一行上有多少个 1； 将上述假设与给出的比特翻转前的汉明码矩阵中 1 的位置全部提取出来得到：

0011 第一列 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 0
0110 第二列 1 ^ 1 ^ 0 ^ 0 ^ 1 ^ 1 = 0
1000 第三列 0 ^ 1 ^ 0 ^ 1 ^ 1 ^ 1 = 0
1100 第四列 0 ^ 0 ^ 1 ^ 1 ^ 1 ^ 1 = 0
1110
1111

对二进制位逐列分析就可以得到：— 1 — 区域有 2 个 1、— 2 — 区域有 4 个 1、— 3 — 区域有 4 个 1、— 4 — 区域有 4 个 1； 利用在第一节中的异或运算法则思路，就可以很容易地得到这些列上的 1 的个数是否满足偶数，具体计算见代码块。 这样得到的结果都是 0000 表明该矩阵盘未发生错误。 同样的，如果某一位发生了比特翻转，则 1 的二进制列就会发生变化。以上述给出的比特翻转后的汉明码矩阵为例：

0011 第一列 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1
0110 第二列 1 ^ 1 ^ 0 ^ 0 ^ 1 ^ 1 = 1
1000 第三列 0 ^ 1 ^ 0 ^ 1 ^ 1 ^ 1 = 0
1100 第四列 0 ^ 0 ^ 1 ^ 1 ^ 1 ^ 1 = 1
1110
1111
1011 这是第11号位置发生翻转后插入的1位置

这样经过4次异或运算就得到发生比特翻转数据的位置为 1011 其原理就是在正确的汉明码结果 0000 的基础上再与发生比特翻转的二进制位置 1011 进行异或运算，其结果必然遵循异或运算法则依旧位 1011。

所以汉明码矩阵的思路位：

1. 提取：提取所有1的二进制位置；
2. 异或：对所有二进制位置的每一位进行遍历式异或运算；
3. 纠正：得到的异或结果就是比特翻转位置并将其再次翻转得以纠正；

3.3 应用

汉明码矩阵凭借其简单的实现原理与简单的数字电路设计，使得其在 ECC 内存的纠错 上广泛应用，且其在性能开销上与普通硬盘来去仅在 3% 以内。

4 参考文献

[1] 硬件茶谈 Bilibili 2022. [2] 汉明码 百度百科 2022.