海明校验的公式推导及讨论

date

type

status

slug

summary

一、思路

海明校验能实现一位错误的纠正和两位的识别。在以下推导时，我们忽略海明校验能实现两位错误的纠正，只设置一个核心目标（最后会推导，实现两位的识别是核心目标所附带实现的）：

💡

核心目标：实现一位错误的纠正

海明校验的提出可以分为以下两个关键的部分：

求出校验码位数的理论最小值；

构造出一种方便的且能达到理论最小值的校验方式。

二、校验码位数的理论最小值

2.1 考虑一个简单的情况

首先，我们将问题简化，假设

校验码与需要校验的数据是分别传输的两串数据；

校验码的传输是不会出错的；

需要校验的数据最多有一个数据出错。

我们讨论，这种情况下，我们需要的最少校验码需要多少位？以下分为几个小问题来思考这个简单的情况。

2.1.1 能实现纠错意味着什么？

由于每个数据位都只有两种情况或者，所以只需要能够识别是哪个位置的数据错误，就能完成纠正（如果这个位置是1，就将其改为0；如果这个位置是，就将其改为）。

能够识别是哪个位置的数据错误，意味着需要校验的数据在传输后的每一种错误情况都和校验码的一个情况相对应。换句话说，校验的数据在传输之后的所有可能组成的集合到校验码的所有可能组成的集合的映射是单射，在样本数量上，应该有

其中，是需要校验的数据传输后的可能情况的样本量，是校验码的所有取值的样本量。

2.1.2 需要校验的数据传输后的可能情况的样本量

由假设3，需要校验的数据最多有一个数据出错，因此会有

其中，为需要校验的数据的位数。

这个表达式的含义是所有可能由一个数据出错（k种情况）和不出错构成。

2.1.3 校验码的所有取值的样本量

由于每个数位共有两种取值，因此对于一个位数为的校验码，应该有

2.1.4 结果

综合问题1~3，可得

此时，距离得到海明校验的表达式已经很近了。

2.2 对简单情况的修正

在2.1，我们做出了如下假设：

校验码与需要校验的数据是分别传输的两串数据；

校验码的传输是不会出错的；

需要校验的数据最多有一个数据出错。

现在我们将假设1与假设2去掉，看会对表达式造成什么影响。

2.2.1 去掉假设1

去掉假设1（由于假设2还存在，意味着原本组成校验码的数，在合成新的一串数据之后，还是不会在传输的过程中出错的），不会对结果造成影响（想想为什么？），以下简单论述一下。

去掉假设1，只是意味着需要将两串数据按照一定规则合成一段数据，这个规则对于数据的收发方都是已知的。一种思考方式是，可以想象发送方将两串数据按照一定的规律合并成一串，接收方再按照相关的规律将这一串数据拆分成两串。或者可以这样想，“分成两串”之后推导出表达式各项的核心在校验码的保序和保值，这两个特点在不分成两串的时候也存在。

2.2.2 继续去掉假设2

显然去掉假设2一定会对表达式造成影响，而且去掉假设2意味着r的取值需要更大。这个影响相当于再引入了r个可能出错的数位。由校验码引入的可能错误的数位与本身要检测的数据可能出错的数位是等价的（由偶校验的特性决定的，使用2.3的偶校验的第二种理解即可很容易的想明白），相当于在传输之后的样本集中加入了r个样本，得到表达式

2.3 另一种图形化推导方式

以下，我们通过图形化的方式从另一个角度推导海明校验的不等式。我们从一个简单的情况开始。

首先我们讨论的是进行了两次偶校验的情形。如下图，每一个圆圈代表的是进行一次检验；其中，在区域I和III的元素是第一次偶校验检验的所有数位，在区域I和III的元素是第二次偶校验检验的所有数位。

由于最多出现一个错误（即不会出现错错为正的情况），当出错的数位在I中时，校验1出错而校验2不出错：当出错在II中时，校验1和校验2同时出错；当出错在III中时，校验1不出错而校验2出错。

在2.1.1，已经论述了能实现纠错，代表着每一种可能的出错情况都对应唯一一种验证结果。在图中，即表示I、II和III都只能最多含有一个数位。因此我们应该让I、II和III分别放入如下数位

当然，这里还需要解释一下。

为什么要放入两个校验码数位，不能在三个位置分别放入原数据的一个数位？

改变我们对偶校验的理解可以很容易回答这个问题。对于偶校验的校验码，我们有两种等价的理解。

