奇偶校验

状态的反推：什么是奇偶校验？

想象你手里有一支按动式圆珠笔. 笔芯初始状态是缩在里面的. 按 下, 笔芯弹出；再按 下, 笔芯缩回. 现在, 闭上眼睛, 让你的朋友随机按动这支笔任意次. 当你睁开眼睛时, 如果看到笔芯是弹出状态的, 你虽然不知道朋友具体按了 下、 下还是 下, 但你绝对可以断定一件事：按动的总次数必然是一个奇数. 相反, 如果笔芯缩回, 按动次数必然是偶数. 这种利用二元状态（弹出/缩回、黑/白、/）的强制交替, 来判断某个未知过程“发生了什么”或“是否可行”的底层思想, 在数学和计算机科学中被称为奇偶校验（Parity Check）. 它不是一个抽象的公式, 而是一种严密的逻辑探针. 接下来, 我们将通过空间几何与计算机编码, 拆解这一工具是如何运转的.

铺瓷砖问题：空间的奇偶限制

我们先来看一个经典的铺设问题. 客厅地板上原本铺着 块 的正方形瓷砖（如图, 去掉了邻角的两块）. 但这些瓷砖已经破损, 需要重新更换. 可惜, 目前这种 的瓷砖缺货, 只有 的长方形瓷砖. 假设我们购买 块 的长方形瓷砖, 能不能将地面重铺呢？

直觉上, 原先面积是 , 现在 块 的瓷砖面积也是 , 似乎可行. 但如果我们利用奇偶校验的思想进行降维分析, 就会发现物理上的绝对限制：

• 第一步（初始状态构建）： 假设我们将整个棋盘像国际象棋那样进行黑白交替染色. 由于棋盘被去掉了两个方格（观察图形可知, 处于邻角的方格颜色相同, 假设这两个方格同为白色）, 所以剩下的区域包含 个黑格和 个白格.
• 第二步（施加几何限制）： 观察一块 的长方形瓷砖. 因为它的物理结构是一条连续的线段, 所以无论水平还是垂直放置, 它每次必然且只能覆盖一个黑格和一个白格（一奇一偶）.
• 第三步（得出结论）： 这意味着, 如果我们使用了 块长方形瓷砖, 它们必定精确消耗了 个黑格和 个白格. 此时棋盘上只剩下 个黑格. 因为一块长方形瓷砖绝对无法同时覆盖两个颜色相同的格子, 所以第 块瓷砖永远无法铺下.

在这个问题中, 同色的格子具有相同的奇偶性, 不同色的格子具有相反的奇偶性. 奇偶校验法通过确立“一黑一白必然成对消耗”的强制规则, 直接给出了问题不可行的定论.

奇偶校验码：计算机的数据装箱

除了判断空间的可行性, 奇偶性还可以用来传递信息并校验精确度. 最典型的应用就是计算机科学中的奇偶校验码（Parity Bit）.

计算机通过电缆或无线通道传输由 和 组成的比特序列时, 因为电压波动, 极易发生单个比特翻转的错误（例如 变成了 ）. 这就如同流水线上的装箱检查, 为了防错, 我们需要一个硬性规则.

假设规则是：每个数据包里 的总数必须是偶数. 如果原数据里 的个数是奇数, 就在末尾硬塞入一个 凑成偶数；如果是偶数, 就在末尾加 .

我们来看具体的推导：

• 发送端： 计算机要传输字符串 1000101. 因为里面含有 个（奇数个）1, 所以我们在它的末尾强行附加一个校验位 1, 变成 10001011. 此时, 整个序列里 1 的总数变成了偶数（ 个）.
• 传输错误： 假设在传输时, 左起第三位发生电压翻转错误, 变成了 10101011.
• 接收端校验： 接收端收到数据后开始数 的个数. 因为数出来的结果是 个（奇数个）, 而规则约定必须是偶数, 所以系统立刻断定：传输过程出错了, 要求重新发送.

通过在末尾增加一个简单的二元状态, 计算机实现了对整个系统的自动化查错.

帽子谜题：状态的递归解算

理解了状态的累加与校验后, 我们来看一个涉及信息传递的极限生存挑战.

有 名囚犯前后站成一排, 每个人都戴着红色或蓝色的帽子. 每个囚犯可以看到前面的人戴着什么颜色的帽子, 但看不到自己或后面的人的帽子颜色. 从最后一个人开始, 每个人必须大声猜出自己帽子的颜色. 猜错则被处决.

