Bóna · 枚举与解析组合学导论 · 第 8 章 对称结构

8.3　纠错码Error-correcting codes

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 即时自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标当信息在传输中可能出错时，怎样设计“编码方式”，让接收方即使收到带错误的信息也能把原意还原出来？本节给出衡量两个码字“差多少”的精确尺度——汉明距离（Hamming distance），并证明：只要任意两个码字之间足够“远”，就能纠正一定数量的错误。

8.3.1　彼此相距甚远的词Words far apart

即使一间酒吧和一间牙医诊所都缺少了若干平常该有的特征，我们多半仍能把它们区分开来。这两个场所如此不同，以至于只要看到它们的一部分，就足以判断哪个是酒吧、哪个是牙医诊所。事实证明，这一想法在编码理论（Coding Theory）中至关重要。

假设我们想用只含两个字母 \(0\) 和 \(1\) 的二元字母表（binary alphabet），通过手机发送一条消息。比方说我们要发送的是一条“是”或“否”的消息。我们可以与接收方约定：\(1\) 表示“是”，\(0\) 表示“否”。如果双方都确信打字时不会出错，这就足够简单了。

然而，如果错误是可能发生的，那么这种编码消息的方式就不高效了。事实上，仅仅一个错误就能把消息的含义完全颠倒成它的反面。要确保我们的消息不被误解，一种办法是把它反复发送好几遍，写在连续的若干位上。比方说，我们把消息发送三遍。如果消息是“是”，我们就发送数字 \(111\)；如果消息是“否”，我们就发送数字 \(000\)。这两个码字（codeword）彼此一点也不相像。因此，只要我们确信至多发生一个打字错误，就可以放心，我们的消息会被正确理解。事实上，如果我们想发送码字 \(111\)（或 \(000\)），且至多犯一个错误，那么收到的词将至少含两个 \(1\)（或至少含两个 \(0\)）。所以，只要每个码字中至多有一位是错误的，所有错误都能被纠正。

例（重复码如何纠错） 约定把每条消息重复三遍：“是” = \(111\)，“否” = \(000\)。
  1. 发送方想说“是”，发出 \(111\)。传输中某一位出错，接收方收到 \(101\)。
  2. 接收方数一数：\(101\) 里有两个 \(1\)、一个 \(0\)。它更接近 \(111\)（只差 \(1\) 位）而非 \(000\)（差 \(2\) 位）。
  3. 因此判定原消息是 \(111\) = “是”，错误被纠正。
  4. 反之若只发一位（\(1\) 表“是”，\(0\) 表“否”），收到的 \(0\) 既可能是 \(0\) 本身、也可能是 \(1\) 出错，无从分辨。重复三遍才让两个码字“拉开了距离”。
000 否 111 是 100010001 110101011 两个码字相差 3 位；各自“差 1 位”的词（圈内）互不重叠，故可纠 1 个错
左圈是与 \(000\) 仅差一位的所有词，右圈是与 \(111\) 仅差一位的所有词。两圈不相交，所以任何“至多错一位”的接收词都只落进一个圈，能被唯一地还原。

这个简单的例子可以朝许多不同方向加以推广。第一，可能要发送的消息不止两条。第二，编码字母表里的数字也可能多于两个。第三，打字时可能犯不止一个错误。尽管如此，我们这个简单例子的核心思想仍然至关重要：这个思想就是，如果各码字之间足够互不相似，那么即使犯了几个错误，我们仍能把它们区分开来。

现在，是时候把“足够不相似”和“几个错误”这两个概念变得更精确了。

定义 8.18 设 \(x\) 与 \(y\) 是同一有限字母表上、长度相同的两个词。则 \(x\) 与 \(y\) 的汉明距离（Hamming distance），记作 \(d(x,y)\)，是 \(x\) 与 \(y\) 取值不同的位置的个数。
例 8.19 若 \(x=100101\)，\(y=001100\)，则 \(d(x,y)=3\)，因为 \(x\) 与 \(y\) 在第一位、第三位、第六位上不同。
x = y = 100101 001100 三处不同 ⇒ d(x,y)=3
把两个等长的词上下对齐，逐位比较。红框标出取值不同的位，框的个数就是汉明距离。

