编码理论基础

1. 码的定义

• 定义一：设 $A$ 是一个有限集合，称之为字母表。$A$ 中元素构成的有限序列称为字或串。一个字中的元素的个数称为字长。

• 定义二：设 $A$ 是一个字母表。$A$ 上所有字的集合记为 $A^*$。$A^*$ 中包含一个长度的零的特殊字，称之为空字，记为 $\varepsilon$。对 $A^*$ 中的任意两个字 $x$ 和 $y$，将 $y$ 排在 $x$ 后面得到 $xy$，$xy$ 显然还是 $A^*$ 中的一个字，即运算即为字的拼接运算。显然，$A^*$ 对拼接运算为带幺半群，单位元为空字 $\varepsilon$。

• 定义三：设 $C$ 是 $A^*$ 的一个子集。如果对任意 $c_1, c_2, \cdots, c_m, c_1^{'}, \cdots, c_n^{'} \in C$，当

  $$c_1 c_2 \cdots c_m = c_1^{'} c_2^{'} \cdots c_n^{'}$$

  时，一定有 $m = n$，并且 $c_i = c_i^{'}, 1 \leq i \leq n$，则称 $C$ 为字母表 $A$ 上的一个码。码 $C$ 中的字称为码字。如果码 $C$ 中的码字长度都相同，则称 $C$ 为定长码；否则称其为变长码。如果 $|A| = n$，则称 $C$ 为 $n$ 元码。

在编码理论中，字母表 $A$ 一般取为有限域 $GF(q)$。设 $V(n, q) = GF(q)^n$ 表示 $GF(q)$ 上的 $n$ 维向量空间。$V(n, q)$ 中的向量 $(x_1, x_2, \cdots, x_n)$ 通常记为 $x_1, x_2, \cdots, x_n$。

• 定义四：$V(n, q)$ 中的任意一个非空子集 $C$ 称为一个 $q$ 元分组码。$C$ 中的每一个向量称为一个码字。如果 $|C| = M$，则称 $C$ 是一个 $q$ 元 $(n, M)$ 码，其中 $n$ 表示码长，$M$ 表示码字个数。

分组码是定长码，一个 $q$ 元 $(n, M)$ 码的所有码字长度都是 $n$。编码理论中主要讨论的就是分组码。

2. 码率的定义

• 定义五：一个 $q$ 元 $(n, M)$ 码的码率定义为

  $$R(C) = \frac{\log_q M}{n}$$

一个 $q$ 元 $(n, M)$ 码有 $M$ 个码字，可以用于传送 $M$ 个不同信息中的任意一个。然而，要传送 $M$ 个信息中的任意一个，码长只需要 $\log_q M$ 就足够了。因此，在一个 $q$ 元 $(n, M)$ 码中，每个码字中的信息位个数为 $\log_q M$，其余的 $n - \log_q M$ 位是冗余位，用于在信道接收端纠正信息在信道传输过程中发生的错误。一个 $q$ 元 $(n, M)$ 码使用 $n$ 个字符来传送 $\log_q M$ 个信息字符，显然一个好码应该具有较大的码率。

3. 汉明距离

• 定义六：设 $\boldsymbol{x}, \boldsymbol{y} \in V(n, q)$。$\boldsymbol{x}$ 和 $\boldsymbol{y}$ 的汉明距离 $d(\boldsymbol{x}, \boldsymbol{y})$ 定义为 $\boldsymbol{x}$ 和 $\boldsymbol{y}$ 中不同分量的个数。设 $\boldsymbol{x} = x_1 x_2 \cdots x_n$，$\boldsymbol{y} = y_1 y_2 \cdots y_n$。对于 $i = 1, 2, \cdots, n$，定义

  $$d(x_i, y_i) = \begin{cases} 0, \text{ if } x_i = y_i \\ 1, \text{ if } x_i \neq y_i \\ \end{cases}$$

  显然

  $$d(\boldsymbol{x}, \boldsymbol{y}) = \sum_{i=1}^n d(x_i, y_i)$$

  性质

  显然，汉明距离作为一个距离度量，满足距离度量的三大性质：非负性、对称性以及三角不等式。

  1. 非负性：$d(\boldsymbol{x}, \boldsymbol{y}) \geq 0$，且 $d(\boldsymbol{x}, \boldsymbol{y}) = 0$ 当且仅当 $\boldsymbol{x} = \boldsymbol{y}$；
  2. 对称性：$d(\boldsymbol{x}, \boldsymbol{y}) = d(\boldsymbol{y}, \boldsymbol{x})$；
  3. 三角不等式：$d(\boldsymbol{x}, \boldsymbol{y}) \leq d(\boldsymbol{x}, \boldsymbol{z}) + d(\boldsymbol{y}, \boldsymbol{z})$。

• 定义七：设 $C$ 是一个 $(n, M)$ 码。码 $C$ 的最小距离定义为 $C$ 中的任意两个不同的码字的汉明距离的最小值，记为 $d(C)$，即

  $$d(C) = \min\{d(\boldsymbol{x}, \boldsymbol{y}) | \boldsymbol{x}, \boldsymbol{y} \in C, \boldsymbol{x} \neq \boldsymbol{y}\}$$

• 定义八：设 $\boldsymbol{x} \in V(n, q)$。$\boldsymbol{x}$ 中非零分量的个数称为汉明重量，记为 $W(\boldsymbol{x})$。设 $\boldsymbol{x} = x_1 x_2 \cdots x _n$，对于 $i = 1, 2, \cdots, n$，定义

  $$W(x_i) = \begin{cases} 0, \text{ if } x_i = 0 \\ 1, \text{ if } x_i \neq 0 \\ \end{cases}$$

  显然

  $$W(\boldsymbol{x}) = \sum_{i=1}^n W(x_i)$$

  性质

  1. 对任意 $\boldsymbol{x}, \boldsymbol{y} \in V(n, q)$，$d(\boldsymbol{x}, \boldsymbol{y}) = W(\boldsymbol{x} - \boldsymbol{y})$。特别地，对任意 $\boldsymbol{u}, \boldsymbol{v} \in V(n, 2)$，$d(\boldsymbol{u}, \boldsymbol{v}) = W(\boldsymbol{u} + \boldsymbol{v})$。
  2. 对任意 $\boldsymbol{x} \in V(n, q)$，$W(\boldsymbol{x}) \geq 0$。$W(\boldsymbol{x}) = 0$ 的充分必要条件为 $\boldsymbol{x} = \boldsymbol{0}$。
  3. 对任意 $\boldsymbol{x}, \boldsymbol{y} \in V(n, q)$，$W(\boldsymbol{x} + \boldsymbol{y}) \leq W(\boldsymbol{x}) + W(\boldsymbol{y})$。

• 定义九：码 $C \subseteq V(n, q)$ 的最小重量定义为 $C$ 中所有非零码字的最小重量，记为 $W(C)$，即

  $$W(C) = \min\{W(\boldsymbol{x}) | \boldsymbol{x} \in C, \boldsymbol{x} \neq \boldsymbol{0}\}$$

4. 最近邻译码

• 定义十：设 $\boldsymbol{x}$ 是一个码字，经过信道传输后，在接收端我们收到的向量为 $\boldsymbol{y}$。由于噪声的干扰，可能 $\boldsymbol{y} \neq \boldsymbol{x}$，并且 $\boldsymbol{y}$ 可能不是一个码字。将 $\boldsymbol{y}$ 译为与 $\boldsymbol{y}$ 汉明距离最小的码字 $\boldsymbol{x}^{'}$ 是合理的。这种译码策略称为最近邻译码。
• 定义十一：满足下述两个条件的信道称为 $q$ 元对称信道：
  1. 每个字符在传输过程中发生错误的概率相同，都为 $p$；
  2. 如果一个字符在传输过程中发生了错误，则它错为其它 $q-1$ 个字符中的任意一个的概率都是相同的。

一般地，对于 $q$ 元对称信道而言，最近邻译码就是最大似然译码。

5. 检错和纠错

码的最小距离是刻画码的检错和纠错性能的一个重要参数。一般用 $(n, M, d)$ 表示码长为 $n$，码字个数为 $M$，最小距离为 $d$ 的一个码。

• 定理一：码 $C$ 至多可以检查 $t$ 个错误的充分必要条件为 $d(C) = t+1$。
• 定理二：码 $C$ 至多可以纠正 $t$ 个错误的充分必要条件为 $d(C) = 2t + 1$ 或 $2t + 2$。

因此，设 $C$ 是一个码，其最小距离为 $d$，则码 $C$ 至多可以检查 $d - 1$ 个错误，至多纠正 $\lfloor \frac{d-1}{2} \rfloor$ 个错误。

6. 编码理论的基本问题

一个好的 $q$ 元 $(n, M, d)$ 码应具有如下性质：

1. 为了更快的发送信息，码长 $n$ 应该小；
2. 为了更多的发送信息，码字个数 $M$ 应该大；
3. 为了能纠正更多的错误，最小距离 $d$ 应该大。

7. 完备码

• 定义十二：对任意 $\boldsymbol{x} \in V(n, q)$ 以及整数 $r \geq 0$，以 $\boldsymbol{x}$ 为中心 $r$ 为半径的球记为 $S_q(\boldsymbol{x}, r)$ 定义为

  $$S_q(\boldsymbol{x}, r) = \{\boldsymbol{y} \in V(n, q) | d(\boldsymbol{x}, \boldsymbol{y}) \leq r\}$$

• 定理三：对任意 $\boldsymbol{x} \in V(n, q)$，球 $S_q(\boldsymbol{x}, r)$ 中包含的向量个数为

  $$\binom{n}{0} + \binom{n}{1}(q - 1) + \cdots + \binom{n}{r} (q - 1)^r$$

• 定理四（汉明界）：对任意一个 $q$ 元 $(n, M, 2t+1)$ 码 $C$，都满足

  $$M\left\{ \binom{n}{0} + \binom{n}{1}(q - 1) + \cdots + \binom{n}{t} (q - 1)^t \right\} \leq q^n$$

  即

  $$M \leq \frac{q^n}{\sum_{i=0}^t \binom{n}{i} (q-1)^i}$$

• 定义十三：设 $C$ 是一个 $q$ 元 $(n, M, 2t+1)$ 码，如果汉明界等号成立，即

  $$M\left\{ \binom{n}{0} + \binom{n}{1}(q - 1) + \cdots + \binom{n}{t} (q - 1)^t \right\} = q^n$$

  则称 $C$ 为完备码。

8. 系统码

在代数编码理论中，通常取 $M = q^k$。一个 $q$ 元 $(n, q^k)$ 码可以对 $V(k, q)$ 中的全体向量进行编码。

• 定义十四：设 $C$ 是一个 $q$ 元 $(n, q^k)$ 码。如果存在 $k$ 个分量位置 $i_1, i_2, \cdots, i_k$，使得去掉码 $C$ 中所有码字的其它 $n - k$ 个分量后，所得到的向量全体为 $V(k, q)$，则称码 $C$ 为具有 $k$ 个信息位的 $q$ 元系统码。分量位置 $i_1, i_2, \cdots, i_k$ 称为信息位，其余 $n - k$ 个分量位置称为校验位。

  在系统码中，信息位和校验位是截然分开的。但在非系统码中，信息位和校验位无法截然分开。校验位就是冗余位，用于在信道的接收端纠正码字在信道传输过程中发生的错误。

9. 新码的构造

我们可以利用一个已知的码来构造新码：

9.1 延长码

将一个码中每个码字都增加一个或多个分量，称为码的延长。最常用的码的延长方法是对每个码字都增加一个奇偶校验位。

• 定义十五：设 $C \subseteq V(n, q)$ 是一个 $q$ 元 $(n, M, d)$ 码，定义

  $$\hat{C} = \{x_1 x_2 \cdots x_n x_{n+1} \in V(n+1, q) | x_1 x_2 \cdots x_n \in C, \sum_{i=1}^{n+1} x_i = 0\}$$

  称 $\hat{C}$ 为码 $C$ 的延长码。码字中的第 $n+1$ 个分量 $x_{n+1}$ 称为奇偶校验位。显然 $\hat{C}$ 是一个 $q$ 元 $(n+1, M, d^{'})$ 码，其中 $d^{'} = d$ 或 $d+1$。

9.2 截短码

码的截短是码的延长的逆过程。将一个码中的每个码字都删去一个或多个分量，称为码的截短。

• 定义十六：设 $C \subseteq V(n, q)$ 是一个 $q$ 元 $(n, M, d)$ 码，其中 $d \geq 2$，则将码 $C$ 中的每个码字都删去第 $i$ 个分量后，就得到一个 $q$ 元 $(n-1, M, d^{'})$ 码，其中 $d^{'} = d$ 或 $d-1$。

9.3 扩张码

对一个码增加一个或多个码字后所得到的码称为扩张码。

9.4 删除码

从一个码中去掉一个或多个码字后所得到的码称为删除码。

9.5 加长码

• 定义十七：设 $C \subseteq V(n, q)$ 是一个 $q$ 元 $(n, M, d)$ 码。对 $s = 0, 1, 2, \cdots, q-1$，令

  $$C_s = \{x_1 x_2 \cdots x_n x_{n+1} \in V(n+1, q) | x_1 x_2 \cdots x_n \in C, x_{n+1} = s\}$$

  称 $C_0 \cup C_1 \cup \cdots \cup C_{q-1}$ 为码 $C$ 的加长码。

9.6 缩小码

• 定义十八：设 $C \subseteq V(n, q)$ 是一个 $q$ 元 $(n, M, d)$ 码。由 $C$ 中第 $i$ 个分量都是 $s$ 的所有码字组成的码记为 $C_{i, s}$，其中 $1 \leq i \leq n, s \in GF(q)$。将 $C_{i, s}$ 中每个码字的第 $i$ 个分量去掉后得到的码称为码 $C$ 的缩小码。

10. 码的等价变换

• 定义十九：关于 $q$ 元 $(n, M)$ 码有两种置换。一种是关于码字分量位置集合的置换，称为换位型置换，记为 $\sigma_1$：

  $$\sigma_1 = \left( \begin{matrix} 1 & 2 & \cdots & n \\ \downarrow & \downarrow & \cdots & \downarrow \\ \sigma_1(1) & \sigma_1(2) & \cdots & \sigma_1(n) \end{matrix} \right)$$

  另一种是关于字母表 $A = GF(q) = \{0, 1, \cdots, q-1\}$ 的置换，称为换元型置换，记为 $\sigma_2$：

  $$\sigma_2 = \left( \begin{matrix} 1 & 2 & \cdots & n \\ \downarrow & \downarrow & \cdots & \downarrow \\ \sigma_2(1) & \sigma_2(2) & \cdots & \sigma_2(n) \end{matrix} \right)$$

• 定义二十：两个 $q$ 元 $(n, M)$ 码是等价的，如果能够通过一系列下述两种变换将其中一个码变为另一个码：

  1. 换位型置换：将码的坐标位置进行置换；
  2. 换元型置换：将出现在某一个固定坐标位置上的字符进行置换。

附录

• 《编码理论基础》by 陈鲁生