上周电脑坏了，没更周记，这周更。

最近计组学了海明校验，觉着还挺有意思。为什么需要这个东西懒得过多阐述，本质很简单。

构造

设数据位数为$n$，校验码位数为$k$，我们的$k$要求满足：

$$2^k - 1 >= n + k$$

现在说说为什么是这样。假设我们传输的数据为：

$$1010110$$

我们如果使用奇偶检验错误率极高。但我们想如果引入多个校验位就可以降低检验的错误率。我们可以利用小小的数学性质，在每个$2$的幂次位置插上一个校验位，再通过异或运算就可以扩大覆盖面，容错率极高。

在$1010110$中，$n = 7$，所以我们算出$k=4$。我们就在$2^0,2^1,2^2,2^3$处插入校验码。设校验码分别为$x_0, x_1, x_2, x_3$，我们要传输的带海明校验码的数据即为$x_0x_11x_2010x_3110$。

我们若要求$x_i$的值，就要把传输数据的位数（从左往右由1开始升序）转为二进制后，所有第$i$位（这里的$i$是二进制算法，从右往左由0开始升序）为1对应的数全部异或。将异或后的值取反即为$x_i$。

比如$x_0x_11x_2010x_3110$中，我如果要算$x_1$，3，6，7，10，11位满足条件。这时将他们全部异或$1 \oplus 1 \oplus 0\oplus1\oplus0 = 0$。所以$x_2=1$。

疑问

你可能要问了，要是异或式子中取到了未知数怎么办？好问题。你可以再看看，取不取得到？

传输后检验

我们拿到传输过来的数据后，将每个校验码与对应的值异或运算，如果结果不为1则说明其对应的值出现了错误。可一个校验码对应多个值要怎么办呢？好消息是一个值也有可能对应多个校验码。你可以通过排除法来确定出问题的范围。

其实还有更简单的方法，我们可以将所有校验码的异或结果拼接成一个二进制数，这个二进制数对应的十进制数即为错误的位置。