数据校验(深入篇)

这篇文章是对我看的科普视频的自我理解和转述，视频来自B站Up主：硬件茶谈。他关于内存数据流的一个视频，有兴趣的同学可以自己去看看。

背景

上篇文章向同学的大致讲解了，汉明码的工作原理，以及他的不足之处。这篇文章我将会带你走进二进制的世界，了解汉明码的魅力，看完这篇文章，你肯定会发出惊叹：卧槽！！

二进制

为了方便我们将二进制和汉明码联系起来，我们首先将汉明码的下标使用二进制表现出来

然后，再将一维数组变成二维数组

从这张图上，我们可以根据之前的数据块划分，找到一些特别的规律，从下面这种图，我们可以看到对应染色的数据部分的下标，第四位都是1。

而另一张图，染色数据部分的下标，第三位都是1

再看看横向划分的两张图，这两张图分别对应，数据下标第二位为1，另一张则是第一位为1

异或

在深入了解汉明码的过程中，我们需要了解一个很重要的二进制运算符异或，异或的数学符号为“⊕”，他的逻辑也很简单，值不同则结果为1，值相同则结果为0。如：1⊕1=0，0⊕1=1。

汉明码

上面的讲解，已经为我们深入理解汉明码打好了基础，现在我们提供一个数据，并翻转数组上的一个数据，生成一个存在错误的数据

行列检测法

我们先使用原本的行列检测的方法，配合二进制找到错误的位置

1. 检测列
   
   
   第一张图和第二张图上，染色部分的1的个数都不为偶数，所以都是错误的，再根据前文所讲的下标，那么错误数据的下标的第三位第四位都是1，即为__11。
2. 检测行
   同上可得，错误数据的下标的第一位为1，第二位为0。即为10__。
   综上所述，可得到错误数据的下标为1011。这个坐标正是我们当时翻转的数据的下标。仔细思考，我们就知道，这是二进制和二分法带来的规律。其实这和当初的计算错误数据的行列没有什么区别，只不过所有数据都有了一个唯一的下标。

改进

有什么办法让找到错误数据的这个过程变得更加简单呢。这就需要用到我们之前讲解的异或。首先我们提供一个二维二进制数组，如下

然后，我们将其中值为1的数据的下标列出来，他们分别是：0000，0001，0100，0110，1000，1001，1101，1111。将他们异或，你会惊讶的发现结果居然是0000，没错不管那些位置的值为1，只要这组数据是完整的正确的，那么其中值为1的下标的异或结果就一定是0000。

这里肯定同学说，这是巧合吧，怎么可能呢，我不信

没办法这就是汉明码的魅力，你可以自己定义一些二进制数组来试试，只要数据本身是正确的，那么结果一定是0000。（TIPS：至于导致这个结果的原因，我会在下一篇文章的<写在结尾>中回答大家，感兴趣的朋友也可以自己思考一下，为什么只要数据正确，不管1在哪，几个1，他们下标的异或一定等于0000。）
那么这个结论怎么能让我们找到错误的数据呢，现在我们将这组正确的数据中的一个数据做一次比特翻转，结果如下

这次我们同样将所有值为1的数据的下标做一个异或，上面我们得到了除翻转数据以外所有值为1的数据的下标的异或值，所以这里我们只要求0000⊕1011就行了，又知0000异或任意一个数，得那个数本身，所以结果就是1011，就是错误数据的下标。

这里又有同学会问了，你这个情况是0翻转成了1，多了一个1，所以异或的结果就是多出来的这个1的下标，那如果情况是1翻转成了0呢？

好吧，这都被你发现了，没办法我只能再提出一个公理了，又已知一个数异或自己得0000，也就是说一堆二进制数异或的结果是0000，那么不管里面少了哪一个数，其他二进制数异或的结果就是那个数。所以只需要提取所有二进制数是1的下标，然后把他们异或起来，得到的结果就是错误数据的下标，如果得到的结果是0000，那么就证明这个数据是正确的，没有发生比特翻转。

写在结尾

深入篇的内容也讲完了，想必看完的人都发出了惊叹，卧槽，这么神奇！其实这种校验数据的方法早已经被更先进的方法替代了，但因为汉明码的实现只需要一个异或，所以硬件实现的成本很低，所以有一些地方还会用到。感兴趣的朋友也可以去b站观看视频 【硬件茶谈】。天道酬勤，与君共勉！