汉明码纠错原理

计算机网络-课程报告

汉明码纠错原理

本文主要参考了3blue1brown大佬的 汉明码，如何克服噪声 和 汉明码，优雅的全貌。

1.引言

光盘有了划痕却仍然能正确显示存储的内容，除非被划得遍体鳞伤。 原因是光盘存储数据有冗余，可以通过数学的方式恢复少量被破坏的数据。图像、视频、音乐等等媒体格式都设计有纠错的方案。所有数据在计算机中的存储最终都是一串0和1的序列，很容易想到一种最简单的纠错方案，就是把所有数据都存储3份。机器读取数据时比较这3份比特序列，如果有差别就以相同的那两个为准。但这就意味着有$\frac{2}{3}$的空间是冗余的，而且即使浪费了这么多空间，仍然不能可靠地解决3份数据里两个都被破坏了的情况。

所以问题来了：如何设计一种纠错策略，既能纠正错误，又能尽可能减少空间占用？纠错的基本原则就是，在所有可能的消息所组成的巨大空间中，只有一些子集才算得上是有效信息。举个例子，单词”Hello World”被拼写为”Helho Worhd”人们仍然能够识别出。当一条信息被修改时，接收方需要把错误信息纠正回最接近的有效信息。

2.奇偶校验

首先介绍一下前置知识：奇偶校验。奇偶校验过程中，发送方会调整数据块的一个比特位，其余的比特位被用作存放信息。这个被调整的比特位唯一的用途是确保这条信息中有偶数个1——如果其余比特位中1的总数是奇数，就将这个校验位调整为1，否则调整为0。通过这个方法，信息中任意一位的翻转都会导致1的个数变为奇数。这样接收方收到这条信息就可以确定其中有错误。

此方法有一个问题：偶数个位发生翻转时，接收方无法确定信息中是否有错误。两个错误都不能保证可靠也许听起来很差劲，但事实上在足够多的错误下任何纠错策略都不能保证信息准确，我们要做的是在给定最大错误数$N$的情况下，保证数据可靠。奇偶校验虽然很脆弱，但是把一个信息块转化为一个比特的思想可以作为更复杂方案的强大基础。下文将介绍一种纠错方案，在256个比特中仅仅占用9个比特，在有一处比特位错误时能够纠正它；在有两处比特位错误时虽然无法纠正，但是可以探测到有两个错误。之后会讨论如何把这个策略放大到更大的数据块。

3.汉明码

为了找到发生错误的位置而不仅仅是知道错误存在，汉明(Richard Hamming)想到了一个好方法，在做奇偶校验时不是对整块信息作校验，而是对其中精心挑选的一部分作校验，这样就可以通过一系列的验证来逐步定位发生错误的具体位置。这种校验的基本思想是如何通过多次奇偶校验来二分查找出错误所在。

举个例子：只对第2列和第4列这些奇数编号位置做校验，如果校验位有错误，那么接收方就可以把错误锁定在更小的范围内；如果校验位无误，那么要么整个信息没有错误，要么错误出在偶数编号位上。对一半的数据做校验看起来更低效了（因为这一块数据需要两个校验位而不是原本的一个），实际上通过有设计的组合，校验可以做到更高效。

我们举一个$4\times4$矩阵的例子，将这些比特位标记为0-15，只用其中的12个实际存储数据，4个纠错码分布在位置编号1248，也就是$2^n$位置。暂时假设错误最多只有1处。

在做奇偶校验时必须有一些用来控制整组数据奇偶性的特殊位，第一次校验通过1号位检查第2第4列，第二次检查通过2号位检查第3第4列。通过这两次检查可以将错误锁定在某一列。同样的道理，通过4号位和8号位的两次检查可以将错误锁定在某一行，此时成功确定了错误的位置。推广到 $16\times16=256$ 的数组上，只要8个校验位就可以确定错误所在的位置。

