海明校验码是怎么实现的
如何一步步推导出海明码。
先提一个基本中的基本，异或。异或是两个数字相异则为1，相同则为0。举例1异或0=1，0异或0=0，1异或1=0。
为什么要提异或呢，因为异或是校验中最为根本的一个东西。假设我有原码1111和错误传输1110以及正确传输1111，那么我怎么能隐藏数据内容直接更快更好的知道数据是否传输错误了呢？
按位异或，如果无错，则异或值必全为0。1111与1111的异或为0000，1111与1110的异或为0001，看出来了吧，异或在校验中有着极为基本的作用。
那么我们为什么要提出海明码？直接用奇偶校验不行吗？
不行，因为奇偶校验只能发现错误，不能追溯错误。所以我们提出了一个疑问，怎么能校验错误并寻找到错误的根源？（先讨论最基本的情况，即只发生一位错误）
那么将问题具体化就是：假设我要传输一个四位数据，想要对此数据进行校验并能够定位错误位置，我该如何设计？
首先考虑校验码的位数问题。
首先要明确的是校验码的位数加上数据的位数必须能够被校验码表示。即假设数据4位，校验码2位，则共有6位，但校验码2位只能标识4种状态，4<6，不能表示清楚每一个位置。所以要增加校验码至3位。
但于此同时又有一个问题，假设我有5位数据，我可不可以使用3位校验码？5+3=2^3，看起来刚好能够表示每个位置的数据，但这是不可以的。比如我传输的数据是11111，结果传输错误，传输成了01111，那么这个时候我要表示第一位的数据传输错误，我的校验码应该是001，而不是000。此外，000还表示了数据无错，所以实际操作中我们计算可表示位数的时候是忽略掉全为0的一种情况。故校验码的位数加上数据位数应该小于等于校验码能表示位数（除去全0情况后的）。
解决了位数的问题，接下来要解决校验码放在哪的问题。
假设我把校验码放在编码的最前3位，数据放在后面4位。再假设我传输的数据是*** 1111（表示校验码）。那么当我的数据位置传输错误后，如传输成为了** 0111，那么我的校验码应该写成2进制的4，因为第4位出现了传输错误。所以整体表示成100 0111。但此时出现一个致命的问题：数据不出错的情况下，可能单纯的校验码传输错误了。也就是说，如果第1位的校验码传输错误时，传输结果为 100 1111。看到问题的所在了吗？根据我的校验码，我应该追溯第4位的传输错误，但是我的第4位是传输正确的，这也就导致了我无法真正的找到错误位。
那么该怎么设计呢？我们可以看到，纠错失败是因为歧义的问题，即无法分辨是校验码所表示位置传输错误还是校验码自身传输错误。那么取消掉歧义，让校验码的自身传输错误时恰好其位置表示是他自己，不就解决掉这个问题了吗？按照刚才的例子来讲，我们首先考虑三种校验码出错的情况，分别是001，010，100三种，那么很明显，我们直接把这三位校验码放到他所表示的位置中不就可以了吗？也就是将校验码放置到第1，第2，第4三个位置中，这样位置的表示与校验码的传输错误可以用同一个表示，不会导致前文说的纠错失败的问题。
好了，到这一步后，我们已经清楚了校验码的设计方式了，但是校验码怎么取值呢？上面所提到的是已知错误去判断校验码的取值，但实际中我们是反过来的过程，所以我们就要去考虑取值的问题。
先讲我们是怎么进行校验的，也就是校验的流程问题。
这一步我们先将校验码和数据部分分开，假设校验码是p，数据是d，然后我们的p是根据d在某种规则下得到的，那么我们只需要将接收到的数据部分按照规则重新计算后（即理论传输正确时校验码的值）与其校验码部分（实际传输的校验码的值）做异或运算，我们将这个异或运算的结果记为s，若结果全为0，则表示两者完全相同，若不全为0，我们还希望s恰好为传输错误的位置信息。即我们希望s=011时（s1=1，s2=1，s3=0），第3位的数据确认传输出错。（s1即为s的第一位，s2为第二位，d，p同理）
这里我们探讨的s其实就是上一阶段讨论校验码位置时的校验码值，因为它的实际意义就是某一位出现了错误，表示位置信息。（而p是实际上校验码位置应该填写的值）
那么接下来我们先来思考一个问题，s1=1代表什么？
这代表001，011，101，111位置中有一个必然出错了。也就是1，3，5，7位中有数据传输错误，s1=1。那我们又知道s1=（p1和d在p1下的规则运算后的异或），所以和p1有关的d就是抛开p1自身后的数据位数，即3，5，7位。
那么问题就简化了，我们需要将3，5，7位进行一种规则运算，使得3，5，7中一旦有一位发生了变化，他的规则运算结果就会由1变0，由0变1。
那么这种规则就是异或。3，5，7三位的异或将形成p1的值。如果其中1位发生了传输错误（或校验码本身第1位发生了传输错误），则按照异或规则形成的新p1必将与之前的p1相反，从而导致s1=1。
同样的，按照此理我们可以求出p2，p3的值。
再举p2的例子好了。s2=1代表着010 011 110 111中一个出错，即2，3，6，7四位中有一个出错。那么p2就应该是除了自己以外的3，6，7位进行异或运算后形成的结果。反过来说，如果3，6，7位发生传输错误（或校验码第2位发生了传输错误），则按照异或规则形成的新p2必与前p2相异，从而导致s2=1。
到此为止，对海明码的编码过程就结束了。后面举例如何校验码是如何验证的。
假设我传输的编码是1010010（正确的海明码)，结果传输成为了1110010，那么海明码将如何验证呢？
1110010 画线部分是校验码，即p1=0，p2=1，p3=0。
s1：d3异或d5异或d7等于0，0异或p1=0.
s2：d3异或d6异或d7等于0，0异或p2=1.
s3：d5异或d6异或d7等于1，1异或p3=1.
故110位置出错，即第6位出现错误。
转自知乎：
2021年04月09日
本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。
