# 纠错码（Error Correcting Codes）

• 在信息传输中，信息往往会丢失甚至损坏。一个比较容易想到的方法是重复传输信息直到丢失的信息被补全，但这样效率很低。本节我们介绍一种新的信息传输思路——加入“纠错码”。纠错码是信息论研究中的一个重要部分，也是控制论、通信理论等的基础，同时也在现实生活的各方面都有着重要的应用。
• 纠错码主要分为两种：一种是基于有限域多项式的代数编码，另一种则是基于图论的组合编码。本节主要讨论的是前者，其也被称为里德-所罗门码（Reed-Solomon Code），由它的两位发明者命名。

# 擦除错误（Erasure Errors）

• 我们设想以下场景：在互联网中，我们尝试将信息通过打包进行传输。由于传输线路的不稳定性，一些包在传输过程中可能会丢失。具体而言，假设信息总共由$n$个数据包组成，其中最多有$k$个数据包会丢失。
• 那么，下面我们会展示如何将$n$个数据包通过编码扩增为$n+k$个，并让接收者在接收到任意$n$个后都能还原出原始信息。
• 首先，我们可以不失一般性地假设每个数据包里都是一个模素数$q$后的一个数（只要$q$足够大，覆盖所有数据包的数值范围即可）。接下来我们就能用$GF(q)$上的多项式处理这个问题【当然现实中会直接在2的幂次值域（比如$[0,2^{32})$）上处理】
• 设$n$个数据包分别为$m_1,\cdots,m_n$，且$m_i\in GF(q),1\leq i\leq n$，则：
  1. 存在唯一的$n-1$次多项式$P(x)$满足：$P(i)=m_i,1\leq i\leq n$
  2. 基于$P(x)$，我们就可以生成冗余的数据包：$c_1=P(1),c_2=P(2),\cdots,c_{n+k}=P(n+k)$。
  3. 这样我们获得任意$n$个数据包，就可以利用拉格朗日插值重构出$P(x)$的表达式，进而推出$m_1,\cdots,m_n$。
• 根据多项式理论，这种纠错编码已经达到了理论最优——如果收到的冗余数据包少于$n$，那么就无法再重新推出原始信息。

# 多项式插值补充

• 除了拉格朗日插值，这里再补充一种多项式插值方法：
  • 已知$d$次多项式的$d+1$个点：$(x_1,y_1),\cdots,(x_{d+1},y_{d+1})$，将它们分别代入以下方程：

    $$a_dx_i^d+a_{d-1}x_i^{d-1}+\cdots+a_0=y_i$$

    这样就得到了一个关于$(a_d,a_{d-1},\cdots,a_0)$的线性方程组，求解即可。
• 很容易证明最终得到的解是唯一的。【利用线性代数的知识易证】

# 一般性错误（General Errors）

• 接下来将擦除错误推广为更一般的错误——传输的信息中有一些被干扰，即正确的信息中混杂着错误信息。
• 然而，即使这样我们也可以使用多项式的理论得出：对于$n$个数据点的信息中有$k$个被干扰，那么只需要再多发送$2k$个数据点即可克服干扰，得到正确信息。具体说明如下：
  • 类似上面的情景，依然假设原始数据点为$m_1,m_2,\cdots,m_n$，发送的数据点为$c_1,c_2,\cdots,c_{n+2k}$，而接收者收到的数据点为$r_1,r_2,\cdots,r_{n+2k}$，且其中至多有$k$个数据点被干扰（替换为错误数据点）。（注：上面的所有数据点的值域均为$GF(q)$，$q$为足够大的质数）
  • 那么对于接收者而言，他需要通过收到的$n+2k$个数据点反推出$n-1$次多项式（至少需要$n$个正确的点），才能得到原始信息。
  • 虽然接收者不知道哪些点是正确的，但他知道$n+2k$个数据点中至少$n+k$个点是正确的。如果找出$n+k$个点能确定一个多项式的话，那么这个多项式与正确的多项式一定有至少$n$数据点重合，这恰恰就是确定一个多项式的最小点数。所以接收者得到的多项式一定是正确的多项式。