第一种理解，偶校验的校验码传递的是偶校验的校验结果。即如果需要校验的数据1的个数为偶数时，校验码为0；如果需要校验的数据1的个数为奇数时，校验码为1。

第二种等价的理解，是更本质的理解。我们要求，所有校验的数位的1的数量必须是偶数，如果1的数量是奇数，我们就认为数据在传递的过程中出错。但是，我们怎么保证真实数据在传递之前1的数量就是偶数呢？答案是我们可以再补上一个数位。如果原始数据1的数量已经是偶数，就补上一个；如果原始数据1的数量是奇数，就补上一个。基于这种理解，我们也可以意识到校验码除了不传递我们想传递的原始文本包含的信息，其他方面都和原始文本是一致的（这里的一致指在出现错误，产生出错样本的可能性，纠错等方面）。

基于的二种理解，我们知道，每一次检验，只要包含了原始数据的一些数位，就要在这次检验中引入一个独立的校验码位。至于这个校验码填充在哪个空间，其实并不固定，我们也可以这样

而三次检验的图示如下，同样的，校验码所放的位置并不是唯一的，只要保证每一个检验的集合中都有一个独立于其他检验的校验码数位即可。

最后，我们就只需要推导一下进行r次检验所包含的独立区域有多少个即可。

每增加一次检验，都会与之前的所有小区块各相交一次，同时再产生一个不与任何检验的集合相交的小区块，有递推关系

可化为

由于，得到

当时，即进行次检验时，也同时引入了位校验码，能放置原数据数位的小区块数应为

原数据个数位不一定占据了所有的可用小区块，从而得到

三、构造一种方便的校验方式

在推导校验码位数的理论最小值时，其实也已经表明了理论最小值是一定能达到的，只需要给双方一套一致的检验规则，即提前告知双方韦恩图中的每一个小区块对应的是校验码或者原始数据的哪一位。至于校验码和原始数据怎么穿插成一串数据，以及具体将数据的哪一位放入哪一个小区块，都是能自由选择的。

海明校验巧妙在规定了一种穿插方式和一种对应方式，在这种穿插和对应方式下，正好能使得错误的数位与报错的特征以一种简单的方式相互对应起来。值得一提的是，由于这种相互对应过于简单，以至于掩盖了其背后的数学原理。

打个比方来说，在判断一个十进制下的数能否被3整除时，我们将所有数位依次相加，看能否被3整除。这种方法很简单，但是背后基于同余的数学原理就被隐藏了，因此当第一次看到这个判断法则时，容易摸不着头脑：这条判准为什么是对的？同样的情形发生在海明校验上。

海明校验的“巧合”是利用了二进制数的数制规律。在此简单论述一下。

我们绘制一个这样的示意图：

校验1、2、3的三个集合分别对应2的0次、1次和2次，并将其写在每个集合的没有重合的部分；

每个区块的数值由他所在的所有校验的值的和决定；

在这之后，你会发现此时三次校验所包含所有数值，就是其参与校验的海明码码号。

校验位	海明码位号	参与校验的海明码位号
1	1	3、5、7
2	2	3、6、7
3	4	5、6、7

此时“巧合”出现了，当某位数据出错时（假设是第6位），那么海明码位号为2和4的检验出错，而2+4正好就是6！

这种“巧合”在10进制下原理似乎并不明显，但是换成二进制表示就一目了然了，容易想明白，不多赘述。以下将图示和表格都改为二进制的方便观察。

校验位	海明码位号（2进制）	参与校验的海明码位号（2进制）	特点
1	1	11、101、111	xx1
2	10	11、110、111	x1x
3	100	101、110、111	1xx

四、推广

为了更深刻的思考海明校验背后的思想，我们试着在海明码的基础上做一些推广，并观察在推广过程中的变与不变，以此抓住其背后更为本质的东西。

4.1 三进制下的纠错实现

4.1.1 三进制的背景

4.1.2 偶检验在三进制下的推广

我们前面说了，偶检验可以看成通过凑一个数，使得所有数位1的个数为偶数个，或者说

4.1.3 三进制的一位纠错实现

4.2 二进制下两位纠错的实现

编辑历史 2024.9.3 创建文档，完成第一部分和2.1，2.2 2024.9.4 完成2.3和第三部分

🥳

PS：评论区可以用了，如果有问题可以写在下面🎇🎇🎇