一般线性编码

二进制编码

关于编码，可参见Shannon熵。关于一般的域上的线性空间，可参见数值线性代数
二进制串的集合为
$\mathbb{F}_2^n = \{ x = (x_1, \ldots, x_n) : x_i \in \mathbb{F}_2 \}.$
它是一个 $n$ 维 $\mathbb{F}_2$ -线性空间，内积为
$x \cdot y = (x_1, \ldots, x_n) \cdot (y_1, \ldots, y_n) = \sum_{i = 1}^n x_iy_i.$
由二进制、逻辑和Boole代数可知， $\mathbb{F}_2$ 不是全序域。因此，由度量和拓扑可知，内积无法诱导度量，不过，我们可以使用其他度量
为一个度量空间，其中
$d_{Ham}(x, y) = card(\{ i : x_i \neq y_i \})$
称为Hamming码距
- 只需证明三角不等式。注意到
  $x_i \neq z_i \Rightarrow x_i \neq y_i \text{ or } y_i \neq z_i.$
  因此，
  $card(\{ i : x_i \neq z_i \}) \leq card(\{ i : x_i \neq y_i \}) + card(\{ i : y_i \neq z_i \}),$
  $d_{Ham}(x, z) \leq d_{Ham}(x, y) + d_{Ham}(y, z).$
二进制编码满足如下条件
- 基本码字 $\mathcal{C} \subset \mathbb{F}_2^n$
- 基本码字的个数为 $|\mathcal{C}| = M$
- 不同基本码字之间的最小距离为 $d$
在距离空间 $(\mathbb{F}_2^n, d_{Ham})$ 中，考虑一族互不相交的、半径为 $e = [(d - 1) / 2]$ 的闭球
$\{ \overline{B}(x, e) : x \in \mathcal{C} \}.$
如果一个二进制串 $y \in \overline{B}(x, e)$ ，那么 $y$ 和 $x$ 至多相差 $e$ 位， $y$ 可以纠错为 $x$ 。因为最小距离 $d$ 确定了纠错位数 $e$ ，所以在实际的通信中，我们希望 $d$ 越大越好

我们可以将 $\mathbb{F}_2$ 扩展到一般的有限域。由有限域的阶可知，我们可取有限域 $\mathbb{F}_q$ ，其中 $q = p^r$ ， $p$ 为素数。此时， $q$ 阶串的集合为
$\mathbb{F}_q^n = \{ x = (x_1, \ldots, x_n) : x_i \in \mathbb{F}_q \}.$
它是一个 $n$ 维 $\mathbb{F}_q$ -线性空间
一般线性编码满足如下条件
- 基本码字 $\mathcal{C} \subset \mathbb{F}_q^n$ 为线性子空间
- 基本码字的个数为 $|\mathcal{C}| = q^k$ ，其中 $k \leq n$ 为线性子空间的维数
- 不同基本码字之间的最小距离为 $d$