• 那么，问题的关键就在于如何确定$k$个错误数据点的编号。如果直接暴力搜索的话最坏需要搜索$\binom{n+2k}{k}$次，复杂度大概是指数级别，不太现实。我们实际会使用下述操作（也被称为伯利坎普-韦尔奇算法(Berlekamp-Welch algorithm)）：
  • 设正确的$n-1$次多项式为$P(x)$，并假设错误数据点的编号为$e_1,\cdots,e_k$。我们另外假设一个$k$次多项式（也称为错误定位多项式）

    $$E(x)=(x-e_1)(x-e_2)\cdots(x-e_k)$$

  • 那么，我们就有以下重要等式：

    $$P(i)E(i)=r_iE(i)\quad 1\leq i\leq n+2k$$

    这相当于$P(i)=r_i$与$E(i)=0$两个情形的并集。
  • 接着我们定义$Q(x)=P(x)E(x)$，则$Q(x)$为$n+k-1$次多项式。对$Q(x)$与$E(x)$均进行待定系数，再代回上面的等式得：

    $$\begin{aligned} &\left\{ \begin{aligned} &Q(x)=a_{n+k-1}x^{n+k-1}+a_{n+k-2}x^{n+k-2}+\cdots+a_1x+a_0\\ &E(x)=x^k+b^{k-1}x^{k-1}+\cdots+b_1x+b_0\\ \end{aligned} \right.\\ &a_{n+k-1}x^{n+k-1}+a_{n+k-2}x^{n+k-2}+\cdots+a_1x+a_0=r_i(x^k+b^{k-1}x^{k-1}+\cdots+b_1x+b_0)\hspace{0.5em}(\mathrm{mod}\hspace{0.2em}q) \end{aligned}$$

    其中第三个方程可以列为方程组，未知变量有$n+2k$个，方程也有$n+2k$个，最终就能解出唯一解$(a_{n+k-1},\cdots,a_0,b_{k-1},\cdots,b_0)$，进而得到$E(x)$，并通过$P(x)=\dfrac{Q(x)}{E(x)}$得到$P(x)\hspace{0.5em}(\mathrm{mod}\hspace{0.2em}q)$。
  • 最后我们将正确的编号（通过$E(x)$得到）代入$P(x)$中就能还原出原始信息。

# 拓展：纠错码本质的探索

• 最后我们进行一些拓展，不局限于里德-所罗门码，讨论上面这种用$n+k$（或$n+2k$）项解决$n$中$k$个错误的思想是否具有普适性。这里我们主要考察原始信息经过纠错编码后得到的内容：$c_1,c_2,\cdots$（称其为 “码词”(codewords)，记为$\vec{c}(m)$）
• 现在将码词视为一个向量（长度为$L$），并引入以下概念：
  1. 汉明距离（Hamming Distance）：衡量两个码词向量之间的相似程度。表达式：

  $$d(\vec{s},\vec{r})=\sum_{i=1}^L\mathbf{1}_{s_i\neq r_i}$$

  2. 考虑任意两个不同的信息$m$和$\tilde{m}$，它们对应的码词$\vec{c}(m)$与$\vec{c}(\tilde{m})$之间可能的最短距离：

     $$\min_{m\neq\tilde{m}}d(\vec{c}(m),\vec{c}(\tilde{m}))$$

     可以反映编码的干扰敏感度（最短距离越短，则敏感度越高，反之越低）；比如，对于一组长度固定的信息集合中的信息，它们的最短距离即为$1$，则它们就没有任何抗干扰能力。
• 对于擦除错误而言，可以推出：当码词的最短距离为$k+1$或更高时，其就能处理包含$k$个擦除错误的数据点。而当最短距离$\leq k$时，就可能从擦除错误的数据点中得到几个不同的还原信息。所以$k+1$已是最优。
• 对于一般性错误而言情况复杂一些。我们可以从干扰者的角度考虑一般错误数量与汉明距离的关系：
  • 假设原始码词与干扰目标码词之间的汉明距离为$d$。干扰者试图让接收者在接受到干扰码词后倾向还原为干扰目标码词，但最高的干扰数据点数小于$d$。
  • 那么，如果干扰者的最高干扰数据点数小于$\frac{d}{2}$，那么接收者还是能成功还原出正确的原始码词。
• 所以，对于$n$个数据点传输最多有$k$个一般错误的情况，码词间的最短距离就至少是$2k+1$，而里德-所罗门编码（将$n$个数据点扩充为$n+2k$个）就恰好满足这个条件。下面就来证明里德-所罗门编码得到的码词最短距离恰为$2k+1$：
  1. 最短距离$\leq 2k+1$。我们尝试构造两个码词，使它们的汉明距离不超过$2k+1$：
  • 设$\vec{m}_a=m_1\cdots m_n,\vec{m}_b=m_1\cdots \overline{m}_n$，两个向量除了最后一项不同，其他均相同。
  • 它们分别通过最高$n-1$次多项式$P_a(x)$与$P_b(x)$生成码词$\vec{c}_a$与$\vec{c}_b$（长度均为$n+2k$）。又因为两个原始向量前$n-1$项均相同，所以对应码词的前$n-1$项也相同。所以它们的不同项最多有$n+2k-(n-1)=2k+1$，即它们的汉明距离不超过$2k+1$。
  2. 最短距离$\geq 2k+1$。事实上我们只需要证明最短距离$\leq 2k$的情况不成立即可。
  • 这里我们同样设两个码词$\vec{c}_a$与$\vec{c}_b$，分别通过最高$n-1$次多项式$P_a(x)$与$P_b(x)$生成（注意和上面的例子独立）。
  • 如果$d(\vec{c}_a,\vec{c}_b)\leq 2k$，那么它们的相同项就至少为$n$，对应的两个多项式就有$n$个共同点，所以推出两个多项式完全相同。但这和我们假设的码词生成的多项式不同相矛盾，故反证法成立。

---

Yeah，CS 70的离散数学部分到这里就结束了，后面就都是概率论的部分了。考虑到笔者在校内已基本学习了这部分内容，故不会再这里重复记录。也就是说，本课程笔记就此完结！めでたしめでたし！
简单回顾一下，这门课是笔者UCB课程系列笔记的第一门课，当时选这门课主要是补充一些离散数学的相关知识我们这一届的培养方案把离散数学这门课给删掉了，或许是考虑到双学位压力比较大doge，这样能更好理解人工智能导论和数据结构这两门课（虽然有点用但不多）
当然，因为只有半学期的量，所以和国内的离散数学课内容相比，笔者感觉学的内容不算很多，但其实精髓应该基本都覆盖到了；况且，在这个AI时代，似乎概率论的作用比离散数学还更重要一些（
好啦，差不多就这样，希望你看得舒服，笔者再去补别的课了~