深入理解奇偶校验
问题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\) 位二进制编码来表示。比如我们有四种颜色如下：
| 颜色 | 编码 |
|---|---|
| 白色 | 00 |
| 黑色 | 01 |
| 红色 | 10 |
| 绿色 | 11 |
那么在 \(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 \oplus 0\) | \(0\) |
| \(0 \oplus 1\) | \(1\) |
| \(1 \oplus 0\) | \(1\) |
| \(1 \oplus 1\) | \(0\) |
可以这么理解，只要两个运算数相同，那么结果就是0，如果两个运算数不同，结果就是1。
应用在奇偶校验
说道奇偶校验的时候我们可能会有疑惑，为什么非要关注编码中\(1\)的个数是奇数偶数呢，关注\(0\)的个数不也一样有同样的效果吗。
这里其实是为了方便计算，因为一串编码中按位进行异或运算，结果是\(1\)就表示编码中\(1\)的个数是奇数。因为两个\(1\)做异或结果是\(0\)，而\(0\)在奇偶校验位中正好表示偶数个\(1\)，所以异或的运算性质正好可以帮助计算编码中\(1\)的个数的奇偶性。
应用在我们上面的问题A中，经过把帽子颜色抽象成二进制编码\(0\)和\(1\)后，每一个人就代表了一个二进制编码，由于帽子颜色只有两种，所以每个人代表的编码只有一位。所以最后一个人他报的内容可以通过异或前\(n - 1\)个人的编码得到，即：
\[ P_{n-1} = P_0 \oplus P_1 \oplus P_2 \oplus \dots \oplus P_{n-2} = \bigoplus_{i = 0} ^ {n-2} P_i \]
而抛开问题A不谈，这里介绍异或运算的另一个性质：
考虑一列数
\[ a_1,a_2,\dots,a_n \]
令
\[ p = a_1 \oplus a_2 \oplus \dots \oplus a_n = \bigoplus_{i = 1} ^n a_i \]
可知
\[ a_k = p \oplus \bigoplus_{i = 1\dots n, i \not =k}a_i \]
这就意味着，在\(p\)与\(a_1 \dots a_n\)这\((n + 1)\)个数中，任意\(n\)个数可以推得其余的一个。
知道上面的性质之后，我们再回到问题A上，现在我们有了\(P_{n-1}\)，而前\(n - 1\)个人要做的事情也可以通过上面的结论表示，其中第\(m\)个人\((0 \leq m \leq n - 2 )\)要做的运算可以表示为
\[ P_m = P_{n - 1} \oplus \bigoplus_{i = 0 \dots n-2, i \not= m} P_i \]
而衍生的问题B就是对每一位都做同样的操作即可。
另一种应用
其实前面讲的那个异或的性质就是一种硬盘储存结构$ $ 独立磁盘冗余阵列$ $RAID5的基本算法。
下面是关于RAID5的一部分介绍：