既然我们已经有了两个词之间的距离概念，就可以仿照欧几里得几何（Euclidean geometry），定义球面与球的概念。

定义 8.20 设 \(x\) 是有限字母表 \(A\) 上一个长度为 \(k\) 的词。则以 \(x\) 为球心、\(r\) 为半径的球面（sphere）\(S_r(x)\)，是 \(A\) 上所有与 \(x\) 距离恰为 \(r\) 的 \(k\) 字母词组成的集合。
类似地，以 \(x\) 为球心、\(r\) 为半径的球（ball）\(B_r(x)\)，是 \(A\) 上所有与 \(x\) 距离至多为 \(r\) 的 \(k\) 字母词组成的集合。
球面 vs. 球：差在哪球面 \(S_r(x)\) 只收恰好差 \(r\) 位的词；球 \(B_r(x)\) 收差 0、1、…、直到 \(r\) 位的所有词（也包括 \(x\) 自己，因为 \(d(x,x)=0\le r\)）。所以 \(B_r(x)=S_0(x)\cup S_1(x)\cup\dots\cup S_r(x)\)，且 \(x\) 本身在球内、却不在半径 \(\ge1\) 的球面上。
例 8.21 设 \(A\) 为二元字母表，\(k=4\)，\(x=1010\)。则 \[S_1(x)=\{0010,\,1110,\,1000,\,1011\},\] 而 \[B_1(x)=\{1010,\,0010,\,1110,\,1000,\,1011\}.\]
逐位翻看 \(x=1010\) 的距离-1 邻居
  1. 把第 1 位 \(1\) 翻成 \(0\)：得 \(0010\)。
  2. 把第 2 位 \(0\) 翻成 \(1\)：得 \(1110\)。
  3. 把第 3 位 \(1\) 翻成 \(0\)：得 \(1000\)。
  4. 把第 4 位 \(0\) 翻成 \(1\)：得 \(1011\)。
  5. 这 4 个词构成球面 \(S_1(x)\)。再补上球心 \(x=1010\) 自己（距离 \(0\)），就得到球 \(B_1(x)\)，共 \(5\) 个词。
长度 \(4\) 的二进制词每位有 \(1\) 种翻法，故 \(|S_1(x)|=4\)，\(|B_1(x)|=1+4=5\)，与上面列出的吻合。

现在，可以把我们先前的观察用更精确的方式表述出来了。

命题 8.22 设 \(C\) 是有限字母表上一个由等长码字组成的码。假设对 \(C\) 中每一对码字 \(x\) 与 \(y\)，都有 \(B_r(x)\cap B_r(y)=\varnothing\)。那么，只要每个码字中至多有 \(r\) 位是错误的，所有错误都能被纠正。
为什么“球不相交”就能纠错设接收到的词为 \(w\)。若发送的码字是 \(x\) 且至多错 \(r\) 位，则 \(d(x,w)\le r\)，即 \(w\in B_r(x)\)。因为各码字的半径-\(r\) 球两两不相交，\(w\) 只可能落进唯一一个码字的球里。接收方只需找出“离 \(w\) 不超过 \(r\) 位”的那个码字，它必然就是原码字——于是错误被纠正。
码字 x 码字 y B_r(x) B_r(y) 收到的词 w 两球不相交 ⇒ w 只能属于一个码字的球 ⇒ 唯一还原
每个码字带一个半径 \(r\) 的球。球两两不相交时，任何“至多错 \(r\) 位”的接收词都只落入一个球，从而能被唯一地纠正回它的球心码字。

如果一个码 \(C\) 具有这样的性质：每个码字至多犯 \(r\) 个错误时所有错误都能被纠正，那么我们就称该码为 \(r\)-纠错码（\(r\)-error-correcting）。

读者也许会说，很好，但我们如何能快速地检验：对每一对码字 \((x,y)\)，球 \(B_r(x)\) 与 \(B_r(y)\) 的确不相交呢？读者在高中里一定学过三角不等式。这条不等式说，在欧几里得几何中，三角形两边之和总是大于第三边，其本质原因在于两点之间最短的路径是直线段。幸运的是，对有限字母表上的词，也有非常类似的结论成立。