说回$4\times4$矩阵，4个校验位有16种可能的数值组合，对应于16个位置任意一个出错的16种情况。那么用什么来表达第17种情况——没有数据出错呢？我们选择舍弃0号位，也就是校验计算的时候根本不把0号位算在内，这样16种校验组合可以和16种情况一一对应。这种对15位数据进行处理表达了11位有效数据的方式称为(15,11)汉明码。

0号位其实还可以发挥一点作用：将其作为整块数据的奇偶校验码，这样我们就可以检测到2位的错误，虽然没有办法修复它。这个操作被称为扩展汉明码。

4.另一种理解

观察上文的简单示例，或许你已经发现了，四个校验位的数组拼在一起成为一个二进制数，其十进制值就是对应的位置号，例如四个校验位倒着排，0111，恰好代表7号位出错。通过这个特性可以使得硬件实现惊人的简单。这个特性并不是巧合，如果将16个二进制数填进对应的位置，那么仅有4个数是只包含一个1的，分别是1、2、4、8号位置。对它们的校验事实上就是在检查“错误是否出现在这一位上”。

异或运算XOR，可以有以下三种理解方式：

• 运算的两个二进制数中有且只有一个为1时结果为1，否则为0
• 两个数不同结果为1，相同结果为0
• 模二的加法，或不进位的二进制加法

对很多串数的的异或运算实际上就是在做奇偶校验，并把结果作为一串数保留下来。因此对汉明码的计算还可以有另一种理解方式：把数组中所有值为1的位取出来，它们对应的位置为一个二进制数，把这些二进制数放在一列，对每一位做异或运算，得到的比特编码实际上就是之前奇偶性检验出来的位置。

数据发送方直接调整刚刚校验出来需要调平的位置，这样整个数组再进行校验的结果就是0000。传输过程中任意一位的0翻转成1都会导致那一位对应的位置编码被加进需要异或运算的序列中，计算结果也就从0000变成了错误那一位的位置编码。同样的道理，1翻转成0会导致那一位对应的位置编码被移出需要异或运算的序列中，计算结果同样从0000变成了错误那一位的位置编码。

5.对多个块的组织

可以观察到，每多一个校验位，数据块的大小就可以翻倍。也就是说，数据块越大，冗余信息占比越小。但数据块不是越大越好，因为上面提到的汉明码只能纠正一个位的错误、指示两个位的错误，而数据块越大其中有多个错误的可能性就越高。实际上错误一旦产生往往会影响很多个位，导致整个块被毁掉。因此实际的处理中会把多个块的数据交替排列，这样可以把一连串的错误交错打散到许多个数据块中。当然现在已经有Reed Solomon等更先进的编码来处理这种问题。

6.后记

在此引用3blue1brown的话：

聪明的想法往往看起来尤其简洁，甚至会让人们以为理所当然。通过本篇介绍，希望汉明码这种算法存在的合理性对你来说已经显而易见。但千万不要草率地以为这些算法真的显而易见，因为这绝不简单。

聪明的想法看似太简单是因为我们只看到了最终的结果，清理掉了过程中的琐事，缄口不提其中的错误岔路，一笔带过解决问题的伊始和前路上无穷的可以探索的可能性，包括所有这一切。对一些特别的发明发现而言，大体上总是有第二个更深层次的原因——人们会忘记欣赏。

把信息当作比特位这种想法直到1948年才被集中整理成完整的理论收集在克劳德·香农独创的信息论论文中，这篇论文的发表和汉明提出他的算法是同时发生的。某种意义上讲，正是这篇奠定基础的论文展示了有效的纠错方式在理论上是永远可行的，无论出现错误的概率有多高。

几十年的快速发展，许多人已经习惯于把比特和信息放在一起思考，很容易忽视掉这两者是多么的不同。可悲的是，那些深远地影响了未来人们思想的想法最终会被年轻一代视作平淡无奇。