问题： 囚犯们该如何提前制定策略, 以确保至少 人必定生存？

如果囚犯们各自为战, 存活率只有 . 在直接给出策略前, 我们需要像工程师一样, 先拆解这个问题中的物理与信息约束：

• 第一步（已知条件的局限）： 每个人只能看到前方的帽子. 这意味着单凭眼前的视觉信息, 囚犯绝对无法推断出自身的颜色状态.
• 第二步（信息的跨时空传递）： 既然自身无法观测, 就必须依靠后面的人传递信息.
• 第三步（通信通道的限制）： 规则限定, 每个人开口只能说出一种颜色. 这意味着, 囚犯们必须找到一种方法, 将“前方红帽子的总数”这个复杂变量, 强行压缩并映射成只有两种状态（红/蓝）的二元信号.

那么, 究竟什么样的数学规律, 能把一个任意大小的整数, 完美映射为只有两种结果的二元状态呢？这就不可避免地要运用到我们刚刚建立的奇偶校验机制. 利用奇偶校验的思想, 将队伍变成一个“单向信息传递链”, 问题就迎刃而解.

囚犯们的制胜策略如下：

• 规则约定： 第 号囚犯（最后一名）承担校验位的角色. 如果他看到前面 人的红帽子总数是奇数, 他就喊“红色”；如果是偶数, 他就喊“蓝色”.
• 第一步（基准信息注入）： 第 号环顾前面 人. 假设他看到 顶红帽子, 因为 是奇数, 所以他大喊“红色”. 此时他有 的概率牺牲, 但他向全队广播了一个绝对的基准条件：前 人中, 红帽子是奇数.
• 第二步（状态递推）： 第 号囚犯接收到了这个基准条件. 接着, 他数了数排在他前面的 个人, 发现有 顶红帽子（偶数）.
• 第三步（逻辑解算）： 因为（前面 人的偶数红帽）+（第 号自己的帽子）=（总体 人的奇数红帽）, 所以第 号囚犯利用简单的减法立刻推断出：自己头上必然是一顶红帽子. 他大喊“红色”, 必定存活.
• 第四步（链式反应）： 第 号囚犯听到第 号喊了“红色”, 他在心里把总的红帽数量减去 （基准状态由奇数变为了偶数）, 再对比自己眼前的红帽数量, 继续解算……

以此类推, 通过第一个人提供的奇偶校验位, 后续的每一个人都能通过“已知的总奇偶性”减去“眼前观察到的奇偶性”, 计算出自己的绝对状态.

延伸思考：从“发现错误”到“纠正错误”

在前面的奇偶校验码例子中, 我们在数据末尾增加一个比特, 成功发现了传输过程中的错误. 但是, 单点校验存在一个物理极限：如果系统发现 1 的总数变成了奇数, 它只能发出“数据有误, 请重新发送”的警报, 却无法知道具体是哪一个位置的开关发生了翻转, 也就无法自动纠正错误.

那么, 我们能否打破这个极限？

假设我们改变数据的物理排列方式. 第一步, 我们不把数据排成单调的一条直线, 而是排成一个纵横交错的二维矩阵（例如 的方格）. 第二步, 我们为这个矩阵的每一行和每一列的末尾, 都分别计算并加上一个独立的奇偶校验位.

请尝试在纸上画出这个方阵并思考：

如果在这个带有行列双重校验的系统中, 有且仅有中间的一个比特在传输时发生了翻转错误. 这意味着什么？ 这意味着, 该比特所在的“那一行”的校验结果会报错, 同时它所在的“那一列”的校验结果也会报错. 利用这种横纵向的交叉定位, 我们是否就能像雷达一样, 精准锁定发生错误的具体坐标, 并直接在接收端将它翻转回正确状态？

这种利用多维物理空间的交叉状态来定位并修复错误的方法, 就是计算机底层极其重要的二维奇偶校验以及更高级的汉明码（Hamming Code）的基础逻辑. 从一维的“报错”升维到二维的“纠错”, 奇偶校验的思想并没有改变, 改变的仅仅是我们构建逻辑网格的维度.

互动答题

1. 齿轮谜题

2. 棋盘谜题

参考文献

[1] 陈永明. 少年趣味代数学[M]. 北京：商务印书馆. 2012, 290-292.

[2] Parity and the Prisoners Hat Puzzle. https://home.cs.colorado.edu/~srirams/courses/csci2824/lec1.pdf.