引理 8.23（词的三角不等式） 设 \(x,y,z\) 是有限字母表上长度相同的三个词。则 \[d(x,y)\le d(x,z)+d(z,y).\]

证明见习题 10。

用具体数字检验三角不等式 取 \(x=000\)，\(z=011\)，\(y=111\)。
  1. \(d(x,z)\)：\(000\) 与 \(011\) 在第 2、3 位不同，故 \(d(x,z)=2\)。
  2. \(d(z,y)\)：\(011\) 与 \(111\) 在第 1 位不同，故 \(d(z,y)=1\)。
  3. \(d(x,y)\)：\(000\) 与 \(111\) 三位全不同，故 \(d(x,y)=3\)。
  4. 检验：\(3\le 2+1=3\)，不等式成立（此处恰好取等）。♦
直观上：从 \(x\) 改到 \(y\) 要翻的位，至多就是“先把 \(x\) 改到 \(z\)、再把 \(z\) 改到 \(y\)”这两段所翻位置的总和，所以 \(d(x,y)\) 不会超过两段之和。
推论 8.24 设 \(C\) 是同一有限字母表上由等长词组成的码。假设对 \(C\) 中每一对码字 \((x,y)\)，都有不等式 \(d(x,y)\ge 2r+1\) 成立。那么 \(C\) 是 \(r\)-纠错码。
证明. 只需证明：对 \(C\) 中每一对词 \((x,y)\)，都有 \(B_r(x)\cap B_r(y)=\varnothing\)，则由命题 8.22 即得所断言的结论。
现在假设存在 \(z\in B_r(x)\cap B_r(y)\)。那么由三角不等式可得 \[d(x,y)\le d(x,z)+d(z,y)\le r+r=2r,\] 这与 \(d(x,y)\ge 2r+1\) 矛盾。所以这样的 \(z\) 不存在。♦
把推论 8.24 的逻辑捋顺
  1. 想要的结论：每对码字的半径-\(r\) 球不相交（这样命题 8.22 就保证可纠 \(r\) 个错）。
  2. 反证：假设某对球相交，取交集中一点 \(z\)。则 \(z\) 离 \(x\) 不超过 \(r\)，离 \(y\) 也不超过 \(r\)。
  3. 用三角不等式：\(d(x,y)\le d(x,z)+d(z,y)\le r+r=2r\)。即两码字相距至多 \(2r\)。
  4. 撞上前提：但前提是任意两码字相距至少 \(2r+1\)，与“至多 \(2r\)”矛盾。
  5. 收尾：矛盾说明交集中的 \(z\) 根本不存在，即球两两不相交。证毕。
一句话：码字两两相距 \(\ge 2r+1\) ⇒ 半径-\(r\) 球两两不相交 ⇒ 能纠 \(r\) 个错。
x y z ≤ r ≤ r 若有公共点 z，则 d(x,y) ≤ r+r = 2r，与 d(x,y) ≥ 2r+1 矛盾
反证法的图示：若两球有公共点 \(z\)，则两球心相距至多 \(2r\)，与“两码字至少相距 \(2r+1\)”相冲突。故球不可能相交。

读者也许又会说，很好，但我仍然得检验：没有任何两个码字彼此距离小于 \(2r+1\)。这件事怎样才能快速完成呢？如果空间不成为顾虑，这本来不是问题。事实上，这非常……

（本节原文 PDF 至此处中断。）

即时自测
  1. 计算二进制词 \(x=110010\) 与 \(y=011011\) 的汉明距离 \(d(x,y)\)。
  2. 设字母表为二元、词长 \(k=4\)，\(x=0000\)。写出球面 \(S_2(x)\) 的全部元素，并求 \(|B_2(x)|\)。
  3. 某个二元码只有两个码字 \(00000\) 与 \(11111\)。它们的汉明距离是多少？根据推论 8.24，这个码最多能保证纠正每个码字中的几个错误？

返回 全书目录