深入理解奇偶校验

问题A

题目

考虑这样一个小问题：

我们现在一共有n个人， $n \in \Bbb N^\ast$ 。所有人排成一队站好后给每个人编号，从前向后依次为 $P_0P_1\dots P_{n-1}$ 。

每个人的头上都戴有一顶帽子，帽子只有黑白两种颜色，且除颜色外无其他差别。每个人所戴帽子的颜色是完全随机的。

这时每个人只能看到在自己前面的所有人的帽子颜色，但是看不到自己的帽子是什么颜色。

例如， $P_1$ 能看到 $P_0$ 帽子的颜色， $P_2$ 能看到 $P_1$ 和 $P_0$ 帽子得颜色， $P_{n - 1}$ 能看到除了自己外所有人帽子的颜色，而 $P_0$ 什么都看不到。

现在要求从 $P_{n - 1}$ 开始，依次向前报出自己所戴帽子的颜色。

为了方便，我们定义n个人中报对自己帽子颜色的人数为 $R_n$ 。

问：

这n个人应该采取什么样的策略才能使 $R_n$ 最大呢， $R_n$ 的数学期望是多少？

思考

首先我们先来考虑，是否存在这样的一种策略，使得 $R_n \equiv n$ 。

只要我们稍作思考，就知道这样的策略是不存在的。

我们以信息论中的比特作为信息量的单位，如果要使 $R_n \equiv n$ ，则整个n个人的系统需要能表达关于不同人帽子颜色的n个比特的信息。然而，对于整个系统而言，$P_{n-1}$ 的帽子的颜色始终是无法被这n个人观测到的，所以 $R_n \not \equiv n$ 。直观上，因为 $P_{n -1}$ 是第一个报自己帽子颜色的，而根据其能观测到的信息，$P_{n-1}$ 是无法推测出自己帽子颜色的，故无论采用什么样的策略，至少 $P_{n-1}$ 都无法保证一定能报对自己帽子的颜色。

那么能不能保证 $R_n \geq n - 1$ 呢？

理论上是有的，因为刚刚已经提到过了，整个系统最多可以准确表达 $n - 1$ 个比特的信息，故总有种策略可以保证 $R_n = n-1$ ，加上剩下一个比特不能准确表达的信息，故可以认为 $R_n \geq n - 1$ 。

解决方法

可以采用这样的一种策略，n个人约定好，如果 $P_{n-1}$ 看到的前 $n - 1$ 个人的帽子颜色中白色的个数为奇数，则 $P_{n - 1}$ 报白色，如果前 $n - 1$ 个人的帽子颜色中白色的个数为偶数，则 $P_{n - 1}$ 报黑色。

这样 $P_{n - 1}$ 报完之后，$P_{n -2}$ 可以根据其能看到的 $n - 2$ 顶帽子颜色和 $P_{n - 1}$ 所报的内容推理出自己帽子是什么颜色。

以此类推，$P_0 \dots P_{n - 2}$都能准确报出自己帽子的颜色，$P_{n - 1}$根据这样的策略报出的颜色有可能恰好是自己帽子的颜色，故$R_n \geq n - 1$。

期望：$\bar{R_n} = n - 0.5$。

问题B

题目

题目的内容与问题A几乎一致，只是现在帽子有 $2^k$ 种不同颜色，$k \in \Bbb N ^ \ast$。

那么在这样的条件下，如何使得 $R_n$ 最大，期望是多少？

思考

其实这个问题和之前的问题没有本质区别，我们只要把题目中 $\lceil$ 帽子的颜色 $\rfloor$ 这个量做一些抽象处理就很容易解决。

我们以问题A为例，帽子只有黑白两种颜色。我们可以定义黑帽子为0，白帽子为1，这样问题A的解决方案就可以解释成，前 $n - 1$ 位上1(白帽子)的个数为奇数，则 $P_{n-1}$ 报1(白色)，如果是偶数则报0(黑色)。

我们稍微缓一下就可以反应过来，这其实就是个奇偶校验中的奇校验问题。如果1的个数为偶数报1则是偶校验。

所以根据这样的思路，奇数偶数只能反映两种状态，所以我们用二进制的形式表示帽子的颜色。如果有 $2^k$ 种不同的颜色，我们就用 $k$ 位二进制编码来表示。比如我们有四种颜色如下：

那么在 $k$ 位每一位上都进行问题A那样的奇偶校验，就可以完成报颜色问题的解答。

解决方法

我们现在有 $n$ 个人， $2^k$ 种帽子，那么我们根据上面表格那种形式，可以对 $2^k$ 种颜色进行长度为 $k$ 的二进制编码。

而 $P_{n-1}$ 要做的就是计算前面 $n-1$ 个人每个人帽子颜色编码的每一位的奇偶校验值，然后组成 $k$ 位的编码作为自己要报的内容。前面 $n-1$ 个人报颜色的方式和问题A相似。

故我们能保证 $R_n \geq n - 1$ ，且期望 $\bar{R_n} = n - 0.5$ 。

问题延伸

以上两个问题都是用来描述奇偶校验的内容的，但是从奇偶校验出发，我们还能得到更多的信息。

异或运算

异或运算： $\oplus$

这是定义在布尔代数上的操作符，满足以下运算规则：

可以这么理解，只要两个运算数相同，那么结果就是0，如果两个运算数不同，结果就是1。

应用在奇偶校验

说道奇偶校验的时候我们可能会有疑惑，为什么非要关注编码中$1$的个数是奇数偶数呢，关注$0$的个数不也一样有同样的效果吗。

这里其实是为了方便计算，因为一串编码中按位进行异或运算，结果是$1$就表示编码中$1$的个数是奇数。因为两个$1$做异或结果是$0$，而$0$在奇偶校验位中正好表示偶数个$1$，所以异或的运算性质正好可以帮助计算编码中$1$的个数的奇偶性。

应用在我们上面的问题A中，经过把帽子颜色抽象成二进制编码$0$和$1$后，每一个人就代表了一个二进制编码，由于帽子颜色只有两种，所以每个人代表的编码只有一位。所以最后一个人他报的内容可以通过异或前$n - 1$个人的编码得到，即：

而抛开问题A不谈，这里介绍异或运算的另一个性质：

考虑一列数

令

可知

这就意味着，在$p$与$a_1 \dots a_n$这$(n + 1)$个数中，任意$n$个数可以推得其余的一个。

知道上面的性质之后，我们再回到问题A上，现在我们有了$P_{n-1}$，而前$n - 1$个人要做的事情也可以通过上面的结论表示，其中第$m$个人$(0 \leq m \leq n - 2 )$要做的运算可以表示为

而衍生的问题B就是对每一位都做同样的操作即可。

另一种应用

其实前面讲的那个异或的性质就是一种硬盘储存结构$\lceil$ 独立磁盘冗余阵列$\rfloor$RAID5的基本算法。

下面是关于RAID5的一部分介